LINK：网络恢复
从这道题中我认识到了:要从各个特殊的 角度去思考 从而解决问题.
30分很好做 利用二进制来做 给先给前64每个点标一个(2^i)
然后查询 就轻易查出.
然后这样能查出(64*50=3200) 个点.
考虑树的情况.
以为这个随机过程树的高度为logn 结果不是/树的高度>50了.
我的错误做法是 随机一个根 然后不断向下扫 询问次数为树高 得分0.
考虑树的叶子节点 如果询问 他们上面的点权只受到一个点的影响.
所以给每个点随机赋权值 这样就能把叶子节点给晒出来了.
考虑筛出来之后 把叶子的父亲异或上叶子的点权 这样新一代的叶子就被生成了.
不断计算即可.询问次数O(1).
考虑基环树的情况 可以发现随机生成两个边的集合.
环大小至少为3 那么环全部出现在某个集合的概率至少为(frac{3}{4})
然后两次询问就完事了.
考虑正解：
由于当前图中一个点可能在多个环中.
我们可以分成50组处理且random shuffle 这样每一组中某个点所以环的个数为2的概率非常小.
这样需要处理一个点在环中的情况 做完叶子之后 可以随机两个点 看一下其中一个点异或另外一个点权是否出现解决环的问题.
在随机的情况下 这个算法跑的很优秀.
code
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 1000000000000000ll
#define ldb long double
#define pb push_back
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define vep(p,n,i) for(RE int i=p;i<n;++i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 13331ll
#define pf(x) ((x)*(x))
#define ui unsigned
#define EPS 1e-5
#define sq sqrt
#define mod 1000000007
#define md 998244353
using namespace std;
#include"explore.h"
//#include"grader.cpp"
#define ull unsigned long long
const int NN=50010,MM=300010;
map<ull,int>H;
vector<ull> A;
vector<int> S;
vector<ull>B;
int n,m,top;
int id[MM],w[MM],s[NN];
ull a[NN],b[NN];
queue<int>q;
inline ull R()
{
ull ans=0;
rep(1,64,i)ans=ans<<1|(rand()&1);
return ans;
}
inline void sc(int x,int y)
{
b[x]^=a[y];
b[y]^=a[x];
Report(x,y);
if(H.find(b[x])!=H.end())q.push(x);
if(H.find(b[y])!=H.end())q.push(y);
}
inline void modify()
{
while(1)
{
int x=rand()%top+1;
int y=rand()%top+1;
if(x==y)x=rand()%top+1,y=rand()%top+1;
x=s[x];y=s[y];
if(H.find(b[x]^a[y])!=H.end())
{
sc(x,y);
return;
}
}
}
inline void solve()
{
B=Query(A,S);
rep(1,n,i)
{
b[i]=B[i-1];
//cout<<b[i]<<' '<<a[i]<<endl;
if(H.find(b[i])!=H.end())q.push(i);
}
while(1)
{
if(q.size())
{
int x=q.front();q.pop();
if(b[x]==0)continue;
int tn=H[b[x]];
//cout<<tn<<endl;
sc(x,tn);
}
else
{
top=0;
rep(1,n,i)if(b[i])s[++top]=i;
if(top==0)return;
modify();
}
}
}
void Solve(int N,int M){
srand(time(0));
n=N,m=M;
rep(1,n,i)a[i]=R(),A.pb(a[i]),H[a[i]]=i;
//rep(1,n,i)cout<<a[i]<<endl;
int B=m/50+1;
rep(1,m,i)id[i]=(i-1)/B+1,w[i]=i;
random_shuffle(w+1,w+1+m);
int flag=1;
rep(1,50,i)
{
S.clear();
while(flag<=m&&id[flag]<=i)S.pb(w[flag]),++flag;
//cout<<S.size()<<endl;
if(S.size())solve();
}
}
</details>