link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/E
定义两种情况,m x y将包含x的stack移到包含y的stack上,c x,询问在cubex的下层有多少cube,
这题没有什么想法,后来是看刘汝佳的书上找到思路的,到现在还不能完全理解,先留代码吧~~~~
code:

/*看到刘汝佳黑书第82页银河英雄传说与此题思想类似,看他的思想往下做就好*/
/*下面a,b,c三个数组的定义为黑书中解释*/
#include <iostream>
#include <cstdio>
#define N 30010
using namespace std;
int a[N];/*表示cube i和a[i]为属于同一队列且a[i]在i前面,称cube a[i]为cube i的父亲*/
int b[N];/*表示cube i到cube a[i]之间的cube数量*/
int c[N];/*表示cube i所属队列后方的cube数量,包括本身*/

int find(int x)
{
    int t=x;
    if(x!=a[x])
    {
        t=a[x];
        a[x]=find(a[x]);
        b[x]+=b[t];/*不断更新数量*/
    }
    return a[x];
}

void merge(int x,int y)

{
    int xx=find(x);
    int yy=find(y);
    if(xx==yy)
        return;
    a[yy]=xx;
    b[yy]=c[xx];
    c[xx]+=c[yy];
}

int main()
{
    int n,x,y,i;
    char ch;
    scanf("%d",&n);
    for(i=1;i<=N;i++)/*一开始就是因为这个RE了,如果是n的话计算的时候会数组越界,警记*/
    {
        a[i]=i;
        b[i]=0;
        c[i]=1;
    }
    getchar();
    while(n--)
    {
        scanf("%c",&ch);
        if(ch=='M')
        {
            scanf("%d%d",&x,&y);
            merge(x,y);
            getchar();
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",c[find(x)]-b[x]-1);
            getchar();
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation