明天旅游去爬山逛庙玩，今天练一天然后早早睡觉啦~

（带权并查集）

1 #include
      
        2 const int N=1e5+1; 3 int f[N]; 4 int r[N];//表示与父节点的关系，0同类，1不同类 5 int n; 6 void init(){ 7     for(int i=1;i<=n;++i){ 8         f[i]=i; r[i]=0; 9     }10 }11 int fin(int x){12     int t;13     if(x==f[x])return x;14     t=f[x];//记录父节点15     f[x]=fin(f[x]);16     r[x]^=r[t];//类别偏移,或r[x]=(r[x]+r[t])%217     return f[x];18 }19 void uni(int x,int y){20     int fx=fin(x);21     int fy=fin(y);22     f[fx]=fy;23     r[fx]=~(r[x]^r[y]);//类别偏移，或r[fx]=(-r[x]+1+r[y]+2)%224                         //  关系：fx与fy= fx与x+ x与y + y与fy25 }26 int main(){27     int t,m,a,b;28     char s[3];29     scanf("%d",&t);30     while(t--){31         scanf("%d%d",&n,&m);32         init();33         while(m--){34             scanf("%s%d%d",s,&a,&b);35             if(s[0]=='D') uni(a,b);36             else{37                 if(fin(a)!=fin(b)){38                     if(n==2) printf("In different gangs.\n");39                     else printf("Not sure yet.\n");40                 }41                 else{42                     if(r[a]==r[b])43                         printf("In the same gang.\n");44                     else printf("In different gangs.\n");45                 }46             }47         }48     }49     return 0;50 }
      

 

（带权并查集）：与上题差不多嗷。

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=2001; 5 int f[N]; 6 int r[N]; 7 int n; 8 void init(){ 9     for(int i=1;i<=n;++i){10         f[i]=i; r[i]=0;11     }12 }13 int fin(int x){14     int t;15     if(x==f[x])return x;16     t=f[x];17     f[x]=fin(f[x]);18     r[x]^=r[t];19     return f[x];20 }21 void uni(int x,int y){22     int fx=fin(x);23     int fy=fin(y);24     f[fx]=fy;25     r[fx]=~(r[x]^r[y]);26 }27 int main(){28     int t,m,a,b,k=1,f;29     scanf("%d",&t);30     while(t--){31         scanf("%d%d",&n,&m);32         init();33         f=1;34         while(m--){35             scanf("%d%d",&a,&b);36             if(f&&fin(a)==fin(b)&&r[a]==r[b])f=0;37             else uni(a,b);38         }39         printf("Scenario #%d:\n%s\n\n",k++,f?"No suspicious bugs found!":"Suspicious bugs found!");40     }41     return 0;42 }
       
      

 

（带权并查集）：栈顶方块为父节点，r[i]为i到父节点的距离，num[fin(i)]表示包含i的栈的大小，相减即可。

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=30001; 5 int f[N],r[N],num[N]; 6 int n; 7 void init(){ 8     for(int i=1;i
       
      

 

（带权并查集）

1 #include
      
        2 #include
       
      

 

（带权并查集）与上题差不多耶。

1 #include
      
        2 #include
       
      

 

 （带权并查集）经典吖orz.

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=50001; 5 int f[N]; 6 int r[N];//表示与父节点的关系,0表示同类，1表示被吃，2表示吃父节点 7 int n,ans; 8 void init(){ 9     for(int i=1;i<=n;++i){10         f[i]=i; r[i]=0;11     }12 }13 int fin(int x){14     int t;15     if(x!=f[x]){16         t=f[x];17         f[x]=fin(f[x]);18         r[x]=(r[x]+r[t])%3;19     }20     return f[x];21 }22 void uni(int x,int y,int d){23     int fx=fin(x);24     int fy=fin(y);25     if(fx==fy){26         if((r[x]-r[y]+3)%3!=d) ans++;27     }28     else{29         f[fx]=fy;30         r[fx]=(-r[x]+d+r[y]+3)%3;31     }32 }33 int main(){34     int m,a,b,d;35     scanf("%d%d",&n,&m);36     init();37     ans=0;38     while(m--){39         scanf("%d%d%d",&d,&a,&b);40         if(a>n||b>n||(d==2&&a==b))ans++;//假话：a或b都大于n，或a吃a41         else  uni(a,b,d-1);42     }43     printf("%d\n",ans);44     return 0;45 }
       
      

 

（带权并查集，枚举）石头剪刀布的游戏，并查集部分和上题食物链很像哦。枚举每个小孩为裁判时的情况，再并查集判断。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=501; 6 const int M=2001; 7 int f[N],r[N]; 8 int n; 9 void init(){10     for(int i=0;i
         
          ')D[i]=1;46             else D[i]=2;47         }48         cnt=ans=id=0;49         for(i=0;i
          
           ans) ans=j;//取最大的矛盾轮数57                         break;58                     }59                 }60             }61             if(!flag){ id=i; cnt++;}62         }63         if(cnt==0) puts("Impossible");64         else if(cnt==1)65             printf("Player %d can be determined to be the judge after %d lines\n",id,ans);66         else  puts("Can not determine");67     }68     return 0;69 }
          
         
        
       
      

 

（带权并查集，离散化）

题意：有一个已知长度的01串，给出多个区间[l,r]，并知道区间中1的个数是奇数还是偶数，问前几个区间互不矛盾。

离散化hash暂时还不会，先用map映射处理大数据问题吧。。

1 #include
      
        2 #include
       
      

 

写完随笔怎么突然有种很萌比的感觉。。。下个月的今天再复习一下好啦。。