专栏文章

CF1583D

DDDF_
CF1583D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miny3n1n
此快照首次捕获于
2025/12/02 10:14
3 个月前
此快照最后确认于
2025/12/02 10:14
3 个月前
查看原文

题解

先求出 pnp_{n} 的值。
具体地，先从 11 到 n−1n-1 枚举一个数 xx，询问 a=[1,1,1,⋯ ,1,x+1]a=[1,1,1,\cdots,1,x+1]，此时若返回 00，则 pnp_{n} 已经确定，即 pn=n+1−xp_{n}=n+1-x；若返回其他的 kk，则标记 pk=pn+xp_{k}=p_{n}+x，求出 pnp_{n} 后再将所有被标记的 pkp_{k} 处理为正确的值。
特殊地，若 ∀x∈[1,n−1]\forall x \in [1,n-1]，返回的 kk 均不为 00，则 pn=1p_{n}=1，然后此时所有 pip_{i} 已经被标记，于是就可以在 n−1n-1 步内求出序列。
为什么这样求
根据排列性质，如果 pn+x≤np_{n}+x \le n，则这个值必定在排列中出现过，且整个排列没有重复的元素。因此可以直接询问 a=[0,0,0,⋯ ,0,x]a=[0,0,0,\cdots,0,x]。
但是因为询问的数组必须满足所有元素在 [1,n][1,n]，所以将整个数组往上 +1+1 后询问。
这样处理之后，发现所有大于 pnp_{n} 的位置都会被标记，所以只需要求小于 pnp_{n} 的位置了。
类似地，对于一个数 xx 的位置（x<pnx<p_{n}），可以询问数组 a=[pn−x+1,pn−x+1，⋯ ,1]a=[p_{n}-x+1,p_{n}-x+1，\cdots,1]，返回值 kk 即为 xx 的位置。
为什么这样构造
可以发现构造的数组 aa 满足除下标 nn 外的所有值都和 ana_{n} 相差 pn−xp_{n}-x。所以这个数组其实等价于 a=[0,0,0,⋯ ,0,x−pn]a=[0,0,0,\cdots,0,x-p_{n}]。
这样，就可以在 nn 步或者 n−1n-1 步内求出 pp。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int main() {
	scanf("%d",&n);
	int pd=1;
	p[n]=n+1;
	while(pd) {
		p[n]--;
		if(p[n]==1) break;
		printf("? ");
		for(int i=1;i<n;i++) printf("1 ");
		printf("%d\n",n-p[n]+2);
		fflush(stdout);
		scanf("%d",&pd);
		p[pd]=n-p[n]+1;
	}
	for(int i=1;i<n;i++) if(p[i]) p[i]+=p[n];
	pd=0;
	for(int i=1;i<p[n];i++) {
		printf("? ");
		for(int j=1;j<n;j++) printf("%d ",p[n]-i+1);
		puts("1");
		fflush(stdout);
		scanf("%d",&pd);
		p[pd]=i;
	}
	printf("! ");
	for(int i=1;i<=n;i++) printf("%d ",p[i]);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...