CF1451C String Equality（数学细心分析，万物皆有规律）

题目描述

Ashish has two strings aa and bb , each of length nn , and an integer kk . The strings only contain lowercase English letters.

He wants to convert string aa into string bb by performing some (possibly zero) operations on aa .

In one move, he can either

choose an index ii ( 1 \leq i\leq n-11≤i≤n−1 ) and swap a_iai and a_{i+1}ai+1 , or

choose an index ii ( 1 \leq i \leq n-k+11≤i≤n−k+1 ) and if a_i, a_{i+1}, \ldots, a_{i+k-1}ai,ai+1,…,ai+k−1 are all equal to some character cc ( c \neqc= 'z'), replace each one with the next character (c+1)(c+1) , that is, 'a' is replaced by 'b', 'b' is replaced by 'c' and so on.

Note that he can perform any number of operations, and the operations can only be performed on string aa .

Help Ashish determine if it is possible to convert string aa into bb after performing some (possibly zero) operations on it.

输入格式

The first line contains a single integer tt ( 1 \leq t \leq 10^51≤t≤105 ) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers nn ( 2 \leq n \leq 10^62≤n≤106 ) and kk ( 1 \leq k \leq n1≤k≤n ).

The second line of each test case contains the string aa of length nn consisting of lowercase English letters.

The third line of each test case contains the string bb of length nn consisting of lowercase English letters.

It is guaranteed that the sum of values nn among all test cases does not exceed 10^6106 .

输出格式

For each test case, print "Yes" if Ashish can convert aa into bb after some moves, else print "No".

You may print the letters of the answer in any case (upper or lower).

题意翻译

本题有多组数据。

第一行输入一个整数 t ，表示数据组数。

对于每组数据：

第一行输入两个正整数  n,k。

第二行输入一个长度为  n 字符串  a。

第三行输入一个长度为  n 字符串  b。

Ashish 会对字符串 aa 进行以下两种操作：

• 选择一个位置  i（ 1≤i≤n−1）并交换  ai 和  ai+1。
• 选择一个位置 i （ 1≤i≤n−k+1），满足 ai,ai+1,…,ai+k−1 都等于某个字符 c （ c！='z'），把 ai,ai+1,…,ai+k−1 都变成 (c+1)。

你需要回答 Ashish 能否通过若干个（可能是零个）操作将字符串  a 变成字符串 b。如果可以，请输出 Yes，否则，输出 No。

输入输出样例

输入 #1复制

4

3 3

abc

bcd

4 2

abba

azza

2 1

zz

aa

6 2

aaabba

ddddcc

输出 #1复制

No

Yes

No

Yes

题目分析，我们可以看成相同字符是排在一起的，然后他们每个字符还是%k=0的，以及后面的字符比前面的大；所以我们i=25循环到i=0，我们可以得到

        rep(i,1,n) aa[a[i]-'a']++;
        rep(i,1,n) aa[b[i]-'a']--;
        int now=0;bool flg=1;
        per(i,25,0) {
            now-=aa[i];
            if(now<0||aa[i]%k!=0) 
      {flg=0;break;}

所以我们就可以知道了，我们把不符合的条件模拟出来，并且标记

完整代码；

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n,k;
char a[1000005],b[1000005];
int aa[26];
int main(){
    for(scanf("%d",&_);_;--_) {
        scanf("%d%d",&n,&k);
        scanf("%s%s",a+1,b+1);
        memset(aa,0,sizeof(aa));
        rep(i,1,n) aa[a[i]-'a']++;
        rep(i,1,n) aa[b[i]-'a']--;
        int now=0;bool flg=1;
        per(i,25,0) {
            now-=aa[i];
            if(now<0||aa[i]%k!=0) 
      {flg=0;break;}
        }
        if(flg) //=1
    puts("Yes");
        else puts("No");
    }
}