Codeforces Round ＃803 (Div. 2)vp

A XOR Mixup

The length is 1 In the sequence of , One number is another number $XOR$ Come on , What is this number

Just output any number in the sequence

Code

void solve(){
    
    int n;cin>>n;
    vector<int> a(n+1);
    int ans = 0;
    forr(i,1,n) cin >> a[i];
    cout << a[1] << endl;
}

B Rising Sand

When m = 1 when , The largest number is $(n-1)/2$;
m > 1 when , The maximum number is the original sequence $tootall$ The number of ;

Code

void solve(){
    
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    forr(i,1,n) cin >> a[i];
    if(m == 1){
    
        int res = (n-1)/2;
        cout << res << endl;
    }
    else{
    
        int res = 0;
        forr(i,2,n-1){
    
            if(a[i] > a[i-1]+a[i+1]) res++;
        }
        cout << res << endl;
    }
}

C 3SUM Closure

When there are positive numbers or negative numbers >= 3 when , Must not meet the conditions , Output no;
When 0 The number of is greater than 0 when , There is at most one positive and one negative and enumeration 1 individual 0 that will do , Otherwise output no;
so , The maximum number of array elements that meet the conditions is 4 individual $O(n^3)$ Enumeration is enough

Code

void solve(){
    
    int n;
    cin>>n;
    map<int,int> mp;
    vector<int>v;
    int t = 0;
    int a =  0, b = 0;
    forr(i,1,n){
    
        int x;cin>>x;
        mp[x] = 1;
        if(x>0)a++,v.push_back(x);
        else if(x<0)b++,v.push_back(x);
        else t++;
    }
    if(t) v.push_back(0);
    if(a>=3||b>=3){
    
        puts("no");
        return;
    }
  forr(i,0,v.size()-1)
      forr(j,i+1,v.size()-1)
      	forr(k,j+1,v.size()-1){
    
        	int g = 0;
        	if(mp[v[i]+v[j]+v[k]]){
    
            	g = 1;
        	}
        	if(!g){
    
            	puts("no");
            	return ;
        	}
    	}
    puts("yes");
}

D Fixed Point Guessing

Interactive questions

Find out $lo{g}^{1e4}\approx 14$ Think about the dichotomy
For interval $[l,r]$ There are two cases of numbers in
Values in $[l,r]$ Within or out of
The value is in the range [l,r] There are also two cases of numbers in the range
One is with [l,r] Internal value $swap$, So they exist in pairs
The other is in the original position
So for [l,r]
If number of the numbers in this range is even , The explanation is that $swap$ operation
Then the answer must not be in this range , Binary search another interval

Code

vector<int> ask1(int l,int r){
    
    cout  << '?' <<" " << l << " " << r << endl;
    vector<int> v;
    forr(i,1,r-l+1){
    
        int x;
        cin>>x;
        v.push_back(x);
    }
    return v;
}
bool check(vector<int> x,int l, int r){
    
    int cnt = 0;
    for(auto i:x){
    
        if(i >=  l && i <= r) cnt++;
    }
    if(cnt%2==0) return 0;
    return 1;
}
void solve(){
    
    int n;
    cin >> n;
    int l = 1, r= n;
    int res = 0;
    while(l < r){
    
        int mid = l + r  >> 1;
        int f = 0;
        vector<int> b;
        b = ask1(l,mid);
        int t =  check(b,l,mid);
        if(t){
    
            r = mid;
        }
        else{
    
            l = mid + 1;
        }
    }
    cout << '!' <<" " << l << endl;
}