自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:08:11，当前版本为作者最后更新于2025-02-15 00:32:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定 $n$ 个字符，字符集 $\texttt{R,S,T}$，每次可以选出若干个字符（可重复）并询问：

• 如果询问的字符中有 $\texttt T$，那么会返回 $\texttt S$ 的个数。
• 否则会返回询问字符的个数。

在 $150$ 次询问内确定每个字符的种类，每次询问至多选 $300$ 个字符。

交互器不是自适应的。

数据范围：$n\le 300$，$\texttt T$ 的个数 $t\le 30$。

思路分析

由于交互库不自适应，因此可以随机重排整个序列。

首先 $2n$ 次询问是简单的，询问每个单点得到所有 $\texttt T$，然后每个不为 $\texttt T$ 的字符和 $\texttt T$ 一起询问就能确定是 $\texttt S$ 还是 $\texttt T$。

然后可以优化，由于可以加入重复元素，因此可以用二进制一次性询问多个字符：

• 选出若干个非 $\texttt T$ 字符，对于第 $i$ 个字符选择 $2^{i-1}$ 次，再加上一个 $\texttt T$，得到的结果里二进制为 $1$ 的位对应的字符是 $\texttt S$，否则对应的字符是 $\texttt R$。

由于 $2^8-1<300$，因此一次可以解决 $8$ 个字符，可以做到 $n+n/8$ 次操作。

如果用二分确定每个 $\texttt T$，操作次数 $8t+n/8$。

直接二分未必优秀，可以先套一层分块。

我们 $8$ 个元素分一块，每块先询问一次，如果有 $\texttt T$ 再二分。

此时询问次数不超过 $n/8+3t+n/8$，我们再在这上面进行一些常数优化。

首先首轮分块我们只询问 $8$ 个元素，那么可以用刚刚的二进制做法，如果块中有 $\texttt T$，那么就能确定这个块里所有的 $\texttt S$。

对于每个有 $\texttt T$ 的块，求出最左边的 $\texttt T$，然后右边剩余的元素全部放入集合 $Q$ 中，这些元素字符集为 $\{\texttt R,\texttt T\}$。

然后每次取出 $Q$ 的前 $8$ 个元素，先判定是否有 $\texttt T$ 再二分，把剩下的元素放回 $Q$。

然后对于首次二分中没有 $\texttt T$ 的块，我们在后续的判定与二分过程中，取出 $8$ 个元素然后用用二进制做法，如果这次判定中有 $\texttt T$ 字符，那么这 $8$ 个元素也能被确定。

那么这些没有 $\texttt T$ 的块期望上来说肯定在求 $\texttt T$ 的块的过程中就会被确定。

其次在随机的过程中，如果第一个 $\texttt T$ 的位置比较大，那么被插入 $Q$ 的元素期望并不多。

不妨把询问次数近似看成 $n/8+3t+|Q|/8$，而 $|Q|$ 不妨看作 $t$ 个 $[0,7]$ 的随机变量之和。

如果每个变量都是均匀随机的用一个简单的 dp 能算出询问次数 $\le 146$ 的概率已经超过 $99.9\%$。

如果粗略地考虑每个变量在 $[0,7]$ 上的分布，则询问次数 $\le 147$ 的概率超过 $99.5\%$，$\le 148$ 的概率超过 $99.9\%$。

时间复杂度 $\mathcal O(n^2)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
int query_sample(vector<int>s);
void answer_type(int x,char c);
mt19937 rnd(time(0));
typedef vector<int> vi;
int sz(vi x) { return x.size(); }
void operator +=(vi &x,vi y) { for(int i:y) x.push_back(i); }
vi I(vi x,int l,int r) { return vi(x.begin()+l,x.begin()+r); }
void pop(vi &x,int m) { x.erase(x.begin(),x.begin()+m); }
char st[305];
void determine_type(int n) {
	vi A; for(int i=1;i<=n;++i) A.push_back(i),st[i]=0;
	shuffle(A.begin(),A.end(),rnd);
	vi R,S,T,RS,RT; vector <vi> G;
	while(A.size()) {
		int m=min(sz(A),8);
		vi q,u;
		for(int i=0;i<m;++i) for(int j=0;j<(1<<i);++j) q.push_back(A[i]);
		int z=query_sample(q);
		if(z==sz(q)) RS+=I(A,0,m);
		else for(int i=0;i<m;++i) {
			if(z>>i&1) st[A[i]]='S';
			else u.push_back(A[i]);
		}
		if(u.size()) G.push_back(u);
		pop(A,m);
	}
	auto chk=[&](vi q) {
		int m=min(sz(RS),8);
		for(int i=0;i<m;++i) for(int j=0;j<(1<<i);++j) q.push_back(RS[i]);
		int z=query_sample(q);
		if(z==sz(q)) return false;
		for(int i=0;i<m;++i) st[RS[i]]="RS"[z>>i&1];
		pop(RS,m);
		return true;
	};
	auto sol=[&](vi q) {
		shuffle(q.begin(),q.end(),rnd);
		int l=0,r=sz(q)-1;
		while(l<r) {
			int mid=(l+r)>>1;
			if(chk(I(q,l,mid+1))) r=mid;
			else l=mid+1;
		}
		for(int i=0;i<=l;++i) st[q[i]]="RT"[i==l];
		return I(q,l+1,sz(q));
	};
	for(auto it:G) RT+=sol(it);
	while(RT.size()) {
		int m=min(sz(RT),8);
		auto it=I(RT,0,m); pop(RT,m);
		if(!chk(it)) for(int i:it) st[i]='R';
		else RT+=sol(it);
	}
	int _=find(st+1,st+n+1,'T')-st;
	while(RS.size()) chk({_});
	for(int i=1;i<=n;++i) answer_type(i,st[i]);
}