Link Sub: http://www.spoj.com/PTIT/problems/P175SUMA/
Người Gửi: Dương Lee
- Problem:
Cho 1 xâu kí tự s với độ dài n. 1 phép biến đổi trên xâu sẽ thay thế 1 kí tự của xâu thành 1 kí tự khác. Với mỗi vị trí trên xâu s chỉ được thực hiện không quá 1 phép biến đổi. Hãy xác định xem sau k phép biến đổi nào đó, sâu s có thể trở thành 1 xâu palindrome hay không. 1 xâu kí tự là xâu Palindrome nếu xâu đó đọc từ phải sang trái cũng giống như đọc từ trái sang phải.Input
Dòng đầu tiên gồm 2 số tự nhiên n, k (1 ≤ n ≤ 105, 0 ≤ k ≤ 105) là độ dài của xâu kí tự s và số phép biến đổi.
Dòng tiếp theo chứa xâu kí tự s.
Output
In ra “Yes” (không có dấu ngoặc kép) nếu sau k phép biến đổi bất kì, xâu s có thể trở thành xâu Palindrome, ngược lại in ra “No”.
Example:
In ra “Yes” (không có dấu ngoặc kép) nếu sau k phép biến đổi bất kì, xâu s có thể trở thành xâu Palindrome, ngược lại in ra “No”.
Input
3 1
abc
Output:
Yes
Input
4 1
abba
Output:
No
- Solution:
Input
4 1
abba
Output:
No
Bài này dễ hiểu nhất là VD thôi: VD1: aaggbc (k=2) -> ta thấy có thể chuyển thành các xâu đối xứng như: cbggbc (a->c, a->b), aaggaa (b->a, c->a), abggba (c->a, a->b),... -> Vậy chỉ cần có thể chuyển tất các cặp kí tự đối xứng nhau cho nó giống nhau (với k) thì sẽ có thể chuyển thành xâu đối xứng. -> Đếm các cặp giống nhau đối xứng, khác nhau đối xứng VD2: abvvqe (k=4) diff_pair = 2 cặp, same_pair = 1 cặp; Ta có các thay đổi sau (thay 1 phần hoặc thay cả cặp): - thay a + thay b + thay cặp vv -> eqggqe - thay căp ae + thay cặp bq -> dlvvld - thay ... Có rất nhiều cách thay... -> Ta sẽ xét tính toán số lượng kí tự có thể thay đổi (change=1*i+(diff_pair-i)*2; i:0->diff_pair) TH1: change = k thì chắc chắn sẽ chuyển đổi được. TH2: change < k (điều này có nghĩa là đã thay hết toàn bộ các kí tự khác nhau và còn thừa k-change kí tự) giờ thì chỉ cần kiểm tra xem số kí tự còn lại có đủ để thay các cặp giống nhau không. (Chú ý: độ dài xâu lẻ thì thoải mái thay đổi các cặp giống nhau)