P8320 『JROI-4』Sunset

题目背景

写不出优美的文字，索性不放背景了。【背景待填充】

由于这只是个 C，出题人打算良心点，于是加了几个 $0$（指交互次数）（确信）——验题人注。

题目描述

这是一道交互题。

落日可以抽象成一个序列 { a n } \{a_n\} {an​}.

{ a n } \{a_n\} {an​} 是一个 $1\sim n$ 的排列。

你还有一个数列 { d n } \{d_n\} {dn​}，为当前 $a$ 数列的前缀最大值。

换言之，
d i = max ⁡ j = 1 i { a j } d_i=\max_{j=1}^i \{a_j\} di​=j=1maxi​{aj​}

注意：根据前文的定义， { d n } \{d_n\} {dn​} 可能随着 { a n } \{a_n\} {an​} 数列的改变而改变。

您可以进行两种不同的操作：

• 指定一个 $i$，询问对于当前的 $a$ 数列， $d_{1\sim i}$ 中有几个不同的值。
• 指定一个 $i$，使得 $a_i\leftarrow 0$.

请使用不超过 $5500$ 次操作求出原排列。

保证交互库是静态的，即交互库不会在交互过程中改变 $a$ 数列。

输入格式

本题多测，第一行一个整数 $T$，表示测试组数，接下来 $T$ 行每行一个整数 $n$，表示本组数据下数列的长度。

本题使用 IO 交互模式。

交互格式

• ? 1 i 询问 $d_{1\sim i}$ 中有几个不同的值，交互库会返回一个正整数 $x$ 表示答案。

• ? 2 i 使 $a_i=0$。

• ! a1 a2 a3 ... an 输出答案。

请注意：在每组数据中，请保证前两种操作的次数总和不超过 $5500$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

• 对于 C/C++：fflush(stdout);
• 对于 C++：std::cout << std::flush;
• 对于 Java：System.out.flush();
• 对于 Python：stdout.flush();
• 对于 Pascal：flush(output);

对于其他语言，请自行查阅对应语言的帮助文档。

输出格式

见「交互格式」。

输入输出样例 #1

输入 #1

1

3

1

2

3


2

输出 #1

? 1 1

? 1 2

? 1 3

? 2 2
? 1 3

! 1 2 3

说明/提示

样例仅供理解交互过程，可能不符合逻辑。

【样例解释】

初始的序列 $a$ 为 1 2 3，$d$ 为 1 2 3.

在对交互库输出了形如 ? 2 2 的命令后，序列 $a$ 变为 1 0 3，$d$ 变为 1 1 3，此时 $d_1\sim d_3$ 中有 $2$ 种不同的值，分别是 $1,3$.

---

可供选手参考的资料：OI Wiki-交互题 | 猜数（IO交互版）

---

数据范围

• 对于 $10\%$ 的数据，$T=1$；
• 对于 $30\%$ 的数据，$n\le 70$；
• 对于另外 $20\%$ 的数据，保证数列 $a$ 随机生成；
• 对于全部数据：$T\le 10,1\le n\le 500$。

C++实现

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
vector<int> v;
int ans[N];
int ask(int x){
	if(x == 1) return 1;
	printf("? 1 %d\n", x);
	fflush(stdout);
	int t; scanf("%d", &t);
	return t;
}
int ra;
int getmx(int l, int r){
	if(l == r) return l;
	int mid = l + r >> 1;
	int t = ra, tt = ask(mid);
	if(t == tt){
		ra = tt;
		return getmx(l, mid);
	} else {
		ra = t;
		return getmx(mid+1, r);
	}
}
int main(){
	int t,n; scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for(int i = n; i; -- i){
			ra = ask(n);
			int k = getmx(1, n);
			ans[k] = i;
			printf("? 2 %d\n", k);
			fflush(stdout);
		}
		printf("!");
		for(int i = 1; i <= n; ++ i) printf(" %d", ans[i]); puts("");
		fflush(stdout);
	}
	return 0;
} 

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容