CCPC-Wannafly Winter Camp Day3 (Div2, onsite) I 石头剪刀布(按秩合并并查集)

男娘i 2021-11-09 11:42 145阅读 0赞

**题解**：每次有两个事件：

1.  *y*

y去挑战*x*x，如果赢了可以坐在*x*

*  x的位置，打平或者输了就要被淘汰。
 *  询问在进行所有一类事件后，有多少种情况可以让*x*

1.  x现在还没有被淘汰。

对于第二类事件，我们假设*x*

x挑战了别人*a*a次，被挑战了*b*b次，那他没有被淘汰的概率就是3*n⋅(13)a⋅(23)b*3n⋅(31)a⋅(32)b。因此我们只要知道*a,b*a,b的值就可以知道答案。因此我们需要维护*a,b*a,b的值。对于第一类事件，我们画画图就会发现它会形成树状关系。那么我们就可以维护这颗树的节点信息，然后去询问就好了。很容易想到并查集了，但是这里似乎并不能直接用路径压缩，原因听一位巨巨说因为每个节点都有权值，根节点也有权值，每次查询的时候会重复累加根节点的信息，所以需要按秩合并。我们可以维护两个信息：每个人的总比赛场次，主场比赛场次。对于*y*y挑战xx，那么肯定y,xy,x的总比赛场次都加11，xx主场比赛场次加11。那么，对于集合yy合并到集合xx，会将xx设为yy的父亲，因为每个节点都包含着它当前这个集合的增量信息，也就意味着集合yy里的增量会凭空多增加xx的增量。因此合并的时候需要减去。然后findfind的时候累加增量即可。

这个题从概率的方向去考虑方案数

用并查集来维护之间的战斗关系，同时记录客场作战次数和主场作战次数

两个集合合并的的时候要减去fa的信息，

--------------------

1 #include<bits/stdc++.h>
     2 typedef long long LL;
     3 using namespace std;
     4 const int N = 2E5+10, mod = 998244353;
     5 LL w[N],v[N],rk[N],f[N];
     6 struct node
     7 {
     8     int fa;
     9     LL _w,_v;
    10 };
    11 LL _pow(LL a,LL n)
    12 {
    13     LL ret = 1;
    14     while(n)
    15     {
    16         if(n & 1) ret = a * ret % mod;
    17         a = a * a % mod;
    18         n >>= 1;
    19     }
    20     return ret;
    21 }
    22 LL Inv(LL n)
    23 {
    24     return _pow(n, mod - 2);
    25 }
    26 node _find(int x)
    27 {
    28     if(x == f[x]) return node{x,w[x],v[x]};
    29     node t = _find(f[x]);
    30     return node{t.fa, t._w + w[x], t._v + v[x]};
    31 }
    32 void _merge(int x,int y)
    33 {
    34     int t1 = _find(x).fa;
    35     int t2 = _find(y).fa;
    36     if(t1 != t2)
    37     {
    38         w[t1]++;
    39         v[t1]++;
    40         w[t2]++;
    41         if(rk[t1] >= rk[t2])
    42         {
    43             w[t2] -= w[t1];
    44             v[t2] -= v[t1];
    45             f[t2] = t1;
    46             rk[t1]++;
    47         }
    48         else
    49         {
    50             w[t1] -= w[t2];
    51             v[t1] -= v[t2];
    52             f[t1] = t2;
    53             rk[t2]++;
    54         }
    55     }
    56 }
    57 int main()
    58 {
    59 
    60     for(int i = 0; i < N; ++i)
    61     {
    62         f[i] = i;
    63     }
    64     int n,m,c,x,y;
    65     cin >> n >> m;
    66     LL t = _pow(3,n);
    67     for(int i = 0; i < m; ++i)
    68     {
    69         scanf("%d",&c);
    70         if(c == 1)
    71         {
    72             scanf("%d %d",&x,&y);
    73             _merge(x,y);
    74         }
    75         else
    76         {
    77             scanf("%d",&x);
    78             node t1 = _find(x);
    79             LL a = t1._v, b = t1._w - t1._v;
    80             LL ans = t * Inv(_pow(3,b)) % mod * _pow(2,a) % mod * Inv(_pow(3,a)) % mod;
    81             printf("%lld\n",ans);
    82         }
    83     }
    84     return 0;
    85 }

--------------------

转载于:https://www.cnblogs.com/zhangbuang/p/10878120.html