写在前面
比赛链接：Dashboard - Codeforces Round #803 (Div. 2) - Codeforces
这场是手速场，提前回寝室睡觉，然后起床打比赛状态贼好，一开始本来打算放弃D的，但是突然有了灵感！
小号加了121分，准备先把小号打上蓝，然后不分大小号了，每次拿分最低的打。
A. XOR Mixup（位运算）
题意
给你一个长度为n的数组，告诉你其中有一个数字是由其他三个异或构成的，问你是哪一个被其他构成。例如：
4
4 3 2 5
这样来看4 xor 2 xor 5 = 3，所以输出3
思路
利用异或性质a ^ b = c可以推出a ^ b ^ c = c ^ c = 0，原因就是两边同时异或一个数不变，并且a ^ a = 0。
这样来看其实数组里面每一个数字都可以，前提是满足条件，题目保证都满足，所以我选择输出a[n]
代码
inline void Case_Test()
{
x = 0;
cin>>n;
for (int i=1;i<=n;i++)
cin>>k;
cout<<k<<endl;
}
B. Rising Sand（思维）
题意
给你一个n,k以及一个长度为n的数组，你可以选择一个连续k个区间全部+1，问最多有多少堆（堆的定义是$1\leq i\leq n$满足$a_i>a_{i-1}+a_{i+1}$）
思路
这样来看，我需要满足拉大堆与两侧的距离，我想让更多的$i$的$a_i-a_{i-1}-a_{i+1}>0$也就是拉大$a_i-a_{i-1}-a_{i+1}$，所以——当 $2\leq k$ 的时候，是无论如何都不能使得这个值增加的，因为你总是与两侧有关系。
所以如果是$2\leq k$的时候只需要输出读入的时候有多少个那就是多少个；否则就可以构造堆为$2,4,6,...,$
代码
inline void Case_Test()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
cin>>a[i];
ans = 0;
for (int i=2;i<n;i++)
if (a[i]>a[i-1]+a[i+1])
ans++;
if (k>=2) cout<<ans<<endl;
else cout<<(n-1)/2<<endl;
}
C. 3SUM Closure（思维） 1300
题意
定义一个SUM-closed，如果这个数列里面存在三个不同的数字，加起来的数也在数列中，那么这个就是"YES"
思路
假设有3个正数（负数同理）a、b、c，a+b+c肯定会大于max(a,b,c)，如果也在数列中，那么就一直这么递增下去，可以看出，是必定不会满足的。所以"3SUM-closed"最多只能有两个正数，和两个负数。
如果有0的话，就加入一个vector中，这个vector还有其他不等于0的，所以这个一定不大，因为0最多1个，正数负数最多加起来四个。
然后对这些进行for循环暴力查找即可
代码
map<int,bool> mp;
inline void Case_Test()
{
cin>>n;
mp.clear();
vector<int> b,z,f;
for (int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]] = true;
if (a[i]!=0) b.push_back(a[i]);
if (a[i]<0) f.push_back(a[i]);
if (a[i]>0) z.push_back(a[i]);
}
if (f.size()>=3||z.size()>=3)
{
cout<<"NO"<<endl;
return;
}
if (mp.find(0)!=mp.end())
b.push_back(0);
cnt = b.size();
for (int i=0;i<cnt;i++)
for (int j=i+1;j<cnt;j++)
for (int k=j+1;k<cnt;k++)
if (mp.find(b[i]+b[j]+b[k])==mp.end())
{
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
}
D. Fixed Point Guessing（交互题，二分） 1600
题意
给你一个长度n（一开始只知道n），本来是一个长度为n（ $1\leq n \leq 10^4$ ）的数组，数组是保证是奇数，里面只能两两交换，并且每个数只能交换一次，这样就只有一个数不能交换。题目用交换后的数组，让你不超过$15$次询问，猜出这个数字是哪个。
你可以猜? x y，题目会告诉你区间$[x,y]$中的从小到大排序是多少。例如5,4,3,2,1，你询问? 1 3，这个时候就会告诉你3 4 5。
最后需要返回! x，告诉程序x是不变的。
思路
我觉得这种题主要是看数据范围，这个15告诉你，肯定就是log2级别的了，所以大概率需要二分或者倍增的区间询问。这个题准备放弃的，但是突然发现那个答案那个数所在的区间有一个特征：
对于一个区间$[x,y]$，查询里面的数字，如果发现应该在$[x,y]$其中的是奇数个，那么能确定不变的就是在这个区间里，这个聊天记录是赛中的，因为就是“成双成对”的概念。
所以就可以一直这么二分下去，我一发过了，真爽，我写的dfs，不过20行。
代码
void dfs(int l,int r)
{
if (l==r) {cout<<"! "<<l<<endl;return;}
int mid = (l+r)>>1;
int m = mid-l+1;
cout<<"? "<<l<<" "<<mid<<endl;
cnt = 0;
for (int i=l;i<=mid;i++)
{
cin>>a[i];
if (a[i]>=l&&a[i]<=mid) cnt++;
}
if (cnt%2==1) dfs(l,mid);
else dfs(mid+1,r);
}
inline void Case_Test()
{
cin>>n;
dfs(1,n);
}