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

Rehabilitation failure xD

C It took a long time to work out the inscription, and then fst 了 , Laugh to death , If it weren't for the novice protection period of less than six times, the score would be lost hhhhhh

A. XOR Mixup

Give an array , One of these numbers is the exclusive or sum of other numbers , Output this number .

Ideas ： One of them is the exclusive or sum of other numbers , That means the XOR sum of this array is 0, According to the nature of the xor , Any number can be used as the exclusive or sum of all other numbers , The answer is to output any number in the array .

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

  Give a series of sand piles , Define a sand pile too high ： The height of this sand pile is greater than the sum of two adjacent piles . Give a k, It can be used for continuous k Heap operation , Every pile +1, Ask how many sand piles are too high after several operations .

Ideas ： Classification of discussion ：k by 1 when , Because we can operate any pile without affecting the adjacent height , We can make it as much as possible , That is, there is one in every pile ;k Not 1 when , Each modification will affect the adjacent height , Make its relative height constant , We can infer k>1 No matter how many times you modify it, it will have no effect on the too high number .

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

Give an array , If the sum of any three numbers in the array exists in the array , So this array is 3SUM-closed Of . Now give the array , Judge whether it is 3SUM-closed.

Ideas ： If there are three positive numbers or three negative numbers in the array at the same time , That will constantly increase or decrease the maximum and minimum values , disqualification ; When the conditions are met , We can regard more elements in the array as 0, Just enumerate directly in a limited number .

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： Clams clams

D. Fixed Point Guessing

   Give an arrangement of odd lengths , Exchange positions in pairs , At last, there must be an element that has not been exchanged , Every time you ask, you can get all the numbers in a section , stay 15 This number can be found in times of inquiry .

Ideas ： We can know how many numbers are in the original range by asking , Because the first array must be 1~n array . Then these numbers have two possibilities , One is to exchange with the value of this interval , In either case, there is no exchange . If elements that are not exchanged are in this interval , Then the length of this interval must be odd , Otherwise, the interval without exchange must be in another interval , For such consideration , Use two points , Can be satisfied in 15 Get the answer within times of asking .

（ Add "fflush(stdout) or cout.flush()" Is to empty the cache , Use it directly std::endl Emptying is the same ）

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： Interactive questions are actually the same as ordinary questions , The form is relatively new hhh

If there is any mistake, please advise , thank you ！