P11083 题解

· · 题解

Problem Link

题目大意

交互器中有一个 x\in[1,n]，每次询问 k 可以得到 [x\ge k]，但交互器会撒至多一次谎，构造最优策略。

数据范围：n\le 3\times 10^4。

思路分析

非常非常感谢 @zhouhuanyi 大佬的指导。

首先考虑如何维护答案，求出每个 x 违反了几个询问 a_x，那么一次询问相当于给 a[1,x-1]/a[x,n] 全体加一。

我们的目标就是让 a_x\le 1 的元素唯一。

很显然 a_x\ge 2 的元素此后完全不会被考虑，那么我们只要取出 a_x\in\{0,1\} 的子序列，容易发现这个子序列的形式一定是 111000111。

那么设 dp_{i,j,k} 表示当前 a 为 i 个 1，j 个 0，k 个 1 拼接时的答案，转移时直接枚举询问 p 在哪个地方，复杂度 \mathcal O(n^4)。

注意到 dp 值域很小，因此 f_{c,i,j} 表示 \max\{k\mid dp_{i,j,k}\le c\}，只需要分讨 p 属于哪个段，可以直接做到 \mathcal O(1) 转移。

时间复杂度 \mathcal O(n^2\log n)，可以处理 n\le 5000 的情况。

然后直接暴力打表记决策点，注意到本地静态空间无法超过 2G，因此用 std::vector 在代码里申请就能开得下。

我们并不需要记录所有决策点，首先 i+j+k\le 5000 的部分可以预处理。

并且已知 17 次操作最多处理 n=6444，那么如果 n<6444，那么直接补成 n=6444 也能在 17 次操作内求出答案。

那么我们只要打表出 n=6444,12286,23464,30000 处的所有决策点即可，Code Link。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5000,M=17,MAXN=3e4+5,inf=1e9;
inline void chkmin(int &x,const int &y) { x=y<x?y:x; }
inline void chkmax(short &x,const short &y) { x=y>x?y:x; }
short f[M+1][N+5][N+5]; int lg[MAXN+5],up[M+1];
array <int,4> str[]={ /*all possible transition pos*/ };
void init(int n) {
    for(int c=0;c<=M;++c) up[c]=min(1<<c,n);
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=1,f[0][0][1]=f[0][1][0]=0;
    for(int c=0;c<=M;++c) {
        for(int i=up[c];i>=0;--i) for(int j=up[c]-i;j>=0;--j) {
            chkmax(f[c][i][j],f[c][i+1][j]),chkmax(f[c][i][j],f[c][i][j+1]);
        }
        if(c==M) return ;
        for(int i=0;i<=up[c];++i) for(int j=0;i+j<=up[c];++j) if(f[c][i][j]>=0) {
            if(f[c][j][i]>=0) chkmax(f[c+1][min(up[c+1]-i-j,(int)f[c][j][i])][i+j],f[c][i][j]); //split j
            if(j<=(1<<c)) {
                chkmax(f[c+1][min(up[c+1]-j,(1<<c)-j+i)][j],f[c][i][j]); //split i
                chkmax(f[c+1][i][j],f[c][i][j]+(1<<c)-j); //split k
            }
        }
    }
}
int dp(int i,int j,int k) {
    if(i<=N&&j<=N) for(int c=0;c<=M;++c) if(f[c][i][j]>=k) return c;
    return M+1;
}
int trs(int i,int j,int k) {
    if(!j) return (i+k)/2;
    if(i+j+k>N) {
        for(auto it:str) if(it[0]==i&&it[1]==j&&it[2]==k) return it[3];
        return -1;
    }
    int vl=dp(i,j,k)-1;
    for(int p=1;p<=i;++p) if(vl==max(dp(i-p,j,k),lg[p+j])) return p;
    for(int p=1;p<j;++p) if(vl==max(dp(p,j-p,k),dp(i,p,j-p))) return i+p;
    for(int p=0;p<k;++p) if(vl==max(lg[j+k-p],dp(i,j,p))) return i+j+p;
    return -1;
}
int o,st[MAXN],m,a[MAXN];
bool qry(int x) {
    if(x>o) return 0;
    cout<<"? "<<x<<endl; string _; cin>>_; return _=="Yes";
}
void solve(int n) {
    m=0;
    for(int i=1;i<=n;++i) st[++m]=i,a[i]=0;
    while(m>1) {
        int l=m,r=0;
        for(int i=1;i<=m;++i) if(a[st[i]]==0) l=min(l,i),r=max(r,i);
        int p=(l>r?m/2:trs(l-1,r-l+1,m-r))+1;
        bool fl=qry(st[p]);
        if(fl) for(int i=1;i<p;++i) ++a[st[i]];
        else for(int i=p;i<=m;++i) ++a[st[i]];
        int k=0;
        for(int i=1;i<=m;++i) if(a[st[i]]<=1) st[++k]=st[i];
        m=k;
    }
    cout<<"! "<<st[m]<<endl;
}
const int LIM[]={30000,23464,12286,6444};
signed main() {
    for(int i=1;i<MAXN;++i) lg[i]=__lg(i-1)+1;
    cin>>o;
    init(min(N,o));
    int n=3e4;
    for(int p:LIM) if(o<=p) n=p;
    if(o<=N) n=o;
    while(true) {
        solve(n);
        string _; cin>>_; if(_=="Done") break;
    }
    return 0;
}