Codeforces Round #784 (Div. 4)

发布于 2022-05-13  548 次阅读


想一边刷题,一边学学英语了,然后就换个平台小刷一场

image-20220513190611535

A: Division?

Codeforces separates its users into 4 divisions by their rating:

  • For Division 1: 1900≤rating
  • For Division 2: 1600≤rating≤1899
  • For Division 3: 1400≤rating≤1599
  • For Division 4: rating≤1399

Given a rating, print in which division the rating belongs.

假装我不会ifelse呢?

    #include<bits/stdc++.h>

    using namespace std;

    inline long long read(void) {
        char c = getchar();
        long long x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x * f;
    }

    void solve() {
        int grade;
        grade=read();
        if(grade>=1900){
            cout<<"Division 1"<<endl;
        }else if(grade>=1600){
            cout<<"Division 2"<<endl;
        }else if(grade>=1400){
            cout<<"Division 3"<<endl;
        }else{
            cout<<"Division 4"<<endl;
        }
    }

    int main() {
        int T = 1;
        cin >> T;
        while (T--) {
            solve();
        }
    }

B:Triple

Given an array a of n elements, print any value that appears at least three times or print -1 if there is no such value.

言简意赅,就问你出现三次的个数,哈希表模拟

#include<bits/stdc++.h>

using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n =read();
    map<int,int> mp;
    for(int i = 0;i<n;i++){
        mp[read()]++;
    }
    int ans=-1;
    for(auto &i: mp){
        if(i.second>=3){
            ans=i.first;
        }
    }
    cout<<ans<<endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C:Odd/Even Increments

Given an array a=[a1,a2,…,an] of n positive integers, you can do operations of two types on it:

Add 1 to every element with an odd index. In other words change the array as follows: a1:=a1+1,a3:=a3+1,a5:=a5+1,…

Add 1 to every element with an even index. In other words change the array as follows: a2:=a2+1,a4:=a4+1,a6:=a*6+1,….

Determine if after any number of operations it is possible to make the final array contain only even numbers or only odd numbers. In other words, determine if you can make all elements of the array have the same parity after any number of operations.

Note that you can do operations of both types any number of times (even none). Operations of different types can be performed a different number of times.

他不说了,能给所有的奇数idx或者偶数idx+1,最后保证所有的都是奇数或者偶数,

那有修改前提了, 最后还要保证一样的,也就是奇数位idx和偶数位置idx 的值奇偶性分别相同咯。

两个flag扫一次

#include<bits/stdc++.h>

