IOI2018 组合动作

UOJ

首先显然可以两次试出首字母

考虑增量构造

假设首字母为A,且已经试出前i个字母得到的串s

我们考虑press这样一个串s+BB+s+BX+s+BY+s+XA

首先这个串长不超过4N

其次由于首字母不重,返回的ans只会等于i+2,i+1,i三者中的一个

如果是i+2,那么显然可以确定第i+1个字母为B,因为XA一定不会产生2的贡献(A是首字母)

如果是i+1,那么第i+1个字母一定是X

如果是i,那么第i+1个字母一定是Y

剩下首字母为B,X,Y的情况类似构造

我们一直使用上述方法试到第n-1个

最后再两次试出最后一个字母即可

这样的总次数是2+(n-2)+2=n+2次

下面是提交代码:

#include<bits/stdc++.h>

#include "combo.h"

using namespace std;

string f[7],ans;

void getf(string fir){

	if(fir=="A"){f[0]+="BB";f[1]+="BX";f[2]+="BY";f[3]+="XA";f[4]+="Y";f[5]+="B";f[6]+="X";}

	if(fir=="B"){f[0]+="AA";f[1]+="AX";f[2]+="AY";f[3]+="XB";f[4]+="Y";f[5]+="A";f[6]+="X";}

	if(fir=="X"){f[0]+="AA";f[1]+="AB";f[2]+="AY";f[3]+="BX";f[4]+="Y";f[5]+="A";f[6]+="B";}

	if(fir=="Y"){f[0]+="AA";f[1]+="AB";f[2]+="AX";f[3]+="BY";f[4]+="X";f[5]+="A";f[6]+="B";}

}

void getfir(){

	int sc=press("AB");

	if(sc){

		int x=press("A");

		if(x)ans+='A';

		else ans+='B';

	}

	else{

		int x=press("X");

		if(x)ans+='X';

		else ans+='Y';

	}

}

void getlas(int n){

	int sc=press(ans+f[4]);

	if(sc==n)ans+=f[4];

	else{

		sc=press(ans+f[5]);

		if(sc==n)ans+=f[5];

		else ans+=f[6];

	}

}

string guess_sequence(int n){

	getfir();

	if(n==1)return ans;

	getf(ans);

	for(int i=2;i<=n-1;i++){

		string now="";

		now+=ans+f[0]+ans+f[1]+ans+f[2]+ans+f[3];

		int x=press(now);

		if(x==i+1)ans+=f[0][0];

		if(x==i)ans+=f[3][0];

		if(x==i-1)ans+=f[4];

	}

	getlas(n);

	return ans;

}

给大家提供一个手写的press用于调试

int press(string ss){

	int l=ss.length(),res=0;

	for(int i=0;i<l;i++){

		int js=0;

		for(int j=0,k=i;j<L;j++,k++)

			if(ss[k]==S[j])js++;

			else break;

		res=max(res,js);

	}

//cout<<ss<<' '<<res<<endl;

	return res;

}