自动搬运

查看原文

来自洛谷，原作者为

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

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

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

以下是正文

Problem Link

题目大意

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

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

思路分析

非常非常感谢

首先考虑如何维护答案，求出每个 $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;
}