首页 > 其他分享 >CF1778C - Flexible String 二进制枚举、状态压缩

CF1778C - Flexible String 二进制枚举、状态压缩

时间:2023-06-18 22:33:33浏览次数:42  
标签:表示 字符 CF1778C String 被选为 二进制 mp Flexible 替换

参考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;
}

暂时写这么多,以后要是有想法再修改

标签:表示,字符,CF1778C,String,被选为,二进制,mp,Flexible,替换
From: https://www.cnblogs.com/neko-yingying/p/17489907.html

相关文章

  • C++面试八股文:std::string是如何实现的?
    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面:面试官:std::string用过吧?二师兄:当然用过(废话,C++程序员就没有没用过std::string的)。面试官:std::string("hello")+"world"、"hello"+std::string("world")和std::string("hello")+std::string("world")的......
  • C++面试八股文:std::string是如何实现的?
    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面:面试官:std::string用过吧?二师兄:当然用过(废话,C++程序员就没有没用过std::string的)。面试官:std::string("hello")+"world"、"hello"+std::string("world")和std::string("hello")+std::string("world")的......
  • mysql:报错Incorrect string value:’\xF0\x9F\x94\xA6\xF0\x9F…’
     一,报错信息:1,报错:Incorrectstringvalue:'\xF0\x9F\x94\xA6\xF0\x9F...'forcolumn'content'atrow1报错的原因:字符串中包含了emoji表情:如:......
  • request超出了配置的maxQueryStringLength
    整个URL的长度为966个字符,经过研究,似乎maxQueryStringLength的默认值是2048<security><requestFiltering><requestLimitsmaxQueryString="2048"></requestLimits></requestFiltering></security>在项目的根web.config中的system.web节点下:&......
  • 题解 CF1830C【Hyperregular Bracket Strings】
    卡特兰数一个长为\(2n\)的序列,填入括号,有多少种合法方案?\(C_n=\sum_iC_iC_{n-i-1}\),其中\(C_0=C_1=1\)。它的封闭形式是\(C_n=\binom{2n}{n}-\binom{2n}{n-1}\)。problem给定一个长度\(n\)和\(k\)个子区间\(\{[l1​,r1​],[l2​,r2​],…,[lk​,rk​]\}\)。问有多......
  • Day08-异常机制、包装类、String-StringBuffer-StringBuilder比较
    异常机制异常处理5个关键字:try、catch、finally、throw、throws注意点假设要捕获多个异常,异常类型从小到大try监控区域,catch(想要捕获的异常类型!)捕获异常finally处理善后工作,可以不要finallythrow主动抛出异常throws在方法上捕获异常 包装类包装类(I......
  • QString::section详解
    目录section()函数简介section()声明start,end含义flags参数示例section()函数简介网上有很多关于Qt中字符串工具函数QString::section的描述,但大多描述不够清晰、直接。本文从官方文档入手,详细讲解如何使用section。QString::section可用来分隔字符串,与QString::split区别是......
  • request超出了配置的maxQueryStringLength
    整个URL的长度为966个字符,经过研究,似乎maxQueryStringLength的默认值是2048<security><requestFiltering><requestLimitsmaxQueryString="2048"></requestLimits></requestFiltering></security>在项目的根web.config中的system.we......
  • CString和char[]互转
    只有以NULL结尾的char[]才能强制转换为CString,即可以直接等于,否则需要通过Format函数char charArray[]="this C++";CString res;res.Format("%s",charArray); ......
  • js中substring
    js中substring主要用于切割字符串,我用的很少,最近再看源码的时候看到了substring,用的也比较少,积累一下例:letstr='abcdefg'str=str.substring(4);console.log(str)//输出'efg'直接截取一个想要的长度,从开头截取,并返回一个被截取之后得的值......