Codeforces Round 950 (Div.3)

6月3日 Codeforces 实战记录。（1495 -> 1425）

AC数3/8。
比赛跳转：Codeforces Round 950 (Div. 3)

题解

A. Problem Generator

完整代码：

#include<bits/stdc++.h>
using namespace std;

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

int cnt[7];

void solve(){
    memset(cnt, 0, sizeof cnt);
    int n = read(), m = read();
    for(int i = 0; i < n; i++){
        char c; cin >> c;
        cnt[c - 'A'] ++;
    }
    int res = 0;
    for(int i = 0; i < 7; i++){
        res += max(0, m - cnt[i]);
    }
    cout << res << '\n';
}

int main(){
    int t = read();
    while(t--){
        solve();
    }
    return 0;
}

B. Choosing Cubes

完整代码：

#include<bits/stdc++.h>
using namespace std;

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

void solve(){
    int n = read(), f = read(), k = read();
    vector<int> v(n);
    for(auto &i : v) i = read();
    int x = v[f - 1];
    sort(v.begin(), v.end());
    
    if(n == k){
        cout << "YES" << '\n';
        return;
    }
    if(x > v[n - k - 1]) {
        cout << "YES" << '\n';
        return;
    }
    if(x == v[n - k - 1] && x == v[n - k]){
        cout << "MAYBE" << '\n';
        return;
    }
    else{
        cout << "NO" << '\n';
        return;
    }	
}

int main(){
    int t = read();
    while(t--){
        solve();
    }
    return 0;
}

C. Sofia and the Lost Operations

满足：d 数组中最后一位出现在 b 中；每一位待更新的数都在 d 数组中。

完整代码：

#include<bits/stdc++.h>
using namespace std;

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

void solve() {
    int n = read();
    vector<int>a(n), b(n);
    for (auto& i : a) i = read();
    for (auto& i : b) i = read();
    int m = read();
    vector<int>d(m);
    for (auto& i : d) i = read();

    int ok = 1;
    
    if(find(b.begin(), b.end(), d[m - 1]) == b.end()) {
        ok = 0;
    }
    
    multiset<int> s(d.begin(), d.end()); 
    for(int i = 0; i < n; i++){
        if(a[i] != b[i]){
            if(!s.count(b[i])){
                ok = 0;
            }
            else{
                s.extract(b[i]);
            }
        }
    }
    
    if(ok){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    
}

int main() {
    int t = read();
    while (t--) {
        solve();
    }
    return 0;
}

D. GCD-sequence

枚举删去每一位。

完整代码：

#include<bits/stdc++.h>
using namespace std;

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

void solve(){
    int n = read();
    vector<int> a(n), b(n - 1);
    for(auto &i : a) i = read();
    
    for(int i = 0; i < n - 1; i++){
        b[i] = gcd(a[i], a[i + 1]);
    }
    
    int bad = 0;
    for(int i = 1; i < n - 1; i++){
        bad += b[i] < b[i - 1];
    }
    
    int ok = 0;
    if(bad - (b[1] < b[0]) == 0){
        ok = 1;
    }
    if(bad - (b[n - 2] < b[n - 3]) == 0){
        ok = 1;	
    }
    for (int i = 1; i < n - 1; i++) {
        int tmp = bad;
        tmp -= b[i] < b[i - 1];
        int g = gcd(a[i - 1], a[i + 1]);
        if (i - 1 > 0) {
            tmp -= b[i - 1] < b[i - 2];
            tmp += g < b[i - 2];
        }
        if (i + 1 < n - 1) {
            tmp -= b[i + 1] < b[i];
            tmp += b[i + 1] < g;
        }
        if (tmp == 0) {
            ok = 1;
        }
    }
    if(ok){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

int main(){
    int t = read();
    while(t--) solve(); 
    return 0;
}