公式推导+dfs简版

写在前面的话：心可以冷，但手不能停
第一题：C. Flexible String
题目大意：给一个$a$字符串和$b$字符串和数字$k$，首先设置一个计数器$cnt$,其中可以对$a$字符串做以下操作：替换$a$中的一个字母$x$，将字母$x$加入到集合$Q$，如果这个字母已经在集合$Q$中了，则$cnt$不动，否则$cnt++$，记$s[l,r]$为在$[l,r]$区间中$a$和$b$的字母全相等。达到的目标为在$cnt\le k$的情况下，让$s[l,r]$的数量最大。
解题思路： 这个题可以这样想，对于任意一个$a[i]\ne b[i]$，可以将这个位置记作一个断点，被断点隔开的若干个区间可以用这样的形式来表达$s[l,r]$的数量:$len\ast (len+1)/2$,其中len为区间内的字母数量。我们注意到如果将某个满足$a[i]\ne b[i]$的字母加入到集合$Q$中，则区间可能被连上，注意可能断点是由两个字母组成的。这样的话，考虑k最大可能为$10$，则可以用数位$dp$或者$dfs$等，来枚举所有可能性。枚举出一种可能性，之后只要用$O(n)$判断即可，大概是$10^8$这样的级别，那么这里的枚举状态可以用这种形式表达：

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可以做以下操作：可以任选一个数字对其进行反转，问达到两个字符串第一次相等所需要的操作次数期望。
解题思路：
参考文章
代码：

#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);}
}