poj1988

发表于 | 分类于 ， ， | 阅读数 次

链接:poj1988

Description

  • Farmer John and Betsy are playing a game with N (1 <= N <= 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<= P <= 100,000)
  • operation. There are two types of operations:
  • moves and counts.
  • In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack
  • containing cube Y.
  • 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.
  • Write a program that can verify the results of the game.

    Input

  • Line 1: A single integer, P
  • 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.
  • Note that the value for N does not appear in the input file. No move operation will request a move a stack
  • onto itself.

    Output

  • Print the output from each of the count operations in the same order as the input file.

    Sample Input

    6
    M 1 6
    C 1
    M 2 4
    M 2 6
    C 3
    C 4

    Sample Output

    1
    0
    2

    题解

  • 带权并查集，和lg1196差不多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(regiser int i=x;i>=y;--i)
#define ll long long 
using namespace std;
const int N=1e5+7;
int f[N],rl[N],n,a,b,nm[N];
char c;

int find(int x){
    if(f[x]==x)return x;
    int t=find(f[x]);
    rl[x]+=rl[f[x]];
    return f[x]=t;
}

inline void un(int x,int y){
    int a=find(x);
    int b=find(y);
    f[b]=a;
    rl[b]=nm[a];		//更新x所在列头 
    nm[a]+=nm[b];		//更新b的长度 
    //nm[a]=0;			
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    rep(i,1,30000)f[i]=i,nm[i]=1;
    rep(i,1,n){
        cin>>c>>a;
        if(c=='M'){cin>>b;un(a,b);}
        else cout<<nm[find(a)]-rl[a]-1<<endl;
    }
    return 0;
}

更厉害的

  • 看了大神的博客，发现，根本不需要多开一个rl数组保存列长度
  • 果然是太弱了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
int f[N],dis[N],n,a,b;
char c;
int find(int x){
    if(f[x]<0)return x;
    int t=find(f[x]);
    dis[x]+=dis[f[x]];
    return f[x]=t;
}

inline void un(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        dis[y]=(-f[x]);
        f[x]+=f[y];
        f[y]=x;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    memset(f,-1,sizeof(f));
    rep(i,1,n){
        cin>>c>>a;
        if(c=='M'){cin>>b; un(a,b);}
        else cout<<f[find(a)]*(-1)-dis[a]-1<<endl;
    }
    return 0;
}