Codeforces Round ＃717 (Div. 2)

2021.4.21

A

The question ： Give two numbers n and k, Then enter with n Sequence of Numbers , Each time the sequence is operated ： Take two numbers , One of them plus 1, Another minus 1, And ensure that every number in the sequence is non negative . The sequence can be processed at most k operations , Make the sequence form a minimum dictionary order .（ The two numbers taken from the title need to be different in size , always wa, As a result, the scene blew up ,）

Answer key ： Each operation is for the first non 0 Number of numbers -1, Last number +1, Conduct k operations , If the sequence is all but the last number 0, Then you can exit the operation directly , The maximum dictionary order has been reached .

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int t,n,k,a[105];
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int l=1,r=n;
        while(k)
        {
            if(a[l]>=k)
            {
                a[r]+=k;
                a[l]-=k;
                k=0;
            }
            else
            {
                a[n]+=a[l];
                k-=a[l];
                a[l]=0;
                l++;

            }
            if(l==r)
                break;
        }
        for(int i=1;i<=n;i++)
            cout<<a[i]<<' ';
        cout<<endl;
    }
    return 0;
}

B

The question ： Give a number n, And then there's one that contains n Sequence of Numbers , You can XOR and sum two adjacent numbers （ At that time, it is regarded as bitwise OR ┭┮﹏┭┮）, Then the length of the sequence is -1, Because two numbers XOR into a number . Finally, judge whether the changed sequence can become a sequence with the same number , It is required that the length of the last generated sequence meeting the conditions is at least 2.

Answer key ：①x^x=0 ②x^x^x=x

First find the exclusive or sum of the whole sequence , If 0, according to ① The resulting sequence can be divided into exclusive or and equal sequences , If not 0, according to ③ Before traversal k（k<n） Whether the exclusive or sum of numbers is equal to the exclusive or sum of the whole sequence , If equal to, judge （（k+1） To （n-1）） Does the prefix XOR and have an equal to 0, If so, the whole sequence can be directly divided into XOR and equal three segment sequences .

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll t,n,a[2005];
    cin>>t;
    while(t--)
    {
        cin>>n;
        a[0]=0;
        int p=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]^=a[i-1];
        }
        if(a[n]==0)
        {
            cout<<"YES"<<endl;
            continue;
        }
        int flag=1;
        for(int i=1;i<n;i++)
        {
            if(a[i]==a[n])
            {
                for(int j=i+1;j<n;j++)
                {
                    if(!a[j])
                    {
                        cout<<"YES"<<endl;
                        flag=0;
                        break;
                    }
                }
            }
            if(!flag)
                break;
        }
        if(flag)
            cout<<"NO"<<endl;
    }
}

C

The question ： Give a length of n Sequence , Judge whether this sequence can be divided into two groups of equal sequences , If you can , You need to delete at least a few numbers from the sequence to make the sequence ineligible , And list the subscripts of the deleted numbers .

Answer key ： First, calculate the greatest common factor of the whole sequence , Then each number in the sequence is divided by the greatest common factor , Narrow the scope of , The resulting sequence must have odd numbers , And the result is the same as the original sequence

① Sequence sum is odd , It must not be possible to divide into two groups and equal sequences , Need to delete 0 A digital .

② Sequence sum is even but sequence sum /2 The resulting number cannot be determined by this n Sequences are randomly combined and added to get , It can't be divided into two groups and equal sequences , Need to delete 0 A digital .

③ Sequence sum is even , Just delete an odd number in the sequence to make the sequence sum odd , Then get ①

#include <bits/stdc++.h>
int dp[200005],a[105];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,d,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i==1)
            d=a[i];
        else
            d=gcd(d,a[i]);
    }
    for(int i=1;i<=n;i++){
        a[i]/=d;
        sum+=a[i];
    }
    int k=0;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]%2)
            k=i;
        for(int j=sum;j>=a[i];j--)
        {
            dp[j]|=dp[j-a[i]];
        }
    }
    if(sum%2||!dp[sum/2])
        cout<<0<<endl;
    else
        cout<<1<<endl<<k<<endl;
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

No one left after the fight ......