Solution

前面两个 Sub 是容易的。后面要敢于想随机化（我就觉得可以确定性构造，然后做不出来）。

Sub1

显然可以分配二进制数，第 $i$ 次询问把第 $i$ 位是 $1$ 的扔进去。

最后查一下就得到了。

Sub2

建立线段树，然后从上往下查，叶子就得到了。

其实 $H$ 还可以进一步减小到 $10$，考虑没分开的时候一起问，分开之后双线程。

Sub3

会做 Sub4 就不用做这个了。

我有一个很坏的做法，首先考虑找到两个集合的划分把两个主席分开，然后分别套用 Sub1。

这里对第 $i$ 位为 $0,1$ 都问一下，如果某一位两边返回真，就直接切开，否则就认为他们重合。

切开之后套用 Sub1，发现其实他们的编号异或已经知道了，然后用一个答案算出另一个答案。

Sub4

要敢于随机化！

观察 QOJ 提交记录，全都是打表，观察官方 solution，也打了表，发现锣鼓没有题解。于是考虑随机化。

经典技巧把询问建立比特位，现在有 $n=1000$ 个长为 $B=26$ 的二进制串，要求他们或起来两两不同。

不会确定性构造。

考虑如果有 $(i\ \text{or}\ j)=(j\ \text{or}\ k)$ 不合法了，对于一位，有这些情况 $010,011,110,111,101,000$，如果这一位有 $p$ 的概率是 $1$，就是 $\frac{p^3+p(1-p)^2+3p^2(1-p)+(1-p)^3}{8}$ 的概率

#include<bits/stdc++.h>
using namespace std;

int main(){
    double mn=2,pp=-1;
    for(double p=0;p<=1;p+=0.000001){
        double res;
        printf("%lf %lf\n",p,res=pow(p,3)+p*pow(1-p,2)+3*pow(p,2)*(1-p)+pow(1-p,3));
        if(res<mn){
            mn=res,pp=p;
        }
    }   
    printf("G %lf %lf\n",mn,pp);
}

三次函数最值的无脑求法，得到最优概率是 $P=0.703704$，对应 $p=0.333333$。

那么整个串就有 $1-P^{26}$ 的概率不同，是大约 $0.99989429$。

一共有 $\binom{n}{3}$ 对 $(i,j,k)$，全对的概率是接近 $0$，但是别急，可以手动剪枝。

我们会什么？贪心，A*，爬山，退火，最优化优先搜索，Beam Search？都可以借鉴思路。

#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (unsigned long long)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}

bitset<100000000> vis;
int main(){
    vector<int> ans;
    int T=1000000;
    while(T--){
        int mask=0;
        for(int i=0;i<26;++i)if(RRand(0,2)==0)mask|=1<<i;
        bool ok=!vis[mask];
        for(int x:ans)ok&=!vis[mask|x];
        if(ok){
            for(int x:ans)vis.set(mask|x);
            vis.set(mask);
            ans.emplace_back(mask);
        }
    }
    printf("sz %d\n",ans.size());
    printf("S %d\n",vis.count());
    return 0;
}

这里只跑出来 $300$ 左右的解，非常不好。

#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (unsigned long long)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}

