题解：P17486 第四槐安通道
ran_qwq
·
·
题解
赛时没注意到可以 sum=1 和 sum=2 分开做痛失首个月赛场黑。
首先考虑 n 次怎么做，对于任意四个数，经典小奥题，询问 (a_1,a_2,a_3),(a_1,a_2,a_4),(a_1,a_3,a_4),(a_2,a_3,a_4) 能求出和，进而反推这四个数。
发现如果问到一个总和为 0 和 3 一次可以确定三个数，可以减少一些询问。因为交互库自适应的所以随机打乱一下，然后从前往后问，问到全 0 或全 1 就跳过，不知道能拿多少分。特别的，对于末尾不足 3 个数的部分，要和已知的数拼到一起问。设 0 的频率为 p，则问出连续三个相同概率为 p^3+(1-p)^3，最劣是 \frac 14。
发现有些组形如 $(1,0,0)$，问出和以及第一个数就能推出后面两个，所以考虑先递归求解所有第一个数，再递归求解仍未确定的第二个数。在 $sum=1$ 和 $sum=2$ 中出现这样的组概率为 $\frac 13$，这样 $T(n)=T(\frac n4)+T(\frac n6)+\frac n3=\frac {4}7n$。能拿到 $97$ 分。
注意到考虑所有 $sum=1$，它 $0$ 的频率是 $p=\frac 23$ 而非 $\frac 12$。所以对 $sum=1$ 和 $sum=2$ 分开做，两个子问题出现三个连续相同概率就是 $(\frac 23)^3+(\frac 13)^3=\frac 13$ 了。这种情况下 $T'(n)=T'(\frac 29n)+T(\frac 4{27}n)+\frac n3$，又有 $T(n)=T'(\frac n4)+T'(\frac n6)+\frac n3$，可以解得
$$T(n)=\frac{37}{66}n$$
:::info[代码：]
```cpp
#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
bool Mbg;
const int N=8.1e5+10,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,const char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,const char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
//#define test
int dream(int x, int y, int z);
#ifdef test
int C,a[N];
int dream(int x,int y,int z) {
C++;
return a[x]+a[y]+a[z];
}
#endif
int p[N];
vector<bool> as;
mt19937_64 rnd(time(0));
void soln(vi p) {
int n=p.size();
for(int i=1;i<=n/4;i++) {
int A=dream(p[i*4-4],p[i*4-3],p[i*4-2]);
int B=dream(p[i*4-4],p[i*4-3],p[i*4-1]);
if(A==3&&B==3) {as[p[i*4-4]]=as[p[i*4-3]]=as[p[i*4-2]]=as[p[i*4-1]]=1; continue;}
if(A==0&&B==0) {as[p[i*4-4]]=as[p[i*4-3]]=as[p[i*4-2]]=as[p[i*4-1]]=0; continue;}
int C=dream(p[i*4-4],p[i*4-2],p[i*4-1]);
int D=dream(p[i*4-3],p[i*4-2],p[i*4-1]);
// wr(A," "),wr(B," "),wr(C," "),wr(D,"\n");
int s=(A+B+C+D)/3;
as[p[i*4-4]]=s-D;
as[p[i*4-3]]=s-C;
as[p[i*4-2]]=s-B;
as[p[i*4-1]]=s-A;
}
}
void sol(vi vc) {
if(vc.size()==0) return;
if(vc.size()<=2) {
for(int i:vc) {
int tt=dream(p[0],p[1],i);
as[i]=tt-as[p[0]]-as[p[1]];
}
return;
}
int n=vc.size();
vi A,B,C,D,T(n/3);
for(int i=0;i<n/3;i++) {
int tt=dream(vc[i*3],vc[i*3+1],vc[i*3+2]);
if(!tt) {
for(int j=i*3;j<i*3+3;j++) as[vc[j]]=0;
} else if(tt==3) {
for(int j=i*3;j<i*3+3;j++) as[vc[j]]=1;
} else if(tt==1) A.pb(vc[i*3]),B.pb(vc[i*3+1]),C.pb(vc[i*3+2]);
T[i]=tt;
}
for(int i=n/3*3;i<n;i++) D.pb(vc[i]);
sol(D);
sol(A);
vi nb,nc;
for(int i=0;i<A.size();i++) {
if(as[A[i]]==1) as[B[i]]=as[C[i]]=0;
else nb.pb(B[i]),nc.pb(C[i]);
}
sol(nb);
for(int i=0;i<nb.size();i++) as[nc[i]]=1-as[nb[i]];
A.clear(),B.clear(),C.clear(),nb.clear(),nc.clear();
for(int i=0;i<n/3;i++) if(T[i]==2) A.pb(vc[i*3]),B.pb(vc[i*3+1]),C.pb(vc[i*3+2]);
sol(A);
for(int i=0;i<A.size();i++) {
if(as[A[i]]==0) as[B[i]]=as[C[i]]=1;
else nb.pb(B[i]),nc.pb(C[i]);
}
sol(nb);
for(int i=0;i<nb.size();i++) as[nc[i]]=1-as[nb[i]];
}
vector<bool> solve(int n) {
for(int i=0;i<n;i++) p[i]=i;
as.resize(n);
shuffle(p,p+n,rnd);
vi vc,V={p[0],p[1],p[2],p[3]};
for(int i=4;i<n;i++) vc.pb(p[i]);
soln(V);
// wr(as[1],"\n");
sol(vc);
return as;
}
#ifdef test
void QwQ() {
int n=810000;
for(int i=0;i<n;i++) a[i]=rnd()&1;
vector<bool> as=solve(n);
// for(int i=0;i<n;i++) wr(a[i]," "); puts("");
// for(int i=0;i<n;i++) wr(as[i]," ");
for(int i=0;i<n;i++) if(as[i]!=a[i]) return puts("WA"),void();
puts("OK");
wr(C,"\n");
}
bool Med;
signed main() {
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
// fprintf(stderr,"%.2fMB\n",abs(&Med-&Mbg)/1024./1024);
int T=1; while(T--) QwQ();
}
#endif
/*
4
1 1 0 0
8
1 1 1 0 1 0 0 1
12
1 0 1 0 0 0 0 1 1 0 1 1
*/
```