Codeforces Round #848 (Div. 2)（A~D）

A. Flip Flop Sum

给出一个只有1和-1的数组，修改一对相邻的数，将它们变为对应的相反数，修改完后数组的和最大是多少。

思路：最优的情况是修改一对-1，其次是一个1一个-1，否则修改两个1。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int t, n;
int a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}bool flag = false;int ans = 0;for(int i = 1; i < n; i ++) {if(a[i] == -1 && a[i + 1] == -1) {a[i] = 1, a[i + 1] = 1;flag = true;break;}}if(flag) {for(int i = 1; i <= n; i ++) {ans += a[i];}std::cout << ans << '\n';continue;}for(int i = 1; i < n; i ++) {if(a[i] + a[i + 1] == 0) {flag = true;break;}}if(flag) {for(int i = 1; i <= n; i ++) {ans += a[i];}std::cout << ans << '\n';continue;}a[1] = -a[1], a[2] = -a[2];for(int i = 1; i <= n; i ++) {ans += a[i];}std::cout << ans << '\n';}return 0;
}

B. The Forbidden Permutation

给出一个permutation p，给出一个数组a和一个数字d，定义pos(a[i]) = x (a[i] - p[x])，定义一个not good数组满足pos(a[i]) < pos(a[i + 1]) <= pos(a[i]) + d，每次修改可以选择p内两个相邻的数，交换两数位置。求想要达到一个good数组，最少需要修改几次。

思路：贪心求解即可。对于满足条件的相邻两数，不需要操作；对于不满足条件的两个数，可以有两种修改操作：（1）两数位置交换；（2）移动两数使得距离大于等于d，每次在满足条件的情况下采用最小值即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int t, n, m, d;
int a[N], p[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> m >> d;d ++;std::map<int, int> mp;for(int i = 1; i <= n; i ++) {std::cin >> p[i];mp[p[i]] = i;}for(int i = 1; i <= m; i ++) {std::cin >> a[i];}int ans = n;for(int i = 2; i <= m; i ++) {int fir = mp[a[i - 1]];int sec = mp[a[i]];if(fir > sec) ans = std::min(0, ans);else {int cnt = std::max(0, (d - (sec - fir)));if(fir - 1 + n - sec >= cnt)ans = std::min(ans, cnt);ans = std::min(ans, sec - fir);}}std::cout << ans << '\n';}return 0;
}

C. Flexible String

给出长度为n的两个字符串a和b，对a进行修改，每次可以将其中一个字符替换为任意的字符，最多修改k种不同的字符，问修改完后最多有多少区间[l, r]满足a[l, r] = b[l, r]。

思路：因为a中最多有10中字符，可以想到采用二进制枚举，枚举修改k种字符，然后对于修改的区间计算即可，具体细节看代码。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
#define int long long
const int N = 1e5 + 5;
int t, n, k;
std::string a, b;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> k;std::cin >> a >> b;a = ' ' + a, b = ' ' + b;std::map<char, int> mp;int cnt = 0;for(int i = 1; i <= n; i ++) {if(!mp[a[i]])mp[a[i]] = ++ cnt;}int ans = 0;for(int o = 0; o < (1 << cnt); o ++) {int cnt1 = __builtin_popcount(o);if(cnt1 > k) continue;int res = 0;for(int i = 1; i <= n; i ++) {int j = i;while(j <= n && (a[j] == b[j] || mp[a[j]] && (o >> (mp[a[j]] - 1) & 1)))j ++;res += (j - i) * (j - i + 1) / 2;i = j;}ans = std::max(res, ans);}std::cout << ans << '\n';}return 0;
}

os：距离1600还差点啊，，这个二进制枚举没想到QAQ

D. Flexible String Revisit

给出a和b两个01串，随机修改a中的0和1为相反的数，问使得a等于b的期望修改次数是多少。

思路：严格鸽！

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int mod = 998244353;
const int N = 1e6 + 5;
int t, n;
std::string a, b;struct ModInt {int MD = mod;int x;ModInt(ll x = 0) : x(x % MD) {}int get() { return x; }ModInt operator + (const ModInt& that) const { int x0 = x + that.x; return ModInt(x0 < MD ? x0 : x0 - MD); }ModInt operator - (const ModInt& that) const { int x0 = x - that.x; return ModInt(x0 < MD ? x0 + MD : x0); }ModInt operator * (const ModInt& that) const { return ModInt((long long)x * that.x % MD); }ModInt operator / (const ModInt& that) const { return *this * that.inverse(); }void operator += (const ModInt& that) { x += that.x; if (x >= MD) x -= MD; }void operator -= (const ModInt& that) { x -= that.x; if (x < 0) x += MD; }void operator *= (const ModInt& that) { x = (long long)x * that.x % MD; }void operator /= (const ModInt& that) { *this = *this / that; }ModInt inverse() const {int a = x, b = MD, u = 1, v = 0;while(b) {int t = a / b;a -= t * b; std::swap(a, b);u -= t * v; std::swap(u, v);}if(u < 0) u += MD;return u;}
};using mint = ModInt;struct node {mint a, b;
} f[N];node operator + (node L, node R) {return {L.a + R.a, L.b + R.b};
}node operator + (node L, mint R) {return {L.a, L.b + R};
}node operator - (node L, node R) {return {L.a - R.a, L.b - R.b};
}node operator - (node L, mint R) {return {L.a, L.b - R};
}node operator / (node L, mint R) {return {L.a / R, L.b / R};
}node operator * (node L, mint R) {return {L.a * R, L.b * R};
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> a >> b;int cnt = 0;for(int i = 0; i < n; i ++) {cnt += (a[i] != b[i]);}f[0] = {0, 0};f[1] = {1, 0};for(int i = 2; i <= n; i ++) {f[i] = (f[i - 1] - mint{1} - f[i - 2] * mint{i - 1} / n) /((mint{n} - (i - 1)) / n);}node xx = f[n] - f[n - 1];mint x = (mint{1} - xx.b) / xx.a;std::cout << (f[cnt].a * x + f[cnt].b).get() << '\n';}return 0;
}

os：第一次用这个取模板子欸！