bitset<100000000> vis;
struct DS{
vector<int> a;
void del(int id){
    for(int i=0;i<a.size();++i)if(i!=id)vis.reset(a[id]|a[i]);
    vis.reset(a[id]);
    for(int i=id+1;i<a.size();++i)a[i-1]=a[i];
    a.pop_back();
}
bool insert(int x){
    if(vis[x])return 0;
    vis.set(x);
    for(int i=0;i<a.size();++i){
        if(vis[x|a[i]]){
            for(int j=0;j<i;++j)vis.reset(x|a[j]);
            vis.reset(x);
            return 0;
        }
        vis.set(x|a[i]);
    }
    a.emplace_back(x);
    return 1;
//     for(int i=static_cast<int>(a.size())-2;i>=0;--i)
//         if(a[i+1]<a[i])swap(a[i],a[i+1]);
}
void keep(){
    vector<int> b;
    for(int i=0;i<a.size();++i)if(RRand(0,1)==0)b.emplace_back(i);
    reverse(b.begin(),b.end());
    for(auto x:b)del(x);
}
int size(){
    return a.size();
}
bool check(){
    vis.reset();
    for(int i=0;i<a.size();++i)
        for(int j=i;j<a.size();++j){
            // printf("or %d %d %d %d\n",i,j,a[i]|a[j],(int)vis[a[i]|a[j]]);
            if(vis[a[i]|a[j]])return 0;
            else vis[a[i]|a[j]]=1;
        }
    return 1;
}
}ans,bestans;
void SA(){
    ans.keep();
    double T=0.3;
    while(T>1e-6){
        int mask;
        mask=0;
        for(int i=0;i<26;++i)if(RRand(0,2)==0)mask|=1<<i;
        if(ans.insert(mask)){
        }else{
            if(RRand(0,1e8)<=1e8*T&&ans.size()>0){
                ans.del(RRand(0,ans.size()-1));
            }
        }
        T*=0.99993;
        if(ans.a.size()>bestans.a.size()){
            bestans=ans;
        }
    }
}
int main(){
    for(int i=1;i<=12;++i)SA();
    printf("sz %d\n",bestans.a.size());
    printf("sz %d\n",ans.a.size());
    printf("S %d\n",vis.count());
    cout<<ans.check()<<endl;
    return 0;
}

加了最朴素的退火，还多次枚举加入的数，测试得到了 $609$。

有一个很厉害的想法，相比于直接随机，取 $popcount\in [7,10]$ 的数其实也差不多。

ans.a.clear();
vis.reset();
int cnt=0;
for(int T=1;T<=3;++T)
for(int i=0;i<1<<26;++i){
    int popc=__builtin_popcount(i);
    if(popc>=8&&popc<=10){
        cnt++;
        if(ans.insert(i)){
            if(RRand(0,99)==0)ans.del(ans.size()-1);
        }
    }
}
printf("cnt %d\n",cnt);
printf("sz %d\n",bestans.a.size());
printf("sz %d\n",ans.a.size());
printf("S %d\n",vis.count());
cout<<ans.check()<<endl;
return 0;

这下退化到 190 个了，非常不好，也不展开了，这个思路不能继续。

怎么办呢，注意到我们的时间很多，调一下退火的参数，并且让它跑足够久。

搞出来 $716$ 的解。

但是跑了很久就卡在 $700$ 左右，然后退而求其次，发现这个退火其实很能做 $R=28$ 的情况，得到很多分。

接着考虑只保留 $popcount=8$ 的二进制表示，因为如果他们相互包含就会有很多不合法的情况。

#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (unsigned long long)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}

