[xsy3553]游戏

题意：交互题，交互库有长为$n$的$01$串$S$，你可以用字符串$T$询问$\sum\limits_{i=1}^n[S_i=T_i]$，要求用$1030$次询问问出$S$，$n=5000$

首先我们可以问出一个集合内有多少个$1$，接下来的询问就是指问集合内$1$的个数，记集合$S$的答案为$ans_S$

我们硬点一个方案的最后一次询问是问总共有多少$1$

如果可以用$k$次询问问出长为$n$的串，那么可以用$2k$次询问问出长为$2n+k-1$的串，构造如下

把串分成三部分：$1\cdots n,n+1\cdots 2n,2n+1\cdots 2n+k-1$，记为$A,B,C$

设对$A$询问的集合为$P_{1\cdots k}$，对$B$询问的集合为$Q_{1\cdots k}$

对$i=1\cdots k-1$，问$P_i\bigcup Q_i$和$(A-P_i)\bigcup Q_i\bigcup\{C_i\}$，倒数第二次问$A$

两个询问结果之和是$ans_A+2ans_{Q_i}+C_i$，和$ans_A$比较奇偶性可以知道$C_i$，继而推出$ans_{Q_i},ans_{P_i}$，做完之后也自然知道了$ans_{Q_k}$，于是递归下去做就行了

当$n=5000$时，这个做法需要$1024$次询问

感觉这个题很巧妙啊？

#include"game.h"
#include<string.h>
#include<vector>
using namespace std;
typedef vector<int> vi;
int n;
string t;
int sum;
int get(vi v){
	int siz;
	t=string(n,'1');
	siz=0;
	for(int x:v){
		if(x>n)break;
		t[x-1]='0';
		siz++;
	}
	return(siz-guess(t)+sum)/2;
}
vi al(int n){
	vi v;
	for(int i=1;i<=n;i++)v.push_back(i);
	return v;
}
vi sh(vi a,int b){
	for(int&x:a)x+=b;
	return a;
}
bool us[6010];
vi inv(vi a,int n){
	vi c;
	memset(us,0,n+1);
	for(int x:a)us[x]=1;
	for(int i=1;i<=n;i++){
		if(!us[i])c.push_back(i);
	}
	return c;
}
vi operator+(vi a,vi b){
	a.insert(a.end(),b.begin(),b.end());
	return a;
}
struct sol{
	int n;
	vector<vi>a;
	void add(vi v){
		a.push_back(v);
	}
}w[20];
void pre(){
	int n,k,i,j;
	vi t;
	w[1]={2,{{1},{1,2}}};
	for(i=2;i<=10;i++){
		k=w[i-1].a.size();
		n=w[i-1].n;
		w[i].n=n*2+k-1;
		for(j=0;j<k-1;j++){
			vi&u=w[i-1].a[j];
			w[i].add(u+sh(u,n));
			t=inv(u,n)+sh(u,n);
			t.push_back(n*2+j+1);
			w[i].add(t);
		}
		w[i].add(al(n));
		w[i].add(al(w[i].n));
	}
}
int res[6010];
void solve(int sh,int id,vi r){
	if(id==1){
		res[sh+1]=r[0];
		res[sh+2]=r[1]-r[0];
		return;
	}
	int n,k,i,c,t,al;
	vi ra,rb;
	n=w[id-1].n;
	k=w[id-1].a.size();
	c=r[k*2-2];
	al=r[k*2-1]-c;
	for(i=0;i<k-1;i++){
		t=res[sh+n*2+i+1]=((r[i*2]+r[i*2+1])^c)&1;
		al-=t;
		rb.push_back(t=(r[i*2]+r[i*2+1]-t-c)/2);
		ra.push_back(r[i*2]-t);
	}
	ra.push_back(c);
	rb.push_back(al);
	solve(sh,id-1,ra);
	solve(sh+n,id-1,rb);
}
const int mx=10;
string game(int _n,int k){
	n=_n;
	vi r;
	string s(n,'1');
	pre();
	sum=guess(s);
	for(vi v:w[mx].a)r.push_back(get(v));
	solve(0,mx,r);
	for(int i=0;i<n;i++)s[i]=res[i+1]+'0';
	return s;
}

巴特西

[xsy3553]游戏

最新文章

热门文章