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：第一次用這個取模闆子欸！