居然是大苹果带出来的兵？直接 biu 了

· · 题解

感觉不像人类了（尽管场了），第一次写三个递归函数嵌套，这不比 cake 难？

如果想让你期望步数增多，那么 0 和 1 出现的概率分别为 50\%，如下分析只考虑这种最坏情况。

先把整个序列 shuffle 一下，再三个三个分组：每次如果结果为 0 或 3 ，那么肯定是全 0 或全 1，然后分为和为 1 的三元组序列与和为 2 的三元组序列两部分：

分析一下期望：设对于一个长度为 n 的二元组序列期望需要进行的查询数为 f(n)，对于一个长度为 n 的三元组序列期望需要进行的查询数为 g(n)，那么答案为 f(n)，且有：

\begin{cases} f(n)=g(\frac{n}{4})+\frac{n}{3}\\ g(n)=f(\frac{2n}{3})+g(\frac{2n}{9})+\frac{n}{3} \end{cases}

可得 f(n)=\frac{37n}{66}，f(810000)\approx454091，可以通过本题。

实现时由于递归出来的序列长度不总是 3 的倍数，最终次数会稍大一些。

代码：

#include<bits/stdc++.h>
using namespace std;
int dream(int x,int y,int z);
vector<bool>ans;
int c0,c1;mt19937 rnd(time(NULL));
struct node2{int x,y;};
struct node3{int x,y,z;};
inline void solve2(vector<node2>v);
inline void solve30(vector<node3>v);
inline void solve31(vector<node3>v);
inline void solve2(vector<node2>v){
    if(v.empty())return;
    int n=v.size()%3;
    for(int i=0;i<n;++i)ans[v[i].x]=dream(c0,c1,v[i].x)-ans[c0]-ans[c1];
    vector<node3>v0,v1;
    for(int i=n;i<(int)v.size();i+=3){
        auto a0=v[i],a1=v[i+1],a2=v[i+2];
        int x=dream(a0.x,a1.x,a2.x);
        if(x==0)ans[a0.x]=0,ans[a1.x]=0,ans[a2.x]=0;
        else if(x==3)ans[a0.x]=1,ans[a1.x]=1,ans[a2.x]=1;
        else if(x==1)v0.emplace_back(node3{a0.x,a1.x,a2.x});
        else if(x==2)v1.emplace_back(node3{a0.x,a1.x,a2.x});
    }solve30(v0),solve31(v1);
    for(auto it:v)ans[it.y]=ans[it.x]^1;
}
inline void solve30(vector<node3>v){
    if(v.empty())return;
    int n=v.size()%3;
    vector<node2>v2;vector<node3>v0,v1;
    for(int i=0;i<n;++i){
        ans[v[i].x]=dream(c0,c1,v[i].x)-ans[c0]-ans[c1];
    }
    for(int i=n;i<(int)v.size();i+=3){
        auto a0=v[i],a1=v[i+1],a2=v[i+2];
        int x=dream(a0.x,a1.x,a2.x);
        if(x==0)ans[a0.x]=0,ans[a1.x]=0,ans[a2.x]=0;
        else if(x==3)ans[a0.x]=1,ans[a1.x]=1,ans[a2.x]=1;
        else if(x==1)v0.emplace_back(node3{a0.x,a1.x,a2.x});
        else if(x==2)v1.emplace_back(node3{a0.x,a1.x,a2.x});
    }solve30(v0),solve31(v1);
    for(auto it:v){
        if(ans[it.x]==1)ans[it.y]=ans[it.z]=0;
        else v2.emplace_back(node2{it.y,it.z});
    }solve2(v2);
}
inline void solve31(vector<node3>v){
    if(v.empty())return;
    int n=v.size()%3;
    vector<node2>v2;vector<node3>v0,v1;
    for(int i=0;i<n;++i){
        ans[v[i].x]=dream(c0,c1,v[i].x)-ans[c0]-ans[c1];
    }
    for(int i=n;i<(int)v.size();i+=3){
        auto a0=v[i],a1=v[i+1],a2=v[i+2];
        int x=dream(a0.x,a1.x,a2.x);
        if(x==0)ans[a0.x]=0,ans[a1.x]=0,ans[a2.x]=0;
        else if(x==3)ans[a0.x]=1,ans[a1.x]=1,ans[a2.x]=1;
        else if(x==1)v0.emplace_back(node3{a0.x,a1.x,a2.x});
        else if(x==2)v1.emplace_back(node3{a0.x,a1.x,a2.x});
    }solve30(v0),solve31(v1);
    for(auto it:v){
        if(ans[it.x]==0)ans[it.y]=ans[it.z]=1;
        else v2.emplace_back(node2{it.y,it.z});
    }solve2(v2);
}
std::vector<bool>solve(int n){
    if(n==4){
        int d=dream(0,1,2),c=dream(0,1,3),b=dream(0,2,3),a=dream(1,2,3);
        int s=(d+c+b+a)/3;
        d=s-d,c=s-c,b=s-b,a=s-a;
        ans.push_back(a),ans.push_back(b),ans.push_back(c),ans.push_back(d);
        return ans;
    }ans.resize(n);
    vector<int>p(n);
    iota(p.begin(),p.end(),0);
    shuffle(p.begin(),p.end(),rnd);
    vector<node3>v0,v1;
    v0.clear(),v1.clear();
    for(int i=0;i<n;i+=3){
        int x=dream(p[i],p[i+1],p[i+2]);
        if(x==0)ans[p[i]]=0,ans[p[i+1]]=0,ans[p[i+2]]=0,c0=p[i],c1=p[i+1];
        else if(x==3)ans[p[i]]=1,ans[p[i+1]]=1,ans[p[i+2]]=1,c0=p[i],c1=p[i+1];
        else if(x==1)v0.emplace_back(node3{p[i],p[i+1],p[i+2]});
        else if(x==2)v1.emplace_back(node3{p[i],p[i+1],p[i+2]});
    }solve30(v0),solve31(v1);
    return ans;
}