const int B=27;
bitset<400000000> vis;
struct DS{
vector<int> a;
void del(int id){
    for(int i=0;i<a.size();++i)if(i!=id)vis.reset(a[id]|a[i]);
    vis.reset(a[id]);
    for(int i=id+1;i<a.size();++i)a[i-1]=a[i];
    a.pop_back();
}
bool insert(int x){
    if(vis[x])return 0;
    vis.set(x);
    for(int i=0;i<a.size();++i){
        if(vis[x|a[i]]){
            for(int j=0;j<i;++j)vis.reset(x|a[j]);
            vis.reset(x);
            return 0;
        }
        vis.set(x|a[i]);
    }
    a.emplace_back(x);
    return 1;
}
void keep(){
    vector<int> b;
    for(int i=0;i<a.size();++i)if(RRand(0,100)==0)b.emplace_back(i);
    reverse(b.begin(),b.end());
    for(auto x:b)del(x);
}
int size(){
    return a.size();
}
bool check(){
    vis.reset();
    for(int i=0;i<a.size();++i)
        for(int j=i;j<a.size();++j){
            // printf("or %d %d %d %d\n",i,j,a[i]|a[j],(int)vis[a[i]|a[j]]);
            if(vis[a[i]|a[j]])return 0;
            else vis[a[i]|a[j]]=1;
        }
    return 1;
}
}ans,bestans;
void SA(){
    ans.keep();
    long double T=0.1;
    while(T>1e-8){
        int mask;
        do{
            mask=0;
            for(int i=0;i<B;++i)if(RRand(0,2)==0)mask|=1<<i;
        }while(__builtin_popcount(mask)!=8);
        if(ans.insert(mask)){
        }else{
            if(RRand(0,1e8)<=1e8*T&&ans.size()>0){
                ans.del(RRand(0,ans.size()-1));
            }
        }
        T*=0.999991;
        if(ans.a.size()>bestans.a.size()){
            bestans=ans;
        }
        // cerr<<"T "<<T<<endl;
    }
}
int main(){
    for(int i=1;i<=3;++i)SA();
    printf("sz %d\n",bestans.a.size());
    printf("sz %d\n",ans.a.size());
    printf("S %d\n",vis.count());
    cout<<bestans.check()<<endl;
    for(auto x:bestans.a){
        printf("%d,",x);
    }puts("");
    cerr<<(double)clock()/CLOCKS_PER_SEC*1000<<endl;
    return 0;
}

这下就能有 $n=1000,R=27$ 的情况了。

但是我的代码最多也就能跑出来 $864$ 了，真不知道那组数据怎么造的。

Sub4

抄写官方题解：

考虑对 Sub3 的精巧优化：对于 $i,j$ 一共 $\binom{10}{2}$ 对，把这个数值相同的数拿出来问一下，就可以直接完成第二部分的询问，知道不确定的位之间的关系，会用 $20+\binom{10}{2}=65$ 个。

然后可以用 3 作为底数，这里就只有 $21+\binom{7}{2}=40$ 个。

还有另类做法，如果有一个 $N,R$ 的做法，可以拓展到 $N^2,3R$，把 $N^2$ 个数排成方阵，然后对行列做这个子问题，然后还有每个斜线，这样可以唯一确定那两个人的位置，从 $N=R=6$ 开始可以得到次数 $54$ 的做法。

