P2342 叠积木

admin

https://www.luogu.org/problemnew/show/P2342

题目描述
约翰和贝西在叠积木。共有30000块积木，编号为1到30000。一开始，这些积木放在地上，自然地分成N堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠， 彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作，操作分为两种：

 第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠放到Y所在的那堆积木之上；

 第二种是统计操作，格式为“统计Z下方的积木数量”。Z代表一块积木的编号，意思是贝西需要报告在编号为Z的积木之下还有多少块积木

请编写一个程序，帮助贝西回答每条统计问题。

输入输出格式
输入格式：
 第一行：单个整数：P，1 ≤ P ≤ 10^5

 第二行到第P + 1行：每行描述一条命令，如果这行开头的字母是 M，代表一条移动命令，后面的两个整数代表上文中的X和Y；如果开头字母是 C，代表一条统计命令。后面的整数代表上文中的Z，保证所有的移动命令都有意义，X和Y不会已经出现在同一堆积木里

输出格式：
 对每一个统计命令，输出正确回答，用换行符分开每个查询的结果

输入输出样例
输入样例#1：
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
输出样例#1：
1
0
2
说明
第一次查询时， 1 下面只有一个 6；第二次查询时， 3 下面没有任何积木；第三次查询时，4 下面有两块积木：1 和 6

zhwang

1. #include<cstdio>
   
2. const int N=30000;
   
3. int sum[N+1];
   
4. int under[N+1];
   
5. int f[N+1];
   
6. int p;
   
7. int cnt;
   
8. int ans[1000001];
   
9. int getf(int num)
   
10. {
    
11.         if(num==f[num])
    
12.         {
    
13.                 return num;
    
14.         }
    
15.         int t=getf(f[num]);
    
16.         under[num]+=under[f[num]];
    
17.         f[num]=t;
    
18.         return f[num];
    
19. }
    
20. void merge(int a,int b)
    
21. {
    
22.         int t1=getf(a);
    
23.         int t2=getf(b);
    
24.         if(t1!=t2)
    
25.         {
    
26.                 f[t2]=t1;
    
27.                 under[t2]=sum[t1];
    
28.                 sum[t1]+=sum[t2];
    
29.         }
    
30. }
    
31. int main()
    
