Dish Owner（并查集）

链接：

题意分析：本题主要操作就是给出0 x y时。拥有第x道菜的厨师与拥有第y道菜的厨师pk。谁拥有的全部菜的当中一道菜（不一定是x或y）的分值比較高谁就获胜，并赢得loser的全部菜。

即比較的是每一个人分值最高的菜。所以对于非loser的人来说。他的分值最高的菜是不变的。

综合题意用并查集易解。

#include 
      
       const int Maxn=10004;int To[Maxn];int val[Maxn];int _find(int x){    if(To[x]!=x)        To[x]=_find(To[x]);     //路径压缩    return To[x];}void _merge(int x,int y){    int fx=_find(x);    int fy=_find(y);    To[fy]=fx;}int main(){    int T;    scanf("%d",&T);    while(T--){        int n;        scanf("%d",&n);        for(int i=1;i<=n;i++){            scanf("%d",&val[i]);            To[i]=i;        }        int query;        scanf("%d",&query);        while(query--){            int op;            scanf("%d",&op);            if(op==0){                int x,y;                scanf("%d%d",&x,&y);                int fx=_find(x);    //获得x，y的父节点                int fy=_find(y);                if(fx==fy)                    puts("Invalid query!");                else{                    if(val[fx]>val[fy]){                        _merge(x,y);                    }                    else if(val[fx]
      

Garden Game

链接：

题意分析：每响哨一次，处在位置i的人就移动到位置A[i]，当中A[i]是不反复的。易知经过有限次响哨后，必然可以恢复到初始态；当中会出现多个互不相关的循环。求出每一个循环的人数。计算其最小公倍数就可以。注意结果会超过int的范围。

Python版：

#coding:utf8def gcd(a, b):  #计算a。b的最大公约数    if(b == 0):        return a    return int(gcd(b, a%b))def fun(a, b):    _gcd=gcd(a, b)    product=a//_gcd*b   #用//运算符保证结果是整数    return int(product)T = int(input())while(T > 0):    n = int(input())    num = [0]    vis = [0]    x = input()    for i in x.split():        num.append(int(i))        vis.append(0)    div = []    st = 1    #计算每一个循环的人数    while(st <= n):        if(vis[st] == 0):            mark=st            vis[st]=1            cnt=1            nx=num[st]            while(mark != nx):                vis[nx] = 1                nx = num[nx]                cnt += 1            if(cnt not in div):                 div.append(cnt)        st += 1    ans = 1    for each in div:        ans = fun(ans,each)    print(int(ans%1000000007))    T -= 1

C++版：

因为中间运算结果甚至会超出64位整形的范围，于是我採用了因数分解的方法。

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int Maxn=100005;const int MOD=1000000007;int num[Maxn];bool vis[Maxn];int prime[10000],primecount=0;int totalcount[10000];void getprime(){    memset(vis,0,sizeof(vis));    int i,j;    for(i=2;i<100000;i++){        if(!vis[i]){            prime[primecount++]=i;            for(j=i+i;j<100000;j+=i){                vis[j]=1;            }        }    }}void getdivsor(int param){    int i;    int num=param;    int cnt;    for(i=0;prime[i]<=num&&i
         

div; while(st<=n){ if(vis[st]==0){ mark=st; vis[st]=1; cnt=1; nx=num[st]; while(mark!=nx){ vis[nx]=1; nx=num[nx]; ++cnt; } div.insert(cnt); } ++st; } long long ans=1; set

::iterator it; for(it=div.begin();it!=div.end();it++){ getdivsor(*it); } for(int i=0;i

0){ temp=(temp*prime[i])%MOD; totalcount[i]--; } ans=(ans*temp)%MOD; } printf("%lld\n",ans); } return 0;}