【UOJ#550】【UNR#4】网络恢复
mrsrz
9月 15, 2020
随机权值法
题目大意：
交互题。
给定 $n$ 个点 $m$ 条边的随机无向简单图，你不知道哪些点之间有边。
你可以进行以下操作：
- 给每个结点赋一个权值。记为 $A_0,A_1,\ldots,A_n$。
- 选取一个边集 $S$。
- 调用
Query(A,S)。这个函数会返回一个长度为 $n$ 的数组 $B$，其中 $B_i$ 表示与 $i$ 通过 $S$ 中的边直接相连的所有结点的 $A$ 的异或和。
你至多可以调用 $50$ 次 Query(A,S)，要求找出所有边（不需要按编号顺序找出）。
题解：
首先考虑一些特殊情况的做法。
当图呈链状的时候，显然对于两端的点的 $B$，它恰好是另一个结点的 $A$，而其它的结点的 $B$ 为某两个 $A$ 的异或和。那么我们只需要找到在 $A$ 中出现的 $B$ 就能找到一条边。然后把这个点删掉继续做即可。
需要找一种赋值方法能使若干不同 $A$ 的异或和不是另一个 $A$。这里在 64 位整数中随机权值即可，冲突的概率极小。
考虑一般图的情况。我们可以用上述方法将图中的一度点都删掉。则图中的点的度数都至少为 $2$。
由于是随机图，它的子图每个点度数都大于等于 $3$ 的概率非常低，因此我们可以认为任意时刻至少有一个点的度数不超过 $2$。
考虑随机一个点 $x$，对于其他点，尝试用 $B$ 异或上 $A_x$。如果此时这个 $B$ 在 $A$ 中出现，说明这个点是二度点且与 $x$ 有边。那么把这条边删掉就又多了一个一度点，从而可以将这个点有关的边全部找出并删掉这个点。
重复此方法直到所有边都弄完即可。
我们如果一次对 $m$ 条边考虑的话，效率较低。由于有 $50$ 次询问可以用，我们将边随机均分为 $50$ 份，对其分别做上述算法即可。
稍微卡卡常就可以在时限内通过。
Code：
#include<bits/stdc++.h>
#include"explore.h"
using namespace std;
#define N NA
const int N=300006;
mt19937_64 mt(time(0)+(size_t)new int);
typedef unsigned long long LL;
int e[N];
LL val[N],b[N];
vector<LL>A,B;struct Hash_Table{
static const int M=19260819,md=M-2;
int cnt[M],head[M],nxt[M],tot;
LL val[M];
Hash_Table(){tot=0;}
inline int&operator[](const LL&k){
const int x=k%md;
for(int i=head[x];i;i=nxt[i])
if(val[i]==k)return cnt[i];
nxt[++tot]=head[x],head[x]=tot,val[tot]=k;
return cnt[tot];
}
inline bool count(const LL&k)const{
const int x=k%md;
for(int i=head[x];i;i=nxt[i])
if(val[i]==k)return 1;
return 0;
}
}mp;
set<int>st[N];
int cnt,n,m,K;
int Q[N*20],hd,tl;
void rep(int u,int v){
if(u>v)swap(u,v);
if(!st[u].count(v)){
st[u].insert(v);
Report(u,v);
++cnt;
}
}
void check1(){
hd=1,tl=0;
for(int i=1;i<=n;++i)if(b[i]){
if(mp.count(b[i]))Q[++tl]=i;
}
while(hd<=tl&&cnt<m){
int u=Q[hd++];
int fa=mp[b[u]];
b[u]=0;
if(!fa)continue;
rep(u,fa);
b[fa]^=val[u];
if(mp.count(b[fa]))Q[++tl]=fa;
}
}
void check2(){
for(int T=1;cnt<K;++T){
int id=mt()%n+1;LL v=val[id];
bool suc=0;
for(int i=1;i<=n;++i)
if(b[i]&&mp.count(b[i]^v)&&i!=id){
rep(i,id);
b[i]^=v,b[id]^=val[i];
suc=1;
}
if(suc)check1();
}
}
void Solve(int nn,int mm){
n=nn,m=mm;
for(int i=1;i<=m;++i)e[i]=i;
shuffle(e+1,e+m+1,mt);
const int Bl=m/50+1;
for(int i=1;i<=n;++i)
val[i]=mt(),A.push_back(val[i]),mp[val[i]]=i;
for(int l=1,r=Bl;l<=m;l+=Bl,r+=Bl){
if(r>m)r=m;
cnt=0;K=r-l+1;
vector<int>S;
for(int i=l;i<=r;++i)S.push_back(e[i]);
B=Query(A,S);
for(int i=1;i<=n;++i)b[i]=B[i-1];
check1();
check2();
}
}