CF1286C2 - Madhouse (Hard version)

题目大意

交互器生成了一个串\(s\)，可以用3次操作，每次

? l r 询问\([l,r]\)内所有连续子串，

交互器返回所有连续子串随机排列（字符位置和串的顺序均随机）的结果

额外要求：查询的总子串个数$\leq \lceil 0.777 (n+1)^2 \rceil $

最后 ! s 输出答案

分析

看一看\(0.777\approx \cfrac{7}{9}\)

于是乎我就写了一个0.75的做法_?

由于思路顺序极为奇怪，所以实现方法也很奇怪

从长到短确定

从\(L=n,n-1,\cdots 1\)依次确定每一种长度的每一个串对应的字符集

假设当前知道\(L+1\)层的样子，可以通过相邻取交确定下一层除了第一个和最后一个的所有串

将他们删掉后，就知道当前头尾字符\(s[n-L+1],s[L]\)是什么

再确定头字符即可

确定头字符

考虑对于一个串，可以用以下方法两次求出整串

1.查询整串\([1,n]\)得到集合\(S\)

2.查询\([2,n]\)得到集合\(T\)

计算\(S-T\)，即得到所有\([1,i]\)串的字符集，依次作差即可

用这个确定前半个串，消耗\((\frac{n}{2})^2\)

结合前面的即可

代码实现比较奇怪

const int N=110,INF=1e9+10;

int n;
struct Node{
	int c[26],n;
	Node(){ memset(c,n=0,sizeof c); }
	Node operator & (const Node __) const {
		Node res;
		rep(i,0,25) res.n+=res.c[i]=min(c[i],__.c[i]);
		return res;
	}
	int operator < (const Node __) const {
		if(n!=__.n) return n<__.n;
		rep(i,0,25) if(c[i]!=__.c[i]) return c[i]<__.c[i];
		return 0;
	}
	int operator == (const Node __) const {
		rep(i,0,25) if(c[i]!=__.c[i]) return 0;
		return 1;
	}
	char operator - (const Node __) const {
		rep(i,0,25) if(c[i]>__.c[i]) return i+'a';
		return -1;
	}
	void Show(){
		cout<<"L="<<n<<' '; rep(i,0,25) rep(j,1,c[i]) putchar(i+'a');
		puts("");
	}
};
Node Read(){
	static char s[N];
	scanf("%s",s);
	Node t;
	for(int i=0;s[i];++i) t.n++,t.c[s[i]-'a']++;
	return t;
}

char s[N];
void Sub1(){
	int m=(n+1)/2;
	multiset <Node> st;
	printf("? %d %d\n",1,m),fflush(stdout);
	rep(i,1,m*(m+1)/2) st.insert(Read());
	if(m>1) {
		printf("? %d %d\n",2,m),fflush(stdout);
		rep(i,1,m*(m-1)/2) st.erase(st.find(Read()));
	}
	Node lst;
	int p=0;
	for(Node i:st) s[++p]=i-lst,lst=i;
}

multiset <Node> st[N];
Node A[N][N];

void Sub2(){
	printf("? %d %d\n",1,n),fflush(stdout);
	rep(i,1,n*(n+1)/2) {
		Node t=Read();
		if(t.n==n) A[1][1]=t;
		else st[t.n].insert(t);
	}
	//rep(i,1,n) {
		//puts("---");
		//for(auto j:st[i]) j.Show();
	//}
	rep(i,1,n/2) {
		//cout<<"$"<<i<<' '<<s[i]<<endl;
		//rep(j,1,i) A[i][j].Show();
		rep(j,1,i-1) {
			A[i][j].c[s[j]-'a']--,A[i][j].n--;
			A[i+1][j+1]=A[i][j];
			//cout<<"Erase: "; A[i+1][j+1].Show();
			//for(auto t:st[n-i]) t.Show();
			assert(st[n-i].find(A[i+1][j+1])!=st[n-i].end());
			st[n-i].erase(st[n-i].find(A[i+1][j+1]));
			A[i][j].c[s[j]-'a']++,A[i][j].n++;
		}
		Node a=*st[n-i].begin();
		Node b=*st[n-i].rbegin();
		Node x=A[i][1],y=A[i][i];
		y.c[s[i]-'a']--;
		s[n-i+1]=x-(a==y?b:a);
		if(a==y) A[i+1][1]=b,A[i+1][i+1]=a;
		else A[i+1][1]=a,A[i+1][i+1]=b;
		//cout<<s[n-i+1]<<endl;
	}
}

int main(){
	n=rd();
	Sub1(),Sub2();
	printf("! ");
	s[n+1]=0,puts(s+1);
	fflush(stdout);
}