Codeforces Round ＃803 (Div. 2)（A~D）

复健失败 xD

C题花了好久搞出来然后fst了，笑死，要不是因为没出六次的新手保护期就掉分了hhhhhh

A. XOR Mixup

给出一个数组，其中某一个数是其他数异或和，输出这个数。

思路：其中某个数是其他数的异或和，那就说明这个数组的异或和是0，根据异或的性质，其中任何一个数都可以作为其他所有数的异或和，答案就是随便输出数组中的一个数即可。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
#define INF 0x3f3f3f3f
const int mod=1e9+7;
const int N=1e3+5;
int t,n;
int a[N];

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
		}
		std::cout<<a[n]<<'\n';
	}
	return 0;
}

 B. Rising Sand

 给出一系列的沙堆，定义一个沙堆过于高：这个沙堆的高度大于相邻两堆之和。给出一个k，每次可以对连续的k堆操作，每一堆+1，问经过若干次操作后最多有多少沙堆过于高。

思路：分类讨论：k为1时，因为我们可以对任意的一堆进行操作而不影响相邻的高度，我们可以使它尽可能的多，即每隔一堆就有一个；k非1时，每次修改都会影响相邻的高度，使其相对高度是不变的，我们大可以推断k>1时无论多少次修改都是对过于高的个数无影响。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
#define INF 0x3f3f3f3f
const int mod=1e9+7;
const int N=2e5+5;
int t,n,k;
int a[N];

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>k;
		int ans=0;
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
		}
		if(k==1){
			int res=n-2;
			std::cout<<(res+1)/2<<'\n';
			continue;
		}
		for(int i=2;i<n;i++){
			if(a[i]>a[i+1]+a[i-1]) ans++;
		}
		std::cout<<ans<<'\n';
	}
	return 0;
}

C. 3SUM Closure

给出一个数组，若对于数组中任意三个数的和都存在于数组中，那么这个数组是3SUM-closed的。现给出数组，判断其是否为3SUM-closed。

思路：若数组中同时存在三个正数或三个负数，那会不断增大或减小最大值和最小值，不符合条件；这样满足条件时，数组中我们可以视为更多的元素为0，在有限个数内直接暴力枚举即可。

AC Code：

#include <bits/stdc++.h>

#define int long long
const int N=2e5+5;
int t,n;
int a[N];
std::vector<int>vec;
std::map<int,int>mp;

bool check(){
	int len=vec.size();
	for(int i=0;i<len;i++){
		for(int j=i+1;j<len;j++){
			for(int k=j+1;k<len;k++){
				if(!mp[vec[i]+vec[j]+vec[k]]) return false;
			}
		}
	}
	return true;
}

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		int l=0,s=0;
		vec.clear();
		mp.clear();
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
			if(a[i]!=0) vec.push_back(a[i]);
			else{
				if(!mp[0]) vec.push_back(a[i]);
			}
			mp[a[i]]++;
			if(a[i]>0) l++;
			if(a[i]<0) s++;
		}
		if(l>=3||s>=3){
			std::cout<<"NO"<<'\n';
			continue;
		}
		std::cout<<(check()?"YES":"NO")<<'\n';
	}
	return 0;
}

os：蛤蛤

D. Fixed Point Guessing

  给出一个奇数长度的排列，两两进行位置互换，那最后必有一个元素未交换位置，每次询问可以得到一段区间内的所有数，在15次询问内找到这个数。

思路：我们通过询问可以知道有多少数是原来这个区间的，因为一开始的数组必是1~n排列。那么这些数有两种可能，一是与这个区间的值进行了交换，两一种情况是未进行交换。若没进行交换的元素在这个区间，那么这个区间长度必为奇数，否则没有交换的区间一定在别的区间，对于这样的考虑，使用二分，可以满足在15次询问内得到答案。

（交互题输出后加 "fflush(stdout) or cout.flush()" 是要清空缓存区，直接使用 std::endl 清空也是一样的）

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N=1e4+5;
int t,n;
int a[N];

void ask(int l,int r){
	std::cout<<"? "<<l<<' '<<r<<std::endl;
	for(int i=l;i<=r;i++){
		std::cin>>a[i];
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		int l=1,r=n;
		while(l<r){
			int mid=l+r>>1;
			ask(l,mid);
			int cnt=0;
			for(int i=l;i<=mid;i++){
				cnt+=(a[i]>=l&&a[i]<=mid);
			}
			if(cnt&1) r=mid;
			else l=mid+1;
		}
		std::cout<<"! "<<l<<std::endl;
	}
	return 0;
}

os：交互题其实和普通题是一样的欸，就是形式比较新一些hhh

若有错误请指教，谢谢！