C：给n和k要求，找出n个不同的数，使得亦或起来等于k
可以先预处理从1到1e5，找亦或起来等于（11111111111111111）（二进制）的所有对数，然后四个一起亦或就是0了，再和k亦或
可以看出要分四种情况讨论，对于n%4=p的情况，应该找到p-1个不同的数亦或起来等于0，可以小范围的p-1重循环搜索，对于n%4==2&&x==0的情况要注意特判，可以用6重循环，每层不超过10
代码过于复杂了，应该可以简化一下
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; bool vis[N];
int main()
{
// cout<<(0^1^2^4^8^15)<<endl;
ios::sync_with_stdio(false);
cin.tie();
int n,x;
cin>>n>>x;
if(n==&&x==)
{
cout<<"NO"<<endl;
return ;
}
cout<<"YES"<<endl;
vector<int>v1,v2;
for(int i=;i<(<<);i++)
{
int s=;
for(int j=;j<;j++)
{
if(i&(<<j));
else s+=(<<j);
}
// cout<<i<<" "<<s<<endl;
if(!vis[i]&&!vis[s])
{
vis[s]=vis[i]=;
v1.pb(i);
v2.pb(s);
}
}
if(n%==&&x==)
{
set<int>ans;
int a,b,c,d,e,f;
for(int i=;i<;i++)
{
for(int j=i+;j<;j++)
{
for(int k=j+;k<;k++)
{
for(int ii=k+;ii<;ii++)
{
for(int jj=ii+;jj<;jj++)
{
if((i^j^k^ii^jj)!=i&&(i^j^k^ii^jj)!=j
&&(i^j^k^ii^jj)!=k&&(i^j^k^ii^jj)!=ii
&&(i^j^k^ii^jj)!=jj&&(i^j^k^ii^jj)==)
{
ans.insert(i);
ans.insert(j);
ans.insert(k);
ans.insert(ii);
ans.insert(jj);
ans.insert();
a=i,b=j,c=k,d=ii,e=jj,f=;
break;
}
}
if(ans.size()!=)break;
}
if(ans.size()!=)break;
}
if(ans.size()!=)break;
}
if(ans.size()!=)break;
}
int k=;
for(int i=;i<v1.size();i++)
{
if(k>=(n-)/)break;
if(v1[i]==a||v2[i]==a||v1[i]==b||v2[i]==b||
v1[i]==c||v2[i]==c||v1[i]==d||v2[i]==d||
v1[i]==e||v2[i]==e||v1[i]==f||v2[i]==f)continue;
k++;
ans.insert(v1[i]);
ans.insert(v2[i]);
}
for(auto x:ans)
cout<<x<<" ";
cout<<endl;
return ;
}
set<int>ans;
if(n%==)
{
ans.insert(x);
int k=;
for(int i=;i<v1.size();i++)
{
if(k>=(n-)/)break;
if(v1[i]==x||v2[i]==x)continue;
ans.insert(v1[i]);
ans.insert(v2[i]);
k++;
}
}
else if(n%==)
{
int a,b;
for(int i=;i<;i++)
{
// cout<<(x^i)<<" "<<i<<endl;
if((x^i)!=i)
{
// cout<<(x^i)<<" "<<i<<endl;
ans.insert(x^i);
ans.insert(i);
a=x^i;b=i;
break;
}
}
int k=;
for(int i=;i<v1.size();i++)
{
if(k>=(n-)/)break;
if(v1[i]==a||v2[i]==a||v1[i]==b||v2[i]==b)continue;
ans.insert(v1[i]);
ans.insert(v2[i]);
k++;
}
}
else if(n%==)
{
int a,b,c;
for(int i=;i<;i++)
{
for(int j=i+;j<;j++)
{
if((x^i^j)!=i&&(x^i^j)!=j)
{
ans.insert(x^i^j);
ans.insert(i);
ans.insert(j);
a=x^i^j;b=i;c=j;
break;
}
}
if(ans.size()!=)break;
}
int k=;
for(int i=;i<v1.size();i++)
{
if(k>=(n-)/)break;
if(v1[i]==a||v2[i]==a||v1[i]==b||v2[i]==b||v1[i]==c||v2[i]==c)continue;
ans.insert(v1[i]);
ans.insert(v2[i]);
k++;
}
}
else
{
int a,b,c,d;
for(int i=;i<;i++)
{
for(int j=i+;j<;j++)
{
for(int k=j+;k<;k++)
{
if((x^i^j^k)!=i&&(x^i^j^k)!=j&&(x^i^j^k)!=k)
{
ans.insert(x^i^j^k);
ans.insert(i);
ans.insert(j);
ans.insert(k);
a=x^i^j^k;b=i;c=j;d=k;
break;
}
}
if(ans.size()!=)break;
}
if(ans.size()!=)break;
}
int k=;
for(int i=;i<v1.size();i++)
{
if(k>=(n-)/)break;
if(v1[i]==a||v2[i]==a||v1[i]==b||v2[i]==b||v1[i]==c||v2[i]==c||v1[i]==d||v2[i]==d)continue;
ans.insert(v1[i]);
ans.insert(v2[i]);
k++;
}
}
for(auto x : ans)
cout<<x<<" ";
cout<<endl;
return ;
}
/******************** ********************/
C
D：交互题（永远是二分），有一个长度为n的01字符串，先输入n，查询是？+长度为n的01字符串，给出的结果是汉明距离（两个字符串不同的个数），要求在15次内找到一个0一个1
既然能保证有0和1，那么可以找到01串或者10串，用二分对于[m,r)如果有01串，那么l=m，否则r=m
one是1的个数，那么如何判断是否有01串呢，构造一个l到r是1的，其他都是0的字符串，假如l到r中只有0，那么结果就是one+(r-l+1)，如果只有1，那么结果就是one-(r-l+1),这样有01就是one-(r-l+1)<k<one+(r-l+1)
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; void debug(){cout<<-<<endl;} int n,one;
bool ok(int l,int r)
{
string s=string(n,'');
for(int i=l;i<=r;i++)
s[i]='';
cout<<"? "<<s<<endl;
cout.flush();
int a;
cin>>a;
return one-(r-l+)<a&&a<one+(r-l+);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cin>>n;
cout<<"? "<<string(n,'')<<endl;
cout.flush();
cin>>one;
int l=,r=n-;
while(l<r-)
{
int m=(l+r)/;
if(ok(m,r))l=m;
else r=m;
}
string s=string(n,'');
s[l]='';
cout<<"? "<<s<<endl;
cout.flush();
int a;
cin>>a;
if(a==one+)cout<<"! "<<l+<<" "<<l+<<endl;
else cout<<"! "<<l+<<" "<<l+<<endl;
cout.flush();
return ;
}
/********************
0011001100
********************/
D