Codeforces Global Round 26

本文主要是介绍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;
}