Cube Stacking

àì夳堔傛蜴生んèń 2022-06-01 04:20 189阅读 0赞

<table style="font-family: &quot;Microsoft YaHei&quot;;"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align: center; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">
      Cube Stacking 
    </div> 
    <div style="text-align: center; font-family: Arial, Helvetica, sans-serif; font-size: 12pt;"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;30000K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;26409</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;9239</td> 
       </tr> 
       <tr> 
        <td colspan="3" align="center" style="color: rgb(14, 173, 0);"><strong>Case Time Limit:</strong>&nbsp;1000MS</td> 
       </tr> 
      </tbody> 
     </table> 
    </div><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Description</p> 
    <div style="font-family: &quot;Times New Roman&quot;, Times, serif; font-size: 12pt;">
      Farmer John and Betsy are playing a game with N (1 &lt;= N &lt;= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1&lt;= P &lt;= 100,000) operation. There are two types of operations:&nbsp; 
     <br>moves and counts.&nbsp; 
     <br>* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.&nbsp; 
     <br>* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.&nbsp; 
     <br> 
     <br>Write a program that can verify the results of the game.&nbsp; 
     <br> 
    </div><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Input</p> 
    <div style="font-family: &quot;Times New Roman&quot;, Times, serif; font-size: 12pt;">
      * Line 1: A single integer, P&nbsp; 
     <br> 
     <br>* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.&nbsp; 
     <br> 
     <br>Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.&nbsp; 
     <br> 
    </div><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Output</p> 
    <div style="font-family: &quot;Times New Roman&quot;, Times, serif; font-size: 12pt;">
      Print the output from each of the count operations in the same order as the input file.&nbsp; 
     <br> 
    </div><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Sample Input</p><pre style="font-family: &quot;Courier New&quot;, Courier, monospace; font-size: 12pt;">6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
</pre><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Sample Output</p><pre style="font-family: &quot;Courier New&quot;, Courier, monospace; font-size: 12pt;">1
0
2
</pre><p style="text-align: left; font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue;">Source</p> 
    <div style="font-family: &quot;Times New Roman&quot;, Times, serif; font-size: 12pt;"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=USACO+2004+U+S+Open" rel="nofollow">USACO 2004 U S Open</a> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

题目大意：有N个立方体和N个格子，1~N编号，一開始i立方体在i号格子上，每一个格子刚好1个立方体。如今m组操作，M a b表示将a号立方体所在的格子的所有立方体放在b号立方体所在的格子的所有立方体上面。C x表示询问x号立方体以下的立方体的个数。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    #define N 30001
    int p,fu[N],zi[N],juli[N];
    int Make_set()//初始化并查集
    {
        int i;
        for(i=1;i<N;i++)
        {
            fu[i]=i;//按题目要求对盒子进行编号
            zi[i]=1;
            juli[i]=0;
        }
    }
    int Find_Set(int x)//找祖宗
    {
        int fx=fu[x];
        if(fu[x]!=x)
        {
            fx=Find_Set(fu[x]);
            juli[x]+=juli[fu[x]];
        }
        return fu[x]=fx;
    }
    void Union(int a,int b)//合并两个集合
    {
        int x,y;
        x=Find_Set(a);
        y=Find_Set(b);
        if(x==y)//相等则在同一个集合中
            return ;
        fu[y]=x;
        juli[y]+=zi[x];
        zi[x]+=zi[y];
    }
    int main()
    {
        while(scanf("%d",&p)!=EOF)
        {
            int i,j,a,b;
            char s[3];
            Make_set();
            for(i=1;i<=p;i++)
            {
                scanf("%s",s);
                if(s[0]=='C')
                {
                    scanf("%d",&a);
                    b=Find_Set(a);
                    printf("%d\n",zi[b]-juli[a]-1);
                }
                else
                {
                    scanf("%d%d",&a,&b);
                    Union(a,b);
                }
            }
        }
        return 0;
    }