Codeforces Globle Round 26

6月9日 Codeforces 实战记录。（1425 -> 1438）

AC数3/9。
比赛跳转：Codeforces Globle Round 26

开场卡在了 B 题，而且到最后都没有过掉 B 题。
看完 tutorial 感觉自己 naive 的可怕。

题解

A. Strange Splitting

分析：由于 n >= 3 ，只有在所有数相同时，不存在符合条件的情况。
否则，任取中间的一个数为一色，range = 0，其他数取另一色，range > 0。

完整代码：

#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>v(n);
    for(auto &i : v) i = read();
    
    if(v[0] == v[n - 1]){
        cout << "NO" << '\n';
        return;
    }
    
    string s(n, 'R');
    s[1] = 'B';
    cout << "YES" << '\n';
    cout << s << '\n'; 
}

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

B. Large Addition

分析：两个 large 数相加，满足：首位是 1，个位是 0-8，其他位是 1-9。

完整代码：

#include<bits/stdc++.h>
#define int long long
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 x = read() + 1; 
    
    while(x >= 10){
        if(x % 10 == 0){
            cout << "NO" << '\n';
            return;
        }
        x /= 10;
    }
    
    cout << ((x == 1) ? "Yes" : "NO") << '\n';
}

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

C1. Magnitude (Easy Version)

分析：dp，维护每一步后的最大值和最小值。
状态转移：最小值是前一步的最小值 +a；最大值是 max(前一步的最大值 + a，最小值的绝对值)

完整代码：

#include<bits/stdc++.h>
#define int long long 
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>zmax(n + 1), fmax(n + 1);
    for(int i = 1; i <= n; i++){
        int a = read();
        fmax[i] = fmax[i - 1] + a;
        zmax[i] = max(zmax[i - 1] + a, abs(fmax[i]));
    }
    cout << zmax[n] << '\n';
}

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

C2. Magnitude (Hard Version)

分析：记录方案数，根据上一问的状态转移做相应的状态转移即可。

完整代码：

#include<bits/stdc++.h>
#define int long long 
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;
}

const int mod = 998244353;

void solve() {
    int n = read();
    vector<int>zmax(n + 1), fmax(n + 1), cntz(n + 1), cntf(n + 1);
    cntz[0] = cntf[0] = 1;
    for (int i = 1; i <= n; i++) {
        int a = read();
        fmax[i] = fmax[i - 1] + a;

        cntf[i] = cntf[i - 1];
        if (fmax[i] >= 0)
            cntf[i] = (cntf[i] * 2) % mod;

        zmax[i] = max(zmax[i - 1] + a, abs(fmax[i]));

        if (zmax[i - 1] == fmax[i - 1]) {
            cntz[i] = cntf[i];
        }
        else {
            if (zmax[i] == -fmax[i]) {
                cntz[i] = cntf[i];
            }
            if (zmax[i] == zmax[i - 1] + a) {
                cntz[i] = (cntz[i] + 2 * cntz[i - 1]) % mod;
            }
        }

    }
    cout << cntz[n] << '\n';
}

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

ELSE

发现了一个很有意思的人。