Xâu bằng nhau

Đề bài

Mô tả

Cho hai xâu ab, đều có độ dài n và chỉ gồm các chữ cái Latin thường, cùng một số nguyên k.

Bạn muốn biến xâu a thành xâu b bằng cách thực hiện một số (có thể bằng 0) thao tác lên a. Mỗi thao tác là một trong hai loại sau:

  • Chọn một chỉ số i (1in1) rồi đổi chỗ aiai+1.
  • Chọn một chỉ số i (1ink+1) sao cho k ký tự liên tiếp ai,ai+1,,ai+k1 đều bằng cùng một ký tự c với c'z', rồi thay tất cả chúng bằng ký tự liền sau c+1 (tức là 'a' thành 'b', 'b' thành 'c', ..., 'y' thành 'z').

Các thao tác chỉ được thực hiện trên xâu a, và có thể thực hiện với số lần tùy ý. Hãy xác định liệu có thể biến a thành b hay không.

Dữ liệu vào

  • Dòng đầu chứa số nguyên t là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm ba dòng:
    • Dòng thứ nhất chứa hai số nguyên nk.
    • Dòng thứ hai chứa xâu a độ dài n.
    • Dòng thứ ba chứa xâu b độ dài n.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra "Yes" nếu có thể biến a thành b, ngược lại in ra "No". Có thể in bằng chữ hoa hoặc thường tùy ý.

Ràng buộc

  • 1t105
  • 2n106
  • 1kn
  • Tổng của n trên tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc
No
Yes
No
Yes
Bộ 2: abba, tăng cặp bb rồi cặp cc... cho đến khi thành azza (đổi chỗ đưa hai ký tự giống nhau cạnh nhau rồi tăng). Bộ 3: chỉ có thể tăng ký tự, không thể giảm zz thành aa. Bộ 4: aaabba, đổi chỗ thành aaaabb rồi tăng dần các cặp để được ddddcc.
3
2 2
aa
cc
4 3
aaaa
dddd
5 5
aaaaa
bbbbb
Yes
No
Yes
Bộ 1: aa tăng thành bb rồi cc. Bộ 2: cần tăng cả 4 ký tự a lên d nhưng mỗi lần chỉ tăng đúng khối 3 ký tự giống nhau, 4 không chia hết cho 3 nên không thể. Bộ 3: cả khối 5 ký tự a được tăng một lần lên b.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0