[CSPS 2022记录] [图论] [随机化] 星战
_Cheems
·
·
个人记录
题意
冗长的题意是做这道题的第一个难关。
简化后的题意是这样的：（不想码字了， 摘自题解）
1. 失活某条边；
2. 失活以某个点为终点的所有边；
3. 激活某条边；
4. 激活以某个点为终点的所有边。
然后问：如果只考虑激活的边，是否同时满足：
1. 所有的点出度均为 $1$；
2. 所有的点都满足，从这个点出发，可以走到一个环中。
## 思路
先从 可以反攻的条件 入手，容易发现 $\rm{1}$ 是 $\rm{2}$ 的充要条件。
回顾欧拉回路的条件：每个点的出度与入度相等。又因为 所有点出度均为 $1$ $\to$ 所有点入度都为 $1$，那么由定义可知满足条件 $1$ 意味着这个图是欧拉回路，也就是环了。
题目到这已经做完一大半了，直接暴力维护所有点出度就有 $40$，结合性质可以拿到 $50$、$60$ 分。
但我们的目标是满分！我们发现满足条件的图的形态大多一致，那么结合哈希的思想，动态维护每个图的哈希值，再与满足条件的图的哈希值对比，若一致则说明此时 **大概率** 可以反攻。
当然哈希函数的构造有很多，介绍一种（对于本题而言）容易实现的构造：
先预先为每个点 $i$ 赋值 $val_i$，定义点 $v$ 的哈希值 $h_v=\sum val_{u_i}$，其中 $u_i$ 满足存在一条被激活的边 $e(u_i,v)$。
那这个图的哈希值就是 $\sum h_i$。
而且我们发现，$val_i$ 的值变化多端，所以很难卡掉。
沿着这个思路写，我们又发现维护出度不太好搞，但维护入度相对简单，这是因为操作 $2,4$ 关注的是以每个点为终点的边，自然而然能想到维护入度。
同时，由上面的分析我们得知维护入度等价于维护出度，在正确性方面也是没错的。
于是正解思路呼吁而出：
先随机赋值 $val_i$，则该图可以反击的形态的哈希值 $bef=\sum val_i$，并记录原图每个点的哈希值 $in_i$、原图的哈希值 $now$。
为了方便实现，还需定义 $ru_i$ 为每个点的哈希值，但这个值是随操作动态维护的。
* 对于操作 $1$：$now-val_u$，$ru_v-val_u$。
* 对于操作 $2$：$now-ru_u$，$ru_u=0$。
* 对于操作 $3$：$now+val_v$，$ru_v+val_u$。
* 对于操作 $4$：$now+(in_u-ru_u)$，$ru_u=in_u$（先将 $u$ 完全摧毁，再修复，这样可避免重复计算）。
最终判断 $now=bef$ 即可。
## 代码
真的很好写，可能是思维方面比较难想，~~建议降蓝~~。
贴上我丑陋的代码~
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,K=1e7+5;
int n,m,q,t,u,v;
int in[N],ru[N],val[N],bef,now;
signed main()
{
srand(time(0));
cin>>n;
for(int i=1; i<=n;i++){
val[i]=rand()%K;
bef+=val[i];
}
cin>>m;
for(int i=1; i<=m;i++){
scanf("%lld%lld",&u,&v);
ru[v]+=val[u]; in[v]+=val[u];
now+=val[u];
}
cin>>q;
for(int i=1; i<=q;i++){
scanf("%lld%lld",&t,&u);
if(t==1||t==3){
scanf("%lld",&v);
}
if(t==1){
now-=val[u];
ru[v]-=val[u];
}
if(t==2){
now-=ru[u];
ru[u]=0;
}
if(t==3){
now+=val[u];
ru[v]+=val[u];
}
if(t==4){
now+=in[u]-ru[u];
ru[u]=in[u];
}
if(now==bef){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
```