Codeforces Round ＃803 (Div. 2)(A-D)

Dashboard - Codeforces Round #803 (Div. 2) - Codeforceshttps://codeforces.com/contest/1698

A. XOR Mixup

Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1698/problem/A

The question :n A digital , Guarantee n-1 Numbers after XOR are the same as the remaining numbers , Find that number .

Ideas : Two identical numbers are XOR followed by 0, Then the question becomes n The number XOR equals 0 了 , Then we can output an input number randomly .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
void solve()
{
    int n,x;
    int ans=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x);
    printf("%lld\n",x);
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Rising Sand

Problem - B - Codeforceshttps://codeforces.com/contest/1698/problem/B

The question : In the long for 1 To n In the array , When 2 To (n-1) An element appears a[i]>a[i-1]+a[i+1], Result contribution +1. We can operate a length of k Subarray of a continuous array of , Every subarray element should +1, Ask what is the biggest contribution to the results .

Ideas : When k>1 when , Because successive cities +1, According to the above inequality , At least both sides should be at the same time +1, Therefore, no matter how many operations are performed, the result contribution will not be increased . In this case, you can directly traverse the result . When k be equal to 1 when , Just output the results greedily .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int arr[200005];
void solve()
{
    int n,k,cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    if(k==1)
    {
        printf("%d\n",(n-1)/2);
    }
    else
    {
        for(int i=2;i<=n-1;i++)
            if(arr[i]>arr[i-1]+arr[i+1])
                cnt++;
        printf("%d\n",cnt);
    }
    return; 
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. 3SUM Closure

Problem - C - Codeforceshttps://codeforces.com/contest/1698/problem/C The question : Give you an array , Ask whether to make all a[i]+a[j]+a[k]=a[l],a[l] Is an element in an array , And i<j<k.

Ideas : This problem has a rule , When the array contains 0 And it must be true when there is only one non-zero number , If there are two non-zero numbers, make sure that the sum of the two is equal to 0. however , It should be noted that , When the array length is small , There are many special situations to deal with , such as [ 1,-1,2  ] etc. , It's too troublesome to consider , Just let the array be short and perform violent simulation .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
void solve()
{
    int n,x,cnt=0,x1=0,x2=0;
    scanf("%d",&n);
    if(n<=10)
    {
        int a[11];
        map<int,int>ma;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),ma[a[i]]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                for(int k=j+1;k<=n;k++)
                {
                    int ans=a[i]+a[j]+a[k];
                    if(ma[ans]==0)
                    {
                        printf("NO\n");
                        return ;
                    }
                }
            }
        }
        printf("YES\n");
        return;
    }
// Array length is short , Direct violence 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if (x!=0)
        {
            cnt++;
            if(x1==0)
                x1=x;
            else if(x2==0)
                x2=x;
        }
    }
    if((cnt==2||cnt==0)&&x1+x2==0)
        printf("YES\n");
    else if(cnt==1)
        printf("YES\n");
    else
        printf("NO\n");
// law 
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Fixed Point Guessing

Problem - D - Codeforceshttps://codeforces.com/contest/1698/problem/D I haven't written interactive questions before , But this interaction is really simple .

Direct bisection interval , When the number of elements in the input interval in the bisection interval is even , It indicates that the exchange has taken place in the interval , Then the result is in the other half , Continue to score two points .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
bool check(int l,int r)
{
    cout<<"? "<<l<<" "<<r<<endl;
    int cnt=0,x;
    for(int i=l;i<=r;i++)
    {
        cin>>x;
        if(l<=x&&x<=r)
            cnt++;
    }
    if(cnt%2)
        return true;
    else
        return false;
}
void solve()
{
    int n;
    scanf("%d",&n);
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(l,mid))
            r=mid;
        else
            l=mid+1;
    }
    cout<<"! "<<r<<endl;
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

Pay attention to fflush(stdout) or cout.flush() in C++; Or directly <<endl.