C. String Equality(思维)

Problem - 1451C - Codeforces

Ashish有两个字符串a和b，每个字符串的长度为n，还有一个整数k。

他想通过对a进行一些（可能是零）操作，将字符串a转换成字符串b。

在一次操作中，他可以

选择一个索引i（1≤i≤n-1）并交换ai和ai+1，或
选择一个索引i（1≤i≤n-k+1），如果ai,ai+1,...,ai+k-1都等于某个字符c（c≠'z'），用下一个字符（c+1）替换每一个，也就是说，'a'被'b'替换，'b'被'c'替换，以此类推。
请注意，他可以进行任何数量的操作，而这些操作只能在字符串a上进行。

帮助Ashish确定在对字符串a进行一些（可能是零）操作后，是否有可能将其转换为b。

输入
第一行包含一个整数t（1≤t≤105）--测试案例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含两个整数n（2≤n≤106）和k（1≤k≤n）。

每个测试用例的第二行包含由小写英文字母组成的长度为n的字符串a。

每个测试案例的第三行包含长度为n的由小写英文字母组成的字符串b。

保证所有测试案例的数值之和不超过106。

输出
对于每个测试案例，如果Ashish能在一些动作后将a转换成b，则打印 "是"，否则打印 "否"。

你可以打印答案的任何字母（大写或小写）。

例子
输入复制
4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc
输出拷贝
没有
是
不
是
注意
在第一个测试案例中，可以证明不可能将a转换成b。

在第二个测试案例中。

"abba" -→inc "acca" -→inc ... -→inc "azza"。

这里 "swap "表示第一种类型的操作，而 "inc "表示第二种类型的操作。

在第四个测试案例中。

"aaabba" --→-swap "aaabab" ---交换 "aaabb" -→inc ... -→inc "ddaabb"  -→inc ... -→inc "dddcc"。

 题解:

根据第一种操作,我们可以任意改变字符串a中字母的位置,

由于只能将小的转化为大的，那么a串要匹配b串，可以考虑从字母’a’开始匹配到字母’z’，每次匹配要求字符串a中可以转化或直接匹配字母数大于等于b中对应字母数。
每次匹配完后，剩下的字母一定要进行转换，因此必须为k倍数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
char a[1000005];
char b[1000005];
int f[5005][5005];
void solve()
{
	int n,k;
	cin >> n >>k;
	cin >> a+1>>b+1;
	map<int,int> f1,f2;
	
	for(int i = 1;i <= n;i++)
	{
		f1[a[i] - 'a'] ++;
		f2[b[i] - 'a']++;
	}
	int f = 0;
	int s = 0;
	for(int i = 0;i < 26;i++)
	{
		s += f1[i];
		if(s < f2[i])
		{
			f = 1;
			break;
		}
		s -= f2[i];
		if(s%k)
		{
			f =1 ;
			break;
		}
	}
	if(f)
	{
		cout<<"No\n";
	}
	else
	{
		cout<<"Yes\n";
	}
}
int main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//aaa
//abb