32. {
    
33.         freopen("testdata.in","r",stdin);
    
34.         freopen("testme.out","w",stdout);
    
35.         for(int i=1;i<=N;i++)
    
36.         {
    
37.                 sum[i]=1;
    
38.                 under[i]=0;
    
39.                 f[i]=i;
    
40.         }
    
41.         scanf("%d",&p);
    
42.         for(int i=1;i<=p;i++)
    
43.         {
    
44.                 char miao;
    
45.                 scanf("%c",&miao);
    
46.                 scanf("%c",&miao);
    
47.                 if(miao=='M')
    
48.                 {
    
49.                         int x,y;
    
50.                         scanf("%d%d",&x,&y);
    
51.                         merge(y,x);
    
52.                 }
    
53.                 else
    
54.                 {
    
55.                         if(miao=='C')
    
56.                         {
    
57.                                 int x;
    
58.                                 scanf("%d",&x);
    
59.                                 getf(x);
    
60.                                 printf("%d\n",under[x]);
    
61.                         }
    
62.                 }
    
63.         }
    
64.         return 0;
    
65. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int const maxn=30000+1;
   
4. int p,par[maxn],under[maxn],sum[maxn];
   
5. int f(int x)
   
6. {
   
7.     if(x==par[x])return x;
   
8.     int t=f(par[x]);
   
9.     under[x]+=under[par[x]];
   
10.     par[x]=t;
    
11.     return par[x];
    
12. }
    
13. void merge(int x,int y)
    
14. {
    
15.     int r1=f(x);
    
16.     int r2=f(y);
    
17.     if(r1==r2)return ;
    
18.     else
    
19.     {
    
20.         par[r1]=r2;
    
21.         under[r1]=sum[r2];
    
22.         sum[r2]+=sum[r1];
    
23.     }
    
24. }
    
25. int main()
    
26. {
    
27.     cin>>p;
    
28.     char ch;
    
29.     int a,b;
    
30.     for(int i=1;i<maxn;i++)par[i]=i,under[i]=0,sum[i]=1;
    
31.     for(int i=1;i<=p;i++)
    
32.     {
    
33.         cin>>ch;
    
34.         if(ch=='M')
    
35.         {
    
36.             cin>>a>>b;
    
37.             merge(a,b);
    
38.         }
    
39.         else if(ch=='C')
    
40.         {
    
41.             cin>>a;
    
42.             f(a);
    
43.             cout<<under[a]<<endl;
    
44.         }
    
45.     }
    
46.     return 0;
    
47. }
    

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int x,y,t,fa[310010],sum[310010],num[310010],all[310010];
    
14. char a[100];
    
15. int getf(int u)
    
16. {
    
17.         if(u==fa[u]) return u;
    
18.         int k=getf(fa[u]);
    
19.         sum[u]+=sum[fa[u]];
    
20.         return fa[u]=k;
    
21. }
    
22. int main()
    
23. {
    
24.         scanf("%d",&t);
    
25.         for(int i=1;i<=310010;i++)
    
26.                 fa[i]=i,num[i]=1;
    
27.         while(t--)
    
28.         {
    
29.                 scanf("%s",a);
    
30.                 if(a[0]=='M')
    
31.                 {
    
32.                         scanf("%d%d",&x,&y);
    
33.                         int t1=getf(x),t2=getf(y);
    
34.                         fa[t1]=t2;
    
35.                         sum[t1]=num[t2];
    
36.                         num[t2]+=num[t1];
    
37.                 }
    
38.                 else
    
39.                 {
    
40.                         scanf("%d",&x);
    
41.                         getf(x);
    
42.                         printf("%d\n",sum[x]);
    
43.                 }
    
44.         }
    
45.         return 0;
    
46. }

复制代码

walk_alone

不知道为什么只有18分

walk_alone

1. #include <cstdio>
   
2. int front[30001],sum[30001],father[30001];
   
3. int getfather(int x)
   
4. {
   
5.     if(father[x]==x)
   
6.                 return x;
   
7.     int ans=getfather(father[x]);
   
8.     front[x]+=front[father[x]];
   
9.     return father[x]=ans;
   
10. }
    
11. int main()
    
12. {
    
13.         int t,count=0;
    
14.     scanf("%d",&t);
    
15.     for(int i=1;i<=30000;i++)
    
16.         {
    
17.         father[i]=i;
    
18.                 front[i]=0;
    
19.                 sum[i]=1;
    
20.         }
    
21.     int x,y;
    
22.     char ch;
    
23.     while(count<t)
    
24.         {
    
25.         scanf("%c",&ch);
    
26.         if(ch=='M')
    
27.                 {
    
28.                         count++;
    
29.             scanf("%d%d",&x,&y);
    
30.             x=getfather(x);
    
31.             y=getfather(y);
    
32.             father[x]=y;
    
33.             front[x]=sum[y];
    
34.             sum[y]+=sum[x];
    
35.         }
    
36.         if(ch=='C')
    
37.                 {
    
38.                         count++;
    
39.             scanf("%d",&x);
    
40.                         printf("%d\n",front[x]);
    
41.                 }
    
42.     }
    
43. }

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int p;
   
4. const int mx=30010;
   
5. int par[mx],i,s[mx],under[mx];
   
6. int getpar(int a)
   
7. {
   
8.     if (a!=par[a])
   
9.     {
   
10.             int x=getpar(par[a]);
    
11.         under[a]+=under[par[a]];
    
12.         par[a]=x;
    
13.     }
    
14.     return par[a];
    
15. }
    
16. int check(int a,int b)
    
17. {
    
18.     if (getpar(a)!=getpar(b))
    
19.         return -1;
    
20.     return max(under[a],under[b])-min(under[a],under[b]);
    
21. }
    
22. bool union_(int a,int b)
    
23. {
    
24.     if ((a=getpar(a))==(b=getpar(b)))
    
25.         return 0;
    
26.     par[a]=b;
    
27.     under[a]+=s[b];
    
28.     s[b]+=s[a];
    
29.     return 1;
    
30. }
    
31. int main()
    
32. {
    
33.     cin>>p;
    
34.     for (i=1;i<=mx-1;i++) par[i]=i,s[i]=1;
    
35.     while (p--)
    
36.     {
    
37.         string s;
    
38.         int a,b;
    
39.         cin>>s>>a;
    
40.         if (s[0]=='M')
    
41.         {
    
42.             cin>>b;
    
43.             union_(a,b);
    
44.         }
    
45.         if (s[0]=='C')
    
46.         {
    
47.             cout<<check(a,getpar(a))<<endl;
    
48.         }
    
49.     }
    
50.     return 0;
    
51. }

复制代码