1451C - String Equality

梦里梦外; 2021-07-16 16:29 252阅读 0赞

[传送门][Link 1]

题意：给出两个字符串a,b，用以下操作：<1>可以交换任意两个相邻字符的位置。<2>可以将连续的K个字符加1，如k=3,则bbbaa,可变为cccaa。最后能将a变为b。

思路：  
对于第一个操作的运用：看到可以交换任意两个相邻字符位置，其实等同于可以给所有字符重新排列，如此我们需要的只是把a的各个字符相应的数量转变为b的各个字符数量即可。

对于第二操作的应用：可以将相邻的K个字符加一，那么我们为了更好的运用，就直接把所有的相同字符排列在一起，然后按字符从‘a’到’z’比较，如果a某低位的字符加上之前剩余可转化字符大于等于b的则可以完成b的相对应的某字符转化，且必须将剩余的某字符转化成下一个字符，这样才可以达到a b对于这个字符数量相等，直到每个字符都可以达成转化则对，具体见代码。

#include<bits/stdc++.h>
        #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
        using namespace std;
        typedef long long ll;
        int sum1[30], sum2[30];
        int main()
        { 
        	FAST;
        	int t;cin >> t;
        	while (t--)
        	{ 
        		int n, k;cin >> n >> k;
        		string str1, str2;cin >> str1 >> str2;
        		memset(sum1, 0, sizeof(sum1));
        		memset(sum2, 0, sizeof(sum2));
        		for (int i = 0;i < str1.size();i++)
        		{ 
        			sum1[str1[i] - 'a' + 1]++;
        			sum2[str2[i] - 'a' + 1]++;
        		}
        		int f = 1, sum = 0;
        		for (int i = 1;i <= 26;i++)
        		{ 
        			if (sum1[i]+sum < sum2[i])
        			{ 
        				f = 0;break;
        			}
        			sum += (sum1[i] - sum2[i]);
        			if (sum % k != 0)//不能整除
        			{ 
        				f = 0;break;
        			}
        		}
        		if (f)cout << "Yes" << endl;
        		else cout << "No" << endl;
        	}
        }

[Link 1]: https://codeforc.es/contest/1451/problem/C