P8320 『JROI-4』Sunset
题目背景
写不出优美的文字，索性不放背景了。【背景待填充】
由于这只是个 C，出题人打算良心点，于是加了几个0 00（指交互次数）（确信）——验题人注。
题目描述
这是一道交互题。
落日可以抽象成一个序列{ a n } \{a_n\}{an}.
{ a n } \{a_n\}{an}是一个1 ∼ n 1\sim n1∼n的排列。
你还有一个数列{ d n } \{d_n\}{dn}，为当前a aa数列的前缀最大值。
换言之，
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 ii，询问对于当前的a aa数列，d 1 ∼ i d_{1\sim i}d1∼i中有几个不同的值。
- 指定一个i ii，使得a i ← 0 a_i\leftarrow 0ai←0.
请使用不超过5500 55005500次操作求出原排列。
保证交互库是静态的，即交互库不会在交互过程中改变a aa数列。
输入格式
本题多测，第一行一个整数T TT，表示测试组数，接下来T TT行每行一个整数n nn，表示本组数据下数列的长度。
本题使用 IO 交互模式。
交互格式
? 1 i询问d 1 ∼ i d_{1\sim i}d1∼i中有几个不同的值，交互库会返回一个正整数x xx表示答案。? 2 i使a i = 0 a_i=0ai=0。! a1 a2 a3 ... an输出答案。
请注意：在每组数据中，请保证前两种操作的次数总和不超过5500 55005500。
需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：
- 对于 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 aa为1 2 3，d dd为1 2 3.
在对交互库输出了形如? 2 2的命令后，序列a aa变为1 0 3，d dd变为1 1 3，此时d 1 ∼ d 3 d_1\sim d_3d1∼d3中有2 22种不同的值，分别是1 , 3 1,31,3.
可供选手参考的资料：OI Wiki-交互题|猜数（IO交互版）
数据范围
- 对于10 % 10\%10%的数据，T = 1 T=1T=1；
- 对于30 % 30\%30%的数据，n ≤ 70 n\le 70n≤70；
- 对于另外20 % 20\%20%的数据，保证数列a aa随机生成；
- 对于全部数据：T ≤ 10 , 1 ≤ n ≤ 500 T \leq 10,1\leq n\leq 500T≤10,1≤n≤500。
C++实现
#include<bits/stdc++.h>usingnamespacestd;constintN=510;vector<int>v;intans[N];intask(intx){if(x==1)return1;printf("? 1 %d\n",x);fflush(stdout);intt;scanf("%d",&t);returnt;}intra;intgetmx(intl,intr){if(l==r)returnl;intmid=l+r>>1;intt=ra,tt=ask(mid);if(t==tt){ra=tt;returngetmx(l,mid);}else{ra=t;returngetmx(mid+1,r);}}intmain(){intt,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(inti=n;i;--i){ra=ask(n);intk=getmx(1,n);ans[k]=i;printf("? 2 %d\n",k);fflush(stdout);}printf("!");for(inti=1;i<=n;++i)printf(" %d",ans[i]);puts("");fflush(stdout);}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
