P11537 题解

· · 题解

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。

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

由于 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]);
}