首页 > 其他分享 >Flexible String

Flexible String

时间:2023-02-03 20:44:22浏览次数:55  
标签:字符 cnt set String 10 int Flexible string

题目链接

题目描述:

You have a string \(a\) and a string \(b\). Both of the strings have length \(n\). There are at most 10 different characters in the string a. You also have a set \(Q\). Initially, the set \(Q\) is empty. You can apply the following operation on the string \(a\) any number of times:

  • Choose an index \(i(1≤i≤n)\) and a lowercase English letter \(c\). Add \(a_i\) to the set \(Q\) and then replace \(a_i\) with \(c\).

For example, Let the string \(a\) be "abecca". We can do the following operations:

  • In the first operation, if you choose \(i=3\) and \(c=x\), the character \(a_3=e\) will be added to the set \(Q\). So, the set \(Q\) will be \(\begin{Bmatrix}e\end{Bmatrix}\), and the string \(a\) will be "ab\(\underline{x}\)cca".
  • In the second operation, if you choose \(i=6\) and \(c=s\), the character \(a_6=a\) will be added to the set \(Q\). So, the set \(Q\) will be \(\begin{Bmatrix}e, a\end{Bmatrix}\), and the string \(a\) will be "abxcc\(\underline{s}\)".

You can apply any number of operations on \(a\), but in the end, the set \(Q\) should contain at most \(k\) different characters. Under this constraint, you have to maximize the number of integer pairs \((l,r) (1≤l≤r≤n)\) such that \(a[l,r]=b[l,r]\). Here, \(s[l,r]\) means the substring of string \(s\) starting at index \(l\)(inclusively) and ending at index \(r\)(inclusively).

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases \(t(1≤t≤10^4)\). The description of the test cases follows.

The first line contains two integers \(n\) and \(k(1≤n≤10^5, 0≤k≤10)\) — the length of the two strings and the limit on different characters in the set \(Q\).

The second line contains the string \(a\) of length \(n\). There is at most \(10\) different characters in the string \(a\).

The last line contains the string \(b\) of length \(n\).

Both of the strings \(a\) and \(b\) contain only lowercase English letters. The sum of \(n\) over all test cases doesn't exceed \(10^5\).

输出描述:

For each test case, print a single integer in a line, the maximum number of pairs \((l,r)\) satisfying the constraints.

样例:

input:

6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb

output:

6
3
6
6
6
11

Note:

In the first case, we can select index \(i=3\) and replace it with character \(c=d\). All possible pairs \((l,r)\) will be valid.

In the second case, we can't perform any operation. The \(3\) valid pairs \((l,r)\) are:

  1. \(a[1,1]=b[1,1]=\) "a",
  2. \(a[1,2]=b[1,2]=\) "ab",
  3. \(a[2,2]=b[2,2]=\) "b".

In the third case, we can choose index \(2\) and index \(3\) and replace them with the characters \(c\) and \(d\) respectively. The final set \(Q\) will be \(\begin{Bmatrix}b\end{Bmatrix}\)having size \(1\) that satisfies the value of \(k\). All possible pairs \((l,r)\) will be valid.

AC代码1:

时间复杂度分析:

在 \(cnt\) 中选 \(k\) 个字符,而所有选择情况都有一个 \(O(n)\) 的时间复杂度,那么也就是最多也就是
\(O(252(C_{10}^5) * n)\)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// 根据题意可知可以在字符串s中选取最多k不同的字符替换成任意其他小写字母
// 要尽可能多的让区间(l, r)使得s[l, r] = z[l, r]
// 那么就可以先将s中不同的字符的个数cnt找出来,在从k和cnt中取最小值,意为最多可以(需要)改变多少个字符
// 然后用0~25代表a~z,把在字符串s出现过的a~z赋予位置
// 之后可以用二进制来表示选取哪些字符,例如011表示选取第一个和第二个位置的字符
// 直接暴力枚举,最终求出答案
void solve()
{
	int n, k;
	cin >> n >> k;

	string s, z;
	cin >> s >> z;

	array<int, 26> f{};

	// 将字符串a中出现的字符标记一下
	for(int i = 0; i < n; i ++)
		f[s[i] - 'a'] ++;

	int cnt = 0;


	for(int i = 0; i < 26; i ++)
		// 大于0代表出现过,让这个字符的位置变为cnt
		if(f[i] > 0)
			f[i] = cnt ++;
		else
			f[i] = -1;

	// k和cnt的大小取最小值
	k = min(k, cnt);
	
	LL ans = 0;

	// 从0~2的cnt次方减1,代表从一个都不选到全选的过程
	for(int i = 0; i < 1 << cnt; i ++)
	{
		// 如果i中的1的个数不等于k那么这种选法就不合法
		if(__builtin_popcount(i) != k)
			continue;

		// 起始位置
		int t = -1;
		LL res = 0;

		for(int j = 0; j <= n; j ++)
		{
			// 如果s和z在这个位置上的字符不相同并且i在这个位置上是0(取反则是1)
			// 就说明没有这个字符不合法,那么就计算一下这个字符之前的区间数量
			// 当j走到最末尾,也要计算一下末尾和t之间是否有还未加上的区间
			if(j == n || (s[j] != z[j] && (~i >> f[s[j] - 'a'] & 1)))
			{
				res += 1LL * (j - t) * (j - t - 1) / 2;

				t = j;
			}
		}

		ans = max(ans, res);
	}

	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int T;
	cin >> T;

	while(T --)
		solve();

	return 0;
}

