Codeforces Round ＃721 (Div. 2)

2021.5.20

A

The question ： Give an integer n, Find the largest k, among n&(n-1)&...&k=0

Answer key ： Just need to make n Every decreasing number, every binary bit, exists 0, May think k Namely n The highest position of 1 The others are 0 Number of numbers m-1, This ensures that every binary bit has 0

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n==1)
            cout<<0<<endl;
        else if(n==2)
            cout<<1<<endl;
        else{
              ll k=1;
        while(k<n){
            k*=2;
        }
        if(k!=n)
        k/=2;
        cout<<k-1<<endl;
        }
    }
    return 0;
}

B1

The question ： The rules ： There can only be two operations at a time ：1、 hold 0 become 1 cost 1 ;2、 If the status of the current string is not palindrome string , That can reverse the string of subsymbols , If it is a palindrome string or the previous round used flipping , You can only use the operation 1, Can't flip . Give a palindrome string , Contains only 0 and 1,ALICE First of all ,BOB Later stage , Finally, the strings are changed to 1 Who spends more , If so, output “DRAW”.

Answer key ： Just judge the substring 0 The number of , If there is no 0 It must be a draw , If 0 The number of is odd , Then prove that the length of the string is odd , And the middle one is 0, If only 1 individual 0 Then you must lose first , If it is greater than 1, Then the back hand will lose （ such as “10001”, Take off the middle first , String is palindrome again , The back hand can only take the cost 1, Then turn it over first , The second hand can only spend 1）, If 0 The number of is even , Then the first hand will lose .（ Finally, there are two forerunners left, and each time they have to spend 1, Backhand flip , The last one can only be spent first 1）

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        int k0=0,k1=0,len=s.size();
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')
                k0++;
            else
                k1++;
        }
        if(k0==0)
            cout<<"DRAW"<<endl;
        else
        {
            if(k0%2)
            {
                if(k0==1)
                    cout<<"BOB"<<endl;
                else
                    cout<<"ALICE"<<endl;
            }
            else
            {
                cout<<"BOB"<<endl;

            }
        }
    }
    return 0;
}

B2

The question ： Again B1 On the basis of , The input substring is not necessarily a palindrome string .

Answer key ： It is only necessary to point out that it is not a case of winning first ：0 The number is 2 And there is only one asymmetric position , It was a draw , If it is a palindrome string and 0 The number of is even or 0 The number of 1, Then the backhand wins , In other cases, we win first （ There is a choice of holding or turning first , So you can get rid of losing , Give yourself the loss to the latter ）

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <string>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        int dif=0;
        for(int i=0;i<(n+1)/2;i++)
        {
            if(s[i]!=s[n-i-1])
                dif++;
        }
        int num=count(s.begin(),s.end(),'0');
        if(!dif&&(num%2==0||num==1))
            cout<<"BOB"<<endl;
        else if(dif==1&&num==2)
            cout<<"DRAW"<<endl;
        else
            cout<<"ALICE"<<endl;
    }
    return 0;
}

C

The question ： Give a length of n Integer sequence of a, Where if an integer pair i<j && ai=aj Then the contribution of this integer pair is 1, If different subsequences have repeated positional contributions, they belong to different contributions , Calculation sequence a The contribution sum of all subsequences of .

Answer key ：dp[i] The contribution of =dp[i-1] The contribution of + contain ai The contribution of subsequences of this number ( All the preceding is equal to ai The subscript sum of the number of * Included later ai A few more numbers can be used as subsequences )

#include <iostream>
#include <algorithm>
#include <map>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    int t,n,x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        map<int,ll>m;
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            sum+=m[x]*(n-i+1);
            cout<<m[x]*(n-i+1)<<endl;
            m[x]+=i;
        }
        cout<<sum<<endl;
    }
    return 0;
}