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

题意:n个数字,保证n-1个数字进行异或之后和剩下的数字相同,找出那个数字.

思路:两个相同的数异或之后为0,那么该题就变为n个数字异或等于0了,那么我们就可以随机输出一个输入的数字即可.

#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

题意:在长为1到n的数组中,当2到(n-1)个元素出现a[i]>a[i-1]+a[i+1],结果贡献就+1.我们每次可以操作长度为k的连续数组的子数组,每个子数组元素都要+1,问结果贡献最大是多少.

思路:当k>1时,因为连续的都会+1,根据上面不等式,两边至少要同时+1,所以不论经过多少次操作都不会增加结果贡献大小.这种情况直接遍历求结果即可.当k等于1时,直接贪心输出结果即可.

#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题意:给你一个数组,问是否令所有的a[i]+a[j]+a[k]=a[l],a[l]是数组中的元素,且i<j<k.

思路:这个题有一个规律,当数组内含有0并且只有一个非零数的时候是一定成立的,如果有两个非零数则要保证两者相加等于0.但是,要注意的是,当数组长度比较小的时候,有很多的特殊情况要处理,比如[ 1,-1,2  ]等,考虑起来太麻烦,直接让数组较短的时候进行暴力模拟求即可.

#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;
    }
//数组长度短,直接暴力
    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");
//规律
    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以前都没写过交互题的,但是这个交互真的简单.

直接二分区间,当输入的区间内元素在二分的这个区间的个数是偶数时,说明区间内都进行了交换,那么结果就在另一半区间,继续二分即可.

#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;
}

注意输出后要fflush(stdout) or cout.flush() in C++;或者直接<<endl.