Codeforces Global Round 26

Codeforces Global Round 26

Codeforces Global Round 26

A. Strange Splitting

题意：非空数组的范围定义为该数组的最大值减去最小值，现在给出长度大于$n$的整数数组$a$，将其分成两组，每组至少一个元素，且两组的范围大小不同；

思路：若当前数组极值$x$不为0，则可以任选一个数单独一组范围为0，其余数为一组范围为$x$；

AC code：

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
    vector<char> v(n, 'B');
    if (a[n - 1] - a[0] != 0) {
        v[1] = 'R';
        cout << "YES" << endl;
        for (auto c : v) cout << c;
        cout << endl;
    } else {
        cout << "NO" << endl;
    }
}

B. Large Addition

题意：定义一个数字在5~9之间即大数，若一个正整数的每一位都是大数，则该正整数为大数，给定一个正整数$x$，它是否有可能为两个相同位数的大正整数的和；

思路：

大数之间的运算一定会进位+1，所以两个位数为$n$的正整数相加一定会变成一个$n+1$的正整数；

由此我们可以得知，要想分解为两个大正整数，第一位一定为1，最后一位一定不为9，中间的数一定为5~9两两组合的个位+1;

AC code :

void solve() {
    string s; cin >> s;
    int n = s.size();
    if (s[0] != '1' || s.back() == '9') {
        cout << "NO" << endl;
        return;
    }
    map<char, bool> st;
    for (int i = 5; i <= 9; i ++) {
        for (int j = 5; j <= 9; j ++) {
            int ca = (i + j) % 10;
            st[ca + '0'] = 1;
            st[ca + '0' + 1] = 1;
        }
    }
    for (int i = 1; i < n - 1; i ++) {
        if (!st[s[i] - 1]) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

C1. Magnitude (Easy Version)

题意：

对于一个长度为$n$的数组$a$中，依次对元素$c$=0进行累加，有两种选择，分别为|c+$a_i$|以及c+$a_i$，求出c可能的最大值；

思路：

显然，对于取绝对值的操作，只有当前前缀为负的一个较大值时才会对最终结果产生正向影响，这样的位置只会出现一次，因为当出现多个负值时，只有对最后一个负值取绝对值才能最大化答案，而对于多个正值取绝对值无影响；

所以，我们可以依次枚举当仅对一个元素取绝对值时的结果取最大值，通过一个前缀以及后缀和可以在O(n)实现；

AC code：

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<int> sum(n + 10, 0), sum2(n + 10, 0);
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        ans += a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = n; i >= 1; i --) {
        sum2[i] = sum2[i + 1] + a[i];
    }
    for (int i = 1; i <= n; i ++) {
        ans = max(ans, abs(sum[i]) + sum2[i + 1]);
    }
    cout << ans << endl;
}

C2. Magnitude (Hard Version)

题意：

大体题意同C1，但所求为，求出有多少种不同的操作可以取到最大值；

思路：

首先求出最值为多少，然后还是依次枚举每一位取绝对值时，能否取到这个最值；

当该位取绝对值达到最值时，该位可以对答案进行有效贡献，接下来讨论贡献应该为多少，令当前取绝对值的位为$i$：

• 对于$i$后面的数，无论正负，是否取绝对值，对答案无影响，因为$i$位取绝对值时已经为最值，所以$i$之后位的贡献为$2^{n-i}$；

• 对于$i$之前的数，无论正负，都不能随便取绝对值，否则可能会对当前最值位造成影响，只有当前前缀为正时，才可以取绝对值，

  此时该位可以任意取值，对最值无影响；

  所以可以对做一个前缀和>=0的前缀和cnt，那么$i$之前对答案的贡献为$2^{cnt[i-1]}$；

• 所以若当前位取绝对值可以得到最值，那么对答案的贡献为$2^{n-i+cnt[i-1]}$；

AC code：

int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    } return res;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1), cnt(n + 10, 0);
    vector<int> sum(n + 10, 0), sum2(n + 10, 0);
    int mx = 0, mn = 1e18;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        mx += a[i];
        sum[i] = sum[i - 1] + a[i];
        mn = min(mn, sum[i]);
    }
    for (int i = n; i >= 1; i --) {
        sum2[i] = sum2[i + 1] + a[i];
    }
    for (int i = 1; i <= n; i ++) {
        cnt[i] = cnt[i - 1] + (sum[i] >= 0 ? 1 : 0);
    }
    if (cnt[n] == n) {
        cout << qmi(2, n, MOD) % MOD << endl;
        return;
    }
    for (int i = 1; i <= n; i ++) {
        mx = max(mx, abs(sum[i]) + sum2[i + 1]);
    }
    int ans = 0;
    int t = 0, tt = 0;
    for (int i = 1; i <= n; i ++) {
        int ca = abs(sum[i]) + sum2[i + 1];
        if (ca == mx) {
            int t = n - i + cnt[i - 1];
            ans += qmi(2, t, MOD);
            ans %= MOD;
        }
    }
    cout << ans << endl;
}