参考splay佬的题解写个记录https://zhuanlan.zhihu.com/p/602721281
题意:给定两个字符串a, b,可以选择α里面的字符进行替换,但是替换的字符种类最多为k个。其中字符串α字符出现的种类不超过10种。求将替换后,两个字符的相同部分的数量。(相同部分指的是,指定一个区间[l,r],对应区间相同)
因为字符种类不超过10种,所以可以考虑枚举所有可能的子集,\(2^{10}\) 共1024种,
S相当于是可以替换的位置的二进制表示,1表示可以替换的位置
感觉S中1的位置可以理解为,第k个出现的字母的位置用来替换,比如001就是第一个出现的字母用来替换,010就是第二个出现的字母用来替换,100就是代表第三个出现的字母用来替换。
例子1:
假设字符串 a 为 "xab",字符串 b 为 "xac",k=1。
mp 的值:
mp['x'] = 1
mp['a'] = 2
mp['b'] = 3
现在,我们来分析不同的 S 值代表的含义:
当 S = 0 时,二进制表示为 0000。这意味着没有字符被选为替换字符
当 S = 1 时,二进制表示为 0001。这表示只有字符 'x' 被选为替换字符。
当 S = 2 时,二进制表示为 0010。这表示只有字符 'a' 被选为替换字符。
当 S = 3 时,二进制表示为 0011。这表示字符 'x' 和 'a' 都被选为替换字符。
当 S = 4 时,二进制表示为 0100。这表示只有字符 'b' 被选为替换字符。
当 S = 5 时,二进制表示为 0101。这表示字符 'x' 和 'b' 被选为替换字符。
当 S = 6 时,二进制表示为 0110。这表示字符 'a' 和 'b' 被选为替换字符。
当 S = 7 时,二进制表示为 0111。这表示字符 'x'、'a' 和 'b' 都被选为替换字符。
以此类推,根据不同的 S 值的二进制表示,可以确定哪些字符被选为替换字符,从而决定指针 j 是否能够前进。
上面这8个数中,因为k=1,所以实际上只有4个数能进入循环;
例子2:
考虑a=xbb,b=xac,k=1的情况,有:
当 S = 0 时,二进制表示为 0000。这意味着没有字符被选为替换字符
当 S = 1 时,二进制表示为 0001。这表示只有字符 'x' 被选为替换字符。
当 S = 2 时,二进制表示为 0010。这表示只有字符 'b' 被选为替换字符。
当 S = 3 时,二进制表示为 0011。这表示字符 'x' 和 'b' 都被选为替换字符。
当 S = 4 时,二进制表示为 0100。这表示只有字符 'b' 被选为替换字符。
当 S = 5 时,二进制表示为 0101。这表示字符 'x' 和 'b' 被选为替换字符。
当 S = 6 时,二进制表示为 0110。这表示字符 'a' 和 'b' 被选为替换字符。
当 S = 7 时,二进制表示为 0111。这表示字符 'x'、'b' 和 'b' 都被选为替换字符。
其中,在S=1时,因为x是两个串的相等字符,所以没用到这个1。
S=2时,遍历到a[2] = b的时候,都通过mp找到b对应的值,是2,令2-1=1,然后S右移1位,刚好得1,可以替换,j++=3;而遍历到a[3]=b的时候,同上,满足条件,j++=4;
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define x first
#define y second
const int N = 3e5 + 10,p = 998244353;
typedef pair<char,int> pii;
void solve()
{
int n,k;
string a,b;
cin >> n >> k >> a >> b;
map<char,int> mp;
a = " " + a;
b = " " + b;
int cur = 0;
//对于每个字符 a[i],我们使用 mp[a[i]] 来查找它在映射表 mp 中对应的值。
//如果 mp[a[i]] 的值为 0,说明该字符在映射表中还没有对应的值,即该字符还没有被标记为可替换的字符。
for(int i = 1; i <= n; i ++){
if(!mp[a[i]]) mp[a[i]] = ++cur;
}
int ans = 0;
auto check = [&](int x){
int res = 0;
//check函数,x每次右移i位,然后&1 判断该位是不是1
//总的来说是统计1的个数,用__builtin_popcount()函数也行
for(int i = 0; i <= 10; i ++)
if(x >> i & 1) res ++;
return res;
};
//有最多10种不同字符,因此枚举S相当于2^cur个不同状态
for(int S = 0; S < (1 << cur); S ++){
if(check(S) > k) continue;
int res = 0;
//双指针判断
for(int i = 1; i <= n; i ++){
int j = i;
// 1.相等的
// 2. S >> (mp[a[j]] - 1) & 1 判断该字符是否在替换字符种类中
while(j <= n && (a[j] == b[j] || (mp[a[j]] && (S >> (mp[a[j]] - 1) & 1) ) ) )
j ++;
res += (j - i) * (j - i + 1) / 2;
i = j;
}
ans = max(ans,res);
}
cout << ans <<'\n';
}
signed main() {
int _t;
cin >> _t;
while(_t--)
solve();
return 0;
}