Educational Codeforces Round 59 (Rated for Div. 2)

比赛链接：https://codeforces.com/contest/1107

A. Digits Sequence Dividing

考虑拆分成两个数，第一个数取一位，后面全部取为第二个数保证最优，当只有两个数且第一个小于等于第二个时输出NO

void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        string s; cin >> s;
        if (n == 2) {
            if (s[0] >= s[1]) cout << "NO" << endl;
            else {
                cout << "YES" << endl;
                cout << 2 << endl;
                cout << s[0] << ' ' << s[1] << endl;
            }
        } else {
            cout << "YES" << endl;
            cout << 2 << endl;
            cout << s[0] << ' ';
            for (int i = 1; i < s.size(); i++) cout << s[i];
            cout << endl;
        }
    }
}

B - Digital root

打表发现所有数字都有一个规律，就是从1~9

void solve() {
    int n; cin >> n;
    while (n--) {
        ll k, x; cin >> k >> x;
        cout << x + (k - 1) * 9 << endl;
    }
}

C - Brutality

思路还是比较简单的，直接取每段的最大k个数就可以

int a[N];
char s[N];
vector<int> ve[N];
void solve() {
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> (s + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == s[i-1]) ve[cnt].push_back(a[i]);
        else {
            cnt++;
            ve[cnt].push_back(a[i]);
        }
    }
    for (int i = 1; i <= cnt; i++) sort(ve[i].begin(), ve[i].end(), greater<int>());
    ll ans = 0;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j < min(k, (int)ve[i].size()); j++) ans += ve[i][j];
    }
    cout << ans << endl;
}

D - Compression

如果可以压缩，那么必须满足当前$x*x$方格内的数全部相同，因此记录二维前缀和就可以，然后x必须是n的因子，直接暴力枚举，复杂度就是$O(N^2\sqrt{N})$

int sum[5250][5250], n;
int get(int x1, int y1, int x2, int y2) {
    return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];
}
bool check(int x) {
    for (int i = 1; i <= n/x; i++) {
        for (int j = 1; j <= n/x; j++) {
            int x1 = x*(i-1)+1, y1 = x*(j-1)+1;
            int x2 = i*x, y2 = j*x;
            int ans = get(x1, y1, x2, y2);
            if (ans != 0 && ans != x*x) return false;
        }
    }
    return true;
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n/4; j++) {
            char c; cin >> c;
            int now = 0;
            if (c >= 'A') now = 10 + c - 'A';
            else now = c - '0';
            for (int k = 0; k < 4; k++) {
                sum[i][4*(j-1)+k+1] = now >> (4-k-1) & 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            if (check(i)) ans = max(ans, i);
            if (check(n/i)) ans = max(ans, n/i);
        }
    }
    cout << ans << endl;
}