寫在前面的話：心可以冷，但手不能停
第一題：C. Flexible String
題目大意：給一個$a$字符串和$b$字符串和數(shù)字$k$，首先設(shè)置一個計數(shù)器$cnt$,其中可以對$a$字符串做以下操作：替換$a$中的一個字母$x$，將字母$x$加入到集合$Q$，如果這個字母已經(jīng)在集合$Q$中了，則$cnt$不動，否則$cnt++$，記$s[l,r]$為在$[l,r]$區(qū)間中$a$和$b$的字母全相等。達(dá)到的目標(biāo)為在$cnt\le k$的情況下，讓$s[l,r]$的數(shù)量最大。
解題思路： 這個題可以這樣想，對于任意一個$a[i]\ne b[i]$，可以將這個位置記作一個斷點，被斷點隔開的若干個區(qū)間可以用這樣的形式來表達(dá)$s[l,r]$的數(shù)量:$len?(len+1)/2$,其中l(wèi)en為區(qū)間內(nèi)的字母數(shù)量。我們注意到如果將某個滿足$a[i]\ne b[i]$的字母加入到集合$Q$中，則區(qū)間可能被連上，注意可能斷點是由兩個字母組成的。這樣的話，考慮k最大可能為$10$，則可以用數(shù)位$dp$或者$dfs$等，來枚舉所有可能性。枚舉出一種可能性，之后只要用$O(n)$判斷即可，大概是$10^8$這樣的級別，那么這里的枚舉狀態(tài)可以用這種形式表達(dá)：

for(int i=0;i<1024;i++)

注意，由于我把集合中的字母用$map$映射，所以所有字母不能映射到$0$，否則$wronganswerontest3$
代碼：

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int length = 1e5 + 5;
char a[length];
char b[length];
ll max(ll a, ll b)
{if (a > b)return a;else return b;
}
ll solve(int i, map<char, int> &mp,int n,int k)
{vector<int> flag(20, 0);int q = 0;for (int j = 1; j <= 10; j++){if (i&(1 << j)){flag[j] = 1;q++;}}if(q>k)return 0;int s = 0;ll res = 0;while (s < n){int tmp = s;while (a[s] == b[s]||flag[mp[a[s]]]==1){s++;if (s >= n)break;}int len = s - tmp;res = res + (ll)(len + 1)*len / 2;s++;}return res;}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;int k;scanf_s("%d%d", &n, &k);getchar();//收\nscanf_s("%s", a,sizeof(a));getchar();//收\nscanf_s("%s", b,sizeof(b));getchar();map<char,int> mp;int cnt = 0;for (int i = 0; i < n; i++){if (a[i] != b[i]){if (mp[a[i]] == 0){mp[a[i]] = ++cnt;}}}if (cnt <= k){ll tmp = (ll)n*(n + 1) / 2;printf("%lld\n", tmp);continue;}vector<ll> dp(1500, 0);ll ans = -1;for (int i = 0; i < 1024; i++){ll a=solve(i*2, mp,n,k);ans = max(ans, a);}printf("%lld\n", ans);}
}

第2題：D. Flexible String Revisit
這個題比較有意思
題目大意： 給一個由0和1組成的兩個字符串，對字符串a(chǎn)可以做以下操作：可以任選一個數(shù)字對其進行反轉(zhuǎn)，問達(dá)到兩個字符串第一次相等所需要的操作次數(shù)期望。
解題思路：
參考文章
代碼：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
int mod = 998244353;
const int length = 1e6 + 5;
int f[length][2];
int dp[length];
char a[length];
char b[length];
int ksm(int k)
{int tmp = mod-2;int base = k;int ans = 1;while (tmp){if (tmp % 2 == 1){ans = (ll)ans*base%mod;}base = (ll)base*base%mod;tmp = tmp >> 1;}return ans;
}
int solve(int n, int k)
{f[n][0] = 1;f[n][1] = 1;for (int i = n-1; i >= 0; i--){int now = ((ll)1 - (ll)(n - i)*f[i + 1][1]%mod *ksm(n) % mod + mod) % mod;f[i][0] = ((ll)1 + (ll)(f[i+1][0])*(n-i)%mod*ksm(n) % mod) % mod*ksm(now)%mod;f[i][1] = (ll)i*ksm(n) % mod*ksm(now) % mod;}dp[0] = f[0][0];for (int i = 1; i <= k; i++){dp[i] = (ll)((ll)dp[i - 1] * f[i][1] % mod + f[i][0]) % mod;}return dp[k];
}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);int k = 0;getchar();scanf_s("%s", a,sizeof(a));//a.push_back(t);getchar();scanf_s("%s", b, sizeof(b));getchar();for (int i = 0; i < n; i++){if (a[i] != b[i])k++;}int a1=solve(n, k);printf("%d\n", a1);}
}