AC代码2:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 30;

int n, k;
LL ans;
string p, s, z;
bool g[N];
unordered_set<int> q;

// 与上一个代码思路一致,也是枚举每一种选法,但是这里采用递归的方式
LL check()
{
	LL res = 0;

    // 合法字符的数量
	LL count = 0;

	for(int i = 0; i < n; i ++)
	{
        // 这个位置的字符合法,则count加1
		if(s[i] == z[i] || g[s[i] - 'a'])
			count ++;
		else
		{
            // 当前区间的数量
			res += count * (count + 1) / 2;

			count = 0;
		}
	}

	res += count * (count + 1) / 2;

	return res;
}

// pos表示当前递归的下标为pos,此时已经改变了cnt个字符
void dfs(int pos, int cnt)
{
    // 如果已经递归到了最后一个字符并且改变了cnt个字符,则计算此时符合条件的区间数量
    if (pos == q.size())
    {
    	if(cnt == k)
    		ans = max(ans, check());

        return;
    }

    // 递归下一个位置
    dfs(pos + 1, cnt);

    // 将这个位置的字符替换,cnt ++,然后递归下一个位置
    g[p[pos] - 'a'] = 1;

    dfs(pos + 1, cnt + 1);

    // 在回溯的过程中,记得恢复原状
    g[p[pos] - 'a'] = 0;
}

void solve()
{
    cin >> n >> k;

    cin >> s >> z;

    ans = 0;

    q.clear();
    p.clear();
    memset(g, 0, sizeof g);

    // 存字符串s中不同字符
    for (int i = 0; i < n; i++)
        q.insert(s[i]);

    int cnt = 0;

    // p中s中不同的字符
    for (auto j : q)
        p += j;

    // 不用字符的个数和k取最小值
    k = min(k, (int)q.size());

    dfs(0, 0);

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}

标签:字符,cnt,set,String,10,int,Flexible,string
From: https://www.cnblogs.com/KSzsh/p/17090222.html

相关文章

  • Codeforces 1316 B. String Modification
    题意:反转一个字符串,反转规则为从字符串首字母开头,长度为,反转问一个$k$时会得到一个新串,求字典序最小的新串和,如果字典序相同,则输出最小的。比赛时被卡,疯狂,其实举......
  • String_StringBuff_StringBuild的区别
    最近在看面试题,stringbuffer和stringbuild也是经常会问到的,而在写代码的过程中,用到这两者都很少,一般都是string,如果要对字符串经常进行更改,那么stringbuffer和stringbu......
  • CodeForeces 1202D Print a 1337-string(构造)
    求能组成1337这个序列的串最短的串是什么这道题我们很容易想到组合数,我可以有限考虑选择3,因为只有3是两个,这样可以使这个串尽可能的短。但是选择3是不能满足我们组成任意个......
  • 【计算机网络】Stanford CS144 Lab1 : stitching substrings into a byte stream 学
    Puttingsubstringsinsequence实现一个流重组器。可以将带有索引的流碎片按照顺序重组。这些流碎片是可以重复的部分,但是不会有冲突的部分。这些流碎片将通过Lab0中......
  • 常用对象API(String类)
    目录StringBuffer字符串缓冲区特点&添加功能增删改查和可变数组长度StringBuilder类StringBuilder练习:String类String类特点:构造函数字符串常见方法获取转换判断比较inter......
  • C++中char*与string转换
    (1)char*转换为string:直接赋值即可chara[1024]="abcdefg";stringmm=a;(2)求char*(不包含\0)以及string的长度:strlen()函数cout<<"a.size:"<<strlen(a)<<endl;......
  • 将char* 赋值给std::string的一些陷阱
    这段时间,总是要使用char或者char*赋值给std::string,踩了不少坑。于是写了个测试代码,如果你不想看我的代码,可以跳到下面直接看总结:   #include<string> ......
  • 在使用cn.hutool.poi.excel,读取数据读不出String的问题
    今天想用cn.hutool.poi.excel包读取Excel数据,就一列数据,我本想用ExcelReader的readAll方法,并传入参数设置类的类型=String.class,发现没有读出数据且没有报错。经过一路翻......
  • POJ-2406-Power Strings
    PowerStringsTimeLimit:6000/3000ms(Java/Other)   MemoryLimit:131072/65536K(Java/Other)TotalSubmission(s):96   AcceptedSubmission(s):34Probl......
  • LeetCode - 344. Reverse String
    题目Writeafunctionthatreversesastring.Theinputstringisgivenasanarrayofcharacterschar[].Donotallocateextraspaceforanotherarray,youmust......