Codeforces round 784 (Div. 4) AK solution

A little memory of the first time ak cf div4 （ Although it's very simple , But it is said that CF Only once before div4 Ash is often rare ）
link ：Round #784 (Div. 4)

A Division?

The title gives the corresponding rank of different scores if Just judge the output of the statement

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
void solve()
{
    
    int n;
    cin >> n;
    if(n >= 1900)cout << "Division 1"<<endl;
    else if(1600<=n && n<=1899)cout << "Division 2"<<endl;
    else if(1400<=n && n<=1599)cout << "Division 3"<<endl;
    else if(n <=1399)cout << "Division 4"<<endl;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

B Triple

Given length is $n$ Array of $ai$ Ask whether there is a number in the array, and the number of occurrences is greater than or equal to 3, Because the number is very small $ai<n$ So we use vis The number of array tags is enough The subscript represents the value . If it does not exist ai Size limit for We can use map The recording effect is the same

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int vis[N];
void solve()
{
    
    int n;
    cin >> n;
    int ans = -1;
    for(int i=1;i<=n;i++)vis[i] = 0;
    for(int i=1;i<=n;i++)
    {
    
        int x;
        cin >> x;
        vis[x] ++;
        if(vis[x] >= 3)ans = x;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

C Odd/Even Increments

The question ：

Given length is $n$ Array of You can add... To all numbers with even or odd subscripts 1 There is no limit to the number of operations Ask if all the odd and even numbers in the array can be made one .

Ideas ：

because Each operation must be performed on all even or odd subscripts , For all numbers with the same subscript parity, each change is synchronous , If the initial is different, it is impossible to make it the same by operation . for example ：1 2 2 Subscript to be 1 3 The initial parity of the number is different , Operate on even subscripts 1 3 Subscripts have no effect , The operation of odd subscript can only change parity at the same time . So judge whether the initial array has odd subscripts / Whether even subscripts and parity are the same .

CODE：

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 110;
int a[N];
void solve()
{
    
    int n;
    cin >> n;
    bool F = true;
    for(int i=1;i<=n;i++)
    {
    
        cin >> a[i];
        if((i&1)&&a[i]%2!=a[1]%2)F = false;
        else if(i%2==0 && a[i]%2!=a[2]%2)F = false ;
    }
    if(F) cout << "YES" << endl;
    else cout << "NO" << endl;
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

D Colorful Stamp

The question ：

Given length is $n$ String There is only ${}^{\prime }{R}^{\prime }$ Red ${}^{\prime }{B}^{\prime }$ Blue ${}^{\prime }{W}^{\prime }$ Three white characters , Now I'll give you a length of $n$ All characters of the are $W$ String . You have an unlimited number of operations , The selected subscript is $i,i+1$ Change the character of to $RB$ perhaps $BR$ You can repeat the operation on the same character , Subscript selection ：$1\le i<n$. Ask if you can do several operations to change the string to a given string

Ideas ：

First of all, we can get from the question ： To be $W$ Separated substrings can be judged separately , because $W$ Cannot be altered by staining , All of them have no influence on each other for example ：WRRBWBBRW Two separated substrings RRB and BBR They don't influence each other . Next, we'll discuss it according to the situation ：

1. For length is 1 String And the only character is $R$ or $B$ It must be impossible to get , So we can deduce a separate substring （ By $W$ Separated substrings ） If its color is solid and not white Then the substring must not be obtained for example WBBW,WRR.

2. For non pure colors （ That is, a separate substring contains both $B$ Contain, $R$） Let's make a conclusion first It must be possible to do several operations to get , prove ： For adjacent characters, there is no substring of the same character （ That is, the adjacent blue must be red , vice versa ） Come on We can use the basic operation （$BR$,$RB$） To get $WWW$ -> $WRB$ -> $BRB$.
For substrings with equal adjacent characters It can also be obtained by the following operations $WWW$ -> $WRB$ -> $RRB$,$RBB$,$BBR$,$BRR$ So it is with . So we can construct all substrings .
The code is very simple , For individual substrings, calculate R,B The number of If a color is 0 One is not 0 It indicates that the substring is a non white solid color substring Direct output NO that will do

CODE

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
char a[N];
void solve()
{
    
    int n;
    cin >> n;
    cin >> (a + 1);
    int sum1=0,sum2=0;
    for(int i=1;i<=n;i++)
    {
    
        if(a[i] == 'R')sum1 ++;
        else if(a[i] == 'B')sum2 ++;
        
        if(a[i]=='W' || i==n)
        {
    
            if((sum1&&!sum2)||(!sum1&&sum2))
            {
    
                cout << "NO" << endl;
                return ;
            }
            sum1 = 0;
            sum2 = 0;
        }
        
    }
    cout << "YES" <<endl;
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

E 2-Letter Strings

The question ：

Given $n$ A length of 2 String , Ask how many string pairs there are $(i,j)i<j$ Satisfy i String and j The string has one and only one character different .

Ideas ：

Because the string length is only two digits, we use $s1$$s2$ Represents these two characters , use $cnt1,cnt2$ The array records the first character as $s1$ The second character of the string is $s2$ The number of strings .
So for $i$ character string ：$ch1,ch2$ The contribution of is to add the first character and $ch2$ The same and the second character is the same as $ch2$ Same number of strings , Finally, it happens to be $ch1ch2$ The number of strings . Because the number of strings that exactly equal when the first character is the same and the second character is the same is calculated once , So the last minus is multiplied by 2. It happens to be $ch1ch2$ The number of strings we can use map Statistics . therefore $ans=cnt1[ch1{-}^{\prime }{a}^{\prime }]+cnt2[ch2{-}^{\prime }{a}^{\prime }]-2\ast map[ch1,ch2];$, Every time I traverse i The postscript will i The count of strings starts from cnt1 In the from cnt2 To prevent double counting $(i,j)i>=jOflovecondition$. Example ：

n = 6
1.ac
2.ac
3.ak
4.ak
5.bc
6.bc
 about 1.ac  The first character is a The string of is 1,2,3,4  common 4 The second character is c There are 1,2,5,6 common 4 individual 
 Both are right 1,2 ac Statistics were made, and finally ans = 4 + 4 - 2 * 2 

CODE

#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll s1[30],s2[30];
char ch1[N],ch2[N];
map<pair<char,char>,ll>mp;
void solve()
{
    
    int n;
    cin >> n;
    mp.clear();
    for(int i=1;i<=n;i++)
    {
    
        cin >> ch1[i] >> ch2[i];
        s1[ch1[i]-'a'] ++;
        s2[ch2[i]-'a'] ++;
        mp[{
    ch1[i],ch2[i]}] ++;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
    
        ll sum = s1[ch1[i]-'a'] + s2[ch2[i]-'a'] - 2 * mp[{
    ch1[i],ch2[i]}];
        ans += sum;
        s1[ch1[i]-'a'] --;
        s2[ch2[i]-'a'] --;
        mp[{
    ch1[i],ch2[i]}] --;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

F Eating Candies

The question ：

Given $n$ A candy weighs $ai$ A Only eat from left to right ,B You can only eat from right to left , And you can't skip not eating the current candy to eat the later . requirement A and B The weight of candy is the same , Ask how much candy they can eat at most .

Ideas ：

You can only eat candy in one direction , And requiring equal weight, we thought of using the prefix and . use map Record A The historical prefix of and the subscript of are $S1->Sn$, Then find out from the back to the front B And For each $Si$ stay map Query in If there are equal , And the query found A Prefix and location of $id<i$ Then you can update the answer .

 for example :
6
2 1 4 2 4 1
map As recorded in 
2 3 7 9 13 14  Left to right prefixes and 
1 2 3 4 5  6  Prefix and corresponding number 
 Find the prefix sum from right to left 
 1  5 7 11 12 14
-1 -1 3 -1 -1 -1 map The number recorded in   Only 7 Found the corresponding answer ans = 3 + n - 3 + 1

CODE

#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int a[N];
map<ll,int>mp;
void solve()
{
    
    int n;
    cin >> n;
    mp.clear();
    ll sum1=0,sum2=0,ans=0;
    for(int i=1;i<=n;i++)
    {
    
        cin >> a[i];
        sum1 += a[i];
        mp[sum1] = i;
    }
    int id;
    for(int i=n;i>=1;i--)
    {
    
        sum2 += a[i];
        if(mp.count(sum2))id = mp[sum2];
        else continue ;

        if(id < i)ans = id + n - i + 1;
        else break;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

G Fall Down

Simulate the process of stone falling , Because columns do not affect each other We can simulate each column separately

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 110;
char a[N][N];
void solve()
{
    
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)scanf("%s",a[i] + 1);
    for(int i=1;i<=m;i++)// Start with the column 
    {
    
        for(int j=n,up=j;j>=1;up=j,j--)
        {
    
            if(a[j][i]=='o') continue ;

            int sum = 0;
            up = j;
            if(a[j][i]=='*')sum = 1;
            while(up - 1 >= 1 && a[up - 1][i]!='o')
            {
    
                up --;
                if(a[up][i]=='*')sum ++;
            }
            for(int k=0;k<sum;k++) a[j-k][i] = '*';
            for(int k=j-sum;k>=up;k--) a[k][i] = '.';
            j = up;
        }
    }
    for(int i=1;i<=n;i++)printf("%s\n",a[i] + 1);
    return ;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

H Maximal AND

The question ：

It's classic cf Bit operation problem , Given length is $n$ Array of $a$ Yes $k$ It's an opportunity . Can make any $ai|2^j(j<=30)$ Ask for k After this operation, it will $a1ANDa2AND\dots ANDan$ What is the maximum value after .

Ideas ：

Because binary numbers $AND$ The operation of different digits has no effect , The final answer is binary if 1 All required $ai$ The binary digit is 1 So we greedily start traversing the array from the high bit of binary , if $ai$ This position is 0 So count $sum++$ take $a1->an$ If less than or equal to... After statistics $k$ It shows that the binary digit can make all... Through several operations $ai$ by 1 The answer plus the value represented by the binary digit , meanwhile $k-sum$

CODE

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll a[N],b[40],n,k;
void init()
{
    
    b[0] = 1;
    for(int i=1;i<=30;i++)b[i] = b[i-1] << 1;// Preprocess the value of binary digits 
}
void solve()
{
    
    cin >> n >> k;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll ans = 0;
    for(int i=30;i>=0;i--)
    {
    
        int sum = 0;
        for(int j=1;j<=n;j++)
        {
    
            if(!(a[j]>>i&1)) sum ++;// Bit operation determines whether the binary digit on this bit is 1
        }
        if(k >= sum)
        {
    
            ans += b[i];
            k -= sum;
        }
    }
    printf("%lld\n",ans);
    return ;
}
int main()
{
    
    int T;
    init();
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

summary

The problem is not difficult , No, the algorithms are basically simple simulation and thinking to find rules . It should be E,H It's a little difficult . Generally speaking, it can be half an hour in advance AK ok , Hand speed and thinking are still a little slow ,rk1 Big guy is so strong , One question per minute on average 12 The speed of light per minute AK tql%%%.