#include "avoid.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> range(int l,int r){
    vector<int> res;
    for(int i=l;i<=r;++i)res.emplace_back(i);
    return res;
}
void solve1(int l,int r,int &ans){
    if(l==r){
        ans=l;
    }else{
        int mid=l+r>>1;
        send(range(l,mid));
        if(wait()[0])solve1(l,mid,ans);
        else solve1(mid+1,r,ans);
    }
}
void solve2(int l,int r,int &ans1,int &ans2){
    if(l==r){
        ans1=ans2=l;
    }else{
        int mid=l+r>>1;
        send(range(l,mid));
        int res0=wait()[0];
        send(range(mid+1,r));
        int res1=wait()[0];
        if(res0&&res1){
            solve1(l,mid,ans1);
            solve1(mid+1,r,ans2);
        }else if(res0){
            solve2(l,mid,ans1,ans2);
        }else{
            solve2(mid+1,r,ans1,ans2);
        }
    }
}
int Solve1(int l,int r,int K,int fl=0){
    for(int i=0;i<=K;++i){
        vector<int> tmp;
        for(int j=l;j<=r;++j)if((j-l)>>i&1)tmp.emplace_back(j);
        send(tmp);
    }
    if(fl)return -1;
    vector<int> res=wait();
    int ans=l;
    for(int i=0;i<=K;++i)if(res[i])ans+=1<<i;
    return ans;
}
int plan[2000]={255,1823,2919,3499,3795,5037,5491,6493,7062,9139,9581,10813,11209,11669,13455,16033,17358,17912,19130,21110,22059,22727,26309,27762,28955,31116,33749,34278,35290,36457,37467,38967,42819,45285,45358,48153,50579,52302,53705,54332,61064,67182,67902,70364,72870,75444,77945,79298,79621,82263,83102,84629,88673,89416,92323,99501,102154,104554,107364,111250,121604,122895,132725,134797,135907,137848,138315,139708,140890,148329,148901,149972,153898,155703,159520,161873,166706,169304,174250,179072,185105,187584,193542,197616,202921,205191,209939,210958,221740,229582,232005,241985,246360,263847,264689,267853,268088,270935,276523,278845,281894,282842,291985,295658,297628,302402,304329,311651,312916,321810,324099,330515,332642,339014,346189,349828,360603,369713,376320,379296,386368,394700,396311,406154,406817,418020,430916,445488,450712,475909,479282,509057,526009,529644,531274,531905,532854,536071,537297,541620,543027,547866,550786,551500,561310,563568,569954,574023,581721,582820,590237,592981,599457,610350,621600,625187,627723,641728,656626,669890,674017,688461,689926,694531,723602,724552,729866,757936,788694,793125,795480,797752,806657,820561,860302,866576,923520,926731,33948220,934426,938068,944448,960524,1036800,1051230,1053877,1054534,1056044,1057642,1061560,1067339,1068593,1070800,1073933,1082780,1084070,1091937,1098922,1115335,1118503,1121928,1124784,1134824,1139786,1148466,1153553,1159252,1163564,1180315,1190662,1200206,1206298,1215570,1218712,1222149,1246028,1247345,22433796,1270656,1294355,1311698,1316227,1320588,1321186,1323337,1333385,1340512,1360688,1379369,1403920,1441965,1444641,1475876,1542336,1573857,1583320,1589453,1590610,1614276,1616656,1636356,1639722,1640324,1663004,1706373,1710612,1753640,1788929,1811520,1872902,1902599,1904848,1909284,1966186,2011152,2100444,2102938,2106595,2107471,2110292,2112290,2115378,2120112,2122194,2130235,2136800,2140753,2145540,2151045,2151506,2163433,2166113,2166935,2185241,2196788,2220136,2233398,2238629,2247362,2248988,2252033,2262045,2269424,2285953,2298274,2303114,2311244,2328067,2359751,11583681,2363208,2382348,2396329,2417188,2429003,2432048,2433236,2493602,2499846,2504728,2515473,2556808,2630931,2640011,2640232,2650125,2655020,2657378,2663960,2689606,2720138,2759748,2761257,2806048,2820152,2835216,2861184,2895894,2935812,2957409,3031078,3113040,3150449,3162531,3175444,3184654,3196232,3205264,3214481,3223937,3236385,3310401,3348032,3410482,3425324,3463232,3490562,3539033,3672117,3698818,3772512,3801762,3809860,3933705,3934624,4197605,4199641,4201735,4203244,4203579,4204883,4213529,4216877,4223456,4228901,4233640,4237838,4243670,4252548,4260651,4265872,4278866,4281456,4293655,4302904,4313240,4338214,4343363,4346544,4363397,4368064,16003073,4394288,4397252,4416769,4457081,4460830,4468098,4468789,4471440,4505765,4522214,4557065,4589322,4606050,4641800,4653272,4658336,4720270,4723049,4740868,4743701,4748354,4754305,4754460,4759834,4786852,4788762,4831296,4862028,4883056,4892689,4915395,4932232,5005347,5047340,5067009,5252436,5261732,5280298,5282888,5285025,5310614,5335298,5360136,5375510,5398597,5407170,5508676,5518354,5540240,5570837,5693952,5709956,5771411,5776009,5869573,5900578,6036512,6300045,6305345,6310214,6338578,6362377,6365538,6374932,6423118,6458408,6588931,6598728,6620738,6645888,6656288,6718608,6750221,6836432,6922756,7080212,7094440,7192578,7340408,7361546,7410306,7441412,7475489,7867522,7881264,7939328,8392500,8394696,8399006,8402022,8403184,8405597,8409267,8414545,8421775,8428353,8431146,8440040,8446384,8454634,8464980,8473986,8483976,8487260,8520027,8524181,8533513,8539236,8559649,8573570,8587590,8597784,8603937,8635412,8655899,8657604,8659366,8668097,8686800,8687909,8714272,8725517,8733258,8784409,8791572,8798343,8822888,8881696,8914644,8923433,8923810,8925958,8932365,8951170,8964372,8986695,8996616,9012321,9069104,9117864,9175595,9216656,9244724,9313282,9339272,9459794,9463941,9471761,9473314,9508937,9510963,9523984,9546880,9569482,9581952,9638410,9705510,9741120,9751560,9798168,9802112,9855234,10011792,10029664,10093617,10125446,10231833,10355024,10497290,10505808,10506412,10544140,10553869,10567794,10589252,10621736,10648064,10666246,10718464,10749701,10799121,10835200,11011273,11046986,11141660,11191297,11207716,11545472,11575318,11665764,11796650,11804976,11930116,12075530,12097024,12587659,12610580,12661281,12699264,12701762,12715180,12720402,12750338,12780177,12911754,12918977,13109816,13111692,13168896,13189472,13238295,13385809,13467716,13631789,13648328,13660172,13763843,13781568,13803556,13894211,14493696,14682322,14689048,14713891,14778568,14951042,15213664,15597825,15810692,15958032,16781252,16783266,16789718,16791857,16795865,16798805,16802460,16804998,16813114,16823049,16829217,16831840,16836660,16845454,16852184,16859243,16873992,16877249,16896131,16910787,16921876,16931333,16941159,16965673,16978187,16991904,17025120,17040508,17046184,17049900,17064545,17076688,17080966,17115281,17171810,17182210,17207370,17302859,17310533,17335829,17340549,17371473,17372678,17378562,17433134,17451276,17454224,17490112,17564307,17580744,17582101,17617921,17678376,17832546,17835539,17863205,17896473,17897920,17900582,17924374,17957046,17974720,18032712,18121475,18129940,18155328,18170248,18170388,18244616,18372896,18379280,18383976,18385418,18416141,18489475,18878826,18909577,18926864,18942180,18946640,18956581,18999298,19007518,19010193,19017825,19051648,19112480,19150368,19165252,19205633,19271687,19276176,19400289,19415492,19530562,19661091,19759364,19930370,19968024,20186246,20594706,20710672,20906112,20986018,20997896,21005202,21008476,21017610,21045333,21048096,21105201,21107753,21236884,21240640,21259456,21340172,21405984,21430314,21578769,21692690,21759368,21774854,22020945,22027393,22038563,22118498,22202496,22709760,22839344,23122464,23216139,23284224,23464001,23607297,24117449,24125732,25191171,25216518,25232172,25249818,25256160,25268392,25305229,25329811,25493682,25559664,25628992,25725004,25736208,25756560,25821602,25833508,26103816,26216097,26237568,26626049,26742977,27264297,27301908,27377984,27467793,27549714,27799816,27985984,28860448,29362954,29372441,29581316,29625632,29786752,29885028,29950113,30419976,30475524,31461510,31492192,33561241,33561686,33566308,33569128,33574800,33575334,33579211,33589492,33592589,33600660,33604259,33616396,33621891,33622107,33625649,33634948,33636833,33686937,33699040,33718394,33720597,33725960,33729539,33759817,33768530,33826130,33837164,33859969,33866632,33884866,33890712,33903184,33910793,33915980,33958022,33989153,34015528,34079341,34088220,34105520,34117312,34132368,34148708,34178370,34213939,34227269,34260098,34343082,34362882,34383136,34455572,34494465,34554240,34607166,34612529,34616194,34630916,34646594,34705569,34751109,34771218,34802724,34824288,34906212,34969602,34999361,35009540,35062432,35163400,35164241,35196432,35283208,35520774,35525128,35654060,35668089,35696913,35722268,35736586,35751120,35787460,35791154,35800836,35938466,35983877,36208805,36255232,36340234,36462664,36571680,36706371,36733130,36790290,36880420,36932096,36979778,37232780,37491008,37749399,37753712,37766183,37783128,37798200,37826634,37889320,37949447,38046496,38142785,38292552,38389792,38407312,38559876,38799375,38818340,38855696,38949056,39027968,39110657,39329890,39856324,39873040,39977192,40032256,40113288,40375313,40435762,40632900,40896012,41288064,41551880,41972034,41973280,42074695,42086484,42166274,42205369,42213701,42273888,42370114,42500627,42539272,42558016,42610698,42733762,42796292,42992398,42999297,43067912,43090185,43336705,44047520,44073872,44138552,44241153,44303382,44863489,45228097,46146694,46174726,46188612,46204177,46401676,46415922,47710384,48312336,49283618,49872960,50332109,50358608,50405938,50471182,50508352,50533448,50644128,50858055,50924704,50997281,51052565,51218496,51382680,51400194,51413920,51431436,51454145,51466372,51642968,52479489,52482184,52691228,52764960,52954258,52990000,53035011,53479956,54526310,54731136,54796803,54825220,54837824,54857793,55144448,56099586,56623409,58737256,58742817,58851556,58856976,59025416,59114880,59293705,59507784,59773204,60826760,61933056,62160912,62915651,63456288,63996033,64098312,65569280,57700353,50889123};
pair<int,int> scout(int R,int H){
    if(R==10&&H==1){
        int ans=Solve1(1,1000,9);
        return {ans,ans};
    }else if(R==20&&H==20){
        pair<int,int> ans;
        solve2(1,1000,ans.first,ans.second);
        return ans;
    }else if(R==30&&H==2){
        for(int i=0;i<10;++i){
            vector<int> tmp1,tmp0;
            for(int j=1;j<=1000;++j)
                if(j>>i&1)tmp1.emplace_back(j);
                else tmp0.emplace_back(j);
            send(tmp0),send(tmp1);
        }
        int ans_=0;
        vector<int> res=wait();
        int p=0,q=-1;
        for(int i=0;i<10;++i){
            if(res[2*i]&&res[2*i+1]){
                p+=1<<i;
                q=i;
            }else if(res[2*i+1]){
                ans_+=1<<i;
            }
        }
        if(p==0)return {ans_,ans_};
        int ans1=0,ans2;
        for(int i=0;i<10;++i)if(i!=q){
            vector<int> tmp;
            for(int j=1;j<=1000;++j)if((j>>i&1)&&(~j>>q&1))tmp.emplace_back(j);
            send(tmp);
        }
        res=wait();
        reverse(res.begin(),res.end());
        for(int i=0;i<10;++i)if(i!=q){
            if(res.back())ans1+=1<<i;
            res.pop_back();
        }
        ans2=ans1^p;
        return {ans1,ans2};
    }else{
        for(int i=0;i<26;++i){
            vector<int> tmp;
            for(int j=0;j<1000;++j)if(plan[j]>>i&1)tmp.emplace_back(j+1);
            send(tmp);
        }
        vector<int> res=wait();
        int Res=0;
        for(int i=0;i<26;++i)Res+=res[i]<<i;
        for(int i=0;i<1000;++i)
            for(int j=0;j<1000;++j)
                if((plan[i]|plan[j])==Res)
                    return {i+1,j+1};
        assert(false);
    }
}

Reference

受到下面的启发。

https://www.cnblogs.com/caijianhong/p/19026007

https://www.cnblogs.com/Xun-Xiaoyao/p/18088128

https://www.ceoi2023.de/wp-content/uploads/2023/09/6-avoid-spoiler.pdf

OU