using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n =read();
    vector<int> mp(n);
    for(int i = 0;i<n ;i++){
        mp[i]=read();
    }
    bool a=true;
    if(mp[0]%2==1){
        for(int i =2;i<n;i+=2){
            if(mp[i]%2!=1){
                a=false;
                break;
            }
        }
    }else{
        for(int i =2;i<n;i+=2){
            if(mp[i]%2!=0){
                a=false;
                break;
            }
        }
    }
    bool b=true;
    if(mp[1]%2==1){
        for(int i =3;i<n;i+=2){
            if(mp[i]%2!=1){
                b=false;
                break;
            }
        }
    }else{
        for(int i =3;i<n;i+=2){
            if(mp[i]%2!=0){
                b=false;
                break;
            }
        }
    }
    if( a&&b){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D: Colorful Stamp

A row of n cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as BR and as RB

During use, the stamp must completely fit on the given n cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp.

For example, one possible sequence of stamps to make the picture BRBBW could be WWWWW→WWRB–––W→BR–––RBW→BRB–––BW. Here W, R, and B represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline.

Given a final picture, is it possible to make it using the stamp zero or more times?

这啥意思呢,就是可以把BR拼到一起。那也就是说在每个子串中,必须要有至少1个B和一个R。

然后就找一下每个不带W的子串,模拟一下就好了

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n = read();
    string s;
    cin >> s;
    s = "W" + s + "W";
    string now;
    vector<string> mp;
    for (int i = 0; i < s.size(); ++i) {
        if(s[i]=='W'&&now.size()!=0){
            mp.push_back(now);
            now="";
        }else if (s[i]!='W'){
            now+=s[i];
        }
    }
    for(auto &str : mp){
        if(str.find('R')==str.npos){
            cout<<"NO"<<endl;
            return;
        }
        if(str.find('B')==str.npos){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;

}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E: 2-Letter Strings

Given n strings, each of length 2, consisting of lowercase Latin alphabet letters from 'a' to 'k', output the number of pairs of indices (i,j) such that i<j and the i-th string and the j-th string differ in exactly one position.

In other words, count the number of pairs (i,j) (i<j) such that the i-th string and the j-th string have exactly one position p (1≤p≤2) such that sipsjp.

The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.

扫!!!!在数电上这叫,逻辑相邻,可以看看数电逻辑相邻的判断

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int a[30][30];
void solve() {
    long long  n,ans=0;
    cin>>n;
    memset(a,0,sizeof a);
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<2;j++)
            for(char c='a';c<='k';c++)
            {
                if(c==s[j])continue;
                string t=s;t[j]=c;
                ans+=a[t[0]-'a'][t[1]-'a'];
            }
        ++a[s[0]-'a'][s[1]-'a'];
    }
    cout<<ans<<'\n';
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F:Eating Candies

There are n candies put from left to right on a table. The candies are numbered from left to right. The i-th candy has weight wi. Alice and Bob eat candies.

Alice can eat any number of candies from the left (she can't skip candies, she eats them in a row).

Bob can eat any number of candies from the right (he can't skip candies, he eats them in a row).

Of course, if Alice ate a candy, Bob can't eat it (and vice versa).

They want to be fair. Their goal is to eat the same total weight of candies. What is the most number of candies they can eat in total?**

前缀和,后缀和,和的位置idx之和小于n,跟tm贯口是的

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n = read();
    vector<int> mp(n);
    for (int i = 0; i < n; ++i) {
        mp[i] = read();
    }
    vector<int> ls(n);
    ls[0] = mp[0];
    vector<int> rs(n);
    rs[n - 1] = mp[n - 1];
    map<int, vector<int>> m;
    m[mp[0]].push_back(1);
    m[mp[n - 1]].push_back(1);
    for (int i = 1; i < n; i++) {
        ls[i] = ls[i - 1] + mp[i];
        m[ls[i]].push_back(i+1);
    }
    for (int i = n - 2; i >= 0; i--) {
        rs[i] = rs[i + 1] + mp[i];
        m[rs[i]].push_back(n-i);
    }
    int ans=0;
    for(auto & l : m){
        if(l.second.size()>=2){
            if(l.second[0]+l.second[1]>ans&&l.second[0]+l.second[1]<=n){
                ans=l.second[0]+l.second[1];
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G: Fall Down

There is a grid with n rows and m

columns, and three types of cells:

An empty cell, denoted with '.'.
A stone, denoted with '*'.
An obstacle, denoted with the lowercase Latin letter 'o'. 

All stones fall down until they meet the floor (the bottom row), an obstacle, or other stone which is already immovable. (In other words, all the stones just fall down as long as they can fall.)

Simulate the process. What does the resulting grid look like?

从下往上模拟每列即可,记录可搬移的位置,

如果遇到*,就移动下去,位置上移。

如果遇到o,就让pos上去。

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n = read();
    int m = read();
    vector<string> mp(n);
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }
    for (int i = 0; i < m; i++) {
        int pos = n - 1;
        for (int j = n - 1; j >= 0; j--) {
            if (mp[j][i] == '*') {
                mp[j][i] = '.';
                mp[pos][i]='*';
                pos--;
            } else if (mp[j][i] == 'o') {
                pos = j - 1;
            }
        }

    }
    for (int i = 0; i < n; i++) {
        cout << mp[i] << endl;
    }
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

绝对不是恋爱脑!