1002：http://acm.hdu.edu.cn/showproblem.php?pid=5438
这个题其实读懂了没有什么坑点的，网赛大家都做得比较激动，没有仔细看题就一直提交，但是正确率太低
题意：n点m边，统计每个点的度数，将各个度数小于2的点从图中删去，并删去与其相邻的所有边，直到图中所有点的度数均不小于2
然后，统计各个奇数环中的所有点的价值之和
题解说是并查集，其实当做模拟题做很简单
第一部分删点就是深搜删，满足degree[i]就把i点删掉，并把 i 的所有邻点的度数均减1（相当于删边），然后递归即可。只要用个vis数组判断就是O（n）
第二部分就是深搜判断每个点属于的集合的点数，对于每个没有删除也没有访问的点进行深搜访问，统计集合中点的个数和价值和，若点数为奇数则累计，vis数组判断就是O（n）
细节：一、二部分的vis数组为同一个，因为在第一部分中被删除的点在第二部分中已经不需要考虑
struct node{
int v,next;
}edge[maxm];
bool Del[maxn];
int value[maxn];
int head[maxn],tot;
int Degree[maxn];
ll ans,temp,num;
void addedge(int u,int v){
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void Delete(int u){
Del[u]=true;Degree[u]=0;
for(int k=head[u];k!=-1;k=edge[k].next){
int v=edge[k].v;
Degree[v]--;
if (Degree[v]<2&&!Del[v]) Delete(v);
}
}
void dfs(int u){
num++;
temp+=value[u];
Del[u]=true;
for(int k=head[u];k!=-1;k=edge[k].next){
int v=edge[k].v;
if (!Del[v]) dfs(v);
}
}
int main(){
//input;
int t,n,m,i,j,k,u,v;
scanf("%d",&t);
while(t--){
ans=tot=0;
memset(head,-1,sizeof(head));
memset(Del,false,sizeof(Del));
memset(Degree,0,sizeof(Degree));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&value[i]);
while(m--){
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
Degree[u]++;
Degree[v]++;
}
for(i=1;i<=n;i++)
if(Degree[i]<2&&!Del[i]) Delete(i);
for(i=1;i<=n;i++)
if (!Del[i]){
temp=num=0;
dfs(i);
if (num&1) ans+=temp;
}
printf("%I64d\n",ans);
}
return 0;
}1005：http://acm.hdu.edu.cn/showproblem.php?pid=5438
这个题比1002感觉要难，觉得时间很紧张，其实暴力做的方法很简单，想怎么减时间比较麻烦
由于是并查集：所以双向边和单向边没有关系，都可以
根据样例来说，确定解题方向为并查集是没错，每个集合的点数统计在根节点上，然后最后统计时对于每个点去找根计算即可
《1》对于q次的查询，每次都需要添加不同的边的集合，按什么顺序操作？很明显：从小到大进行添边即可保证之前添加过的边不影响现在的边集而且也是必须要添加的，这样，对整个q次查询中，最多添加的边数为m（之前想的是对边排序然后每次二分添加；现在只需要对输入的所有边排序之后，按从小到大即可）
只需：输入的所有边排序；q次查询时按照小到大排序；输出前按照查询顺序排序即可
细节：添加边时要注意判断当前的边数必须小于等于总边数，因为有可能需要查询的值大于所有边长值
《2》为了省时间，能不能边合并节点边计算，这样可以减少最后统计时每个点找根的时间。其实是可以的，方法如下：
对于现在的两个点u，v，其父节点为fu，fv，其节点个数为num[fu]，num[fv]，那么在前一次统计时，有num[fu]*(num[fu]+1)+num[fv]*(num[fv]+1)，而现在如果fu和fv不等的话，两个集合需要合并，即f[fv]=fu，num[fu]+=num[fv]+1，而现在这个大集合有的统计数为num[fu]*(num[fu]+1)
由此得到方法，第k次查询的初值定为第k-1次查询的结果，然后合并时，减掉原来统计的，加上现在统计的就OK了
现在说完道理就可以贴代码了：
int t,tempedge,nowedge,totedge;
int n,m,q;
int f[maxn];
int num[maxn];
int head[maxn];
struct node{
int u,v,cost,Next;
}edge[2*maxm];
struct Node{
int Query;
int Number;
ll tot;
}ans[maxq];
int cmp1(Node a,Node b){
return a.Query<b.Query;
}
int cmp2(Node a,Node b){
return a.Number<b.Number;
}
int cmp3(node a,node b){
return a.cost<b.cost;
}
void addedge(int u,int v,int cost){
edge[totedge].u=u;
edge[totedge].v=v;
edge[totedge].cost=cost;
edge[totedge].Next=head[u];
head[u]=totedge++;
}
int find(int x){
if (f[x]==-1) return x;
return f[x]=find(f[x]);
}
int main(){
//input;
int i,j,k,u,v,cost;
scanf("%d",&t);
while(t--){
tempedge=totedge=0;
memset(f,-1,sizeof(f));
memset(num,0,sizeof(num));
memset(ans,0,sizeof(ans));
memset(edge,0,sizeof(edge));
scanf("%d%d%d",&n,&m,&q);
while(m--){
scanf("%d%d%d",&u,&v,&cost);
addedge(u,v,cost);
//addedge(v,u,cost);
}
sort(edge,edge+totedge,cmp3);
//for(i=0;i<totedge;i++) printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].cost);
for(i=1;i<=q;i++){
scanf("%d",&ans[i].Query);
ans[i].Number=i;
ans[i].tot=0;
}
sort(ans+1,ans+q+1,cmp1);
//for(i=1;i<=q;i++) printf("%d %d %d\n",ans[i].query,ans[i].number,ans[i].tot);
for(i=1;i<=q;i++){
ans[i].tot=ans[i-1].tot;
nowedge=tempedge;
while(edge[nowedge].cost<=ans[i].Query&&nowedge<totedge) nowedge++;
for(j=tempedge;j<nowedge;j++){
u=edge[j].u;
v=edge[j].v;
int fu=find(u);
int fv=find(v);
if (fu!=fv){
f[fv]=fu;
ans[i].tot-=num[fu]*(num[fu]+1)+num[fv]*(num[fv]+1);
num[fu]+=num[fv]+1;
ans[i].tot+=(num[fu]+1)*num[fu];
}
}
/*for(j=1;j<=n;j++){
int fj=find(j);
ans[i].tot+=num[fj];
}*/
//cout<<endl;
//for(j=1;j<=n;j++) printf("father:%d value:%d\n",f[j],num[j]);
//cout<<endl;
tempedge=nowedge;
}
sort(ans+1,ans+q+1,cmp2);
for(i=1;i<=q;i++) printf("%I64d\n",ans[i].tot);
//for(i=1;i<=q;i++) printf("%d %d %d\n",ans[i].query,ans[i].number,ans[i].tot);
}
return 0;
}1010：Lucas+孙子定理模板题：贴板子了
ll n,m,p;
int k,x;
ll a[maxn],b[maxn];
ll Exgcd(ll a,ll b,ll &x,ll &y){
ll d;
if (b==0){
x=1;y=0;return a;
}
d=Exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll mod_mul(ll a,ll b,ll mod){
ll ret=0;
while(b){
if (b&1) ret=(ret+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ret;
}
ll CRT(ll a[],ll m[],ll n){
ll M=1,d,ret=0,i,x,y,Mi,temp;
for(i=0;i<n;i++) M*=m[i];
for(i=0;i<n;i++){
Mi=M/m[i];
d=Exgcd(m[i],Mi,x,y);
temp=mod_mul(y,Mi,M);
temp=mod_mul(temp,a[i],M);
ret=(ret+temp)%M;
}
return (M+ret)%M;
}
ll quickmod(ll a,ll b){
ll ans=1;
a%=p;
while(b){
if (b&1) ans=ans*a%p;
b>>=1;
a=a*a%p;
}
return ans;
}
ll calc(ll n,ll m){
if (m>n) return 0;
ll ans=1,a,b;
for(int i=1;i<=m;i++){
a=(n+i-m)%p;
b=i%p;
ans=ans*(a*quickmod(b,p-2)%p)%p;
}
return ans;
}
ll lucas(ll n,ll m){
if (m==0) return 1;
return (calc(n%p,m%p)*lucas(n/p,m/p))%p;
}
int main(){
//input;
int t,x;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d%d",&n,&m,&k);
for(int i=0;i<k;i++){
scanf("%d",&x);
p=b[i]=x;
a[i]=lucas(n,m);
}
printf("%I64d\n",CRT(a,b,k));
}
return 0;
}到现在为止AC的题数到了可以进现场赛的边界了。。。。觉得自己真是好水。。。。。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
附带几个长春网赛的题解链接，方便大家一起学习：
官方英文题解：http://bestcoder.hdu.edu.cn/blog/2015-acmicpc-asia-regional-changchun-online-solution-document/
http://acmicpc.info/archives/1896
哥伦布序列（1003）完美打表：http://blog.csdn.net/fcxxzux/article/details/48420475
http://blog.csdn.net/lwt36/article/details/48415647
京公网安备 11010502036488号