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="< 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  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<<"$"<