本文主要是介绍A. Déjà Vu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思想：构造非回文字符串---->维护一对位置对称，但字符不同的字符对
对于所给的字符串有两种可能
①是回文字符串
可以考虑从左到右遍历，找到不是‘a’的字符对的那个字符的位置插入’a’，替代掉了 原本对称的字符对其中的一个字符的位置，并且这个字符对不是’a’所以自然插入后就不在是回文了
比如
baab 变成 abaab
如果找不到这个位置，说明这个回文都是’a’输出"NO"就行
②已经不是回文字符串
不能用上个方法，比如题目给的最后一个样例
nutforajaroftuna 变成 anutforajaroftuna 就成了回文
所以不能这样,但可以继续用那个思想，很明显这个字符已经不是回文了，也就是至少有一对位置对称，但不相等的字符对，那么就让插入的这个字符’a’不影响这个字符对，这样得到最终的字符串就还是非回文的。
所以从左到右找到这对字符，把’a’插到这对字符的中间即可，这样就不影响这对字符的对称性了
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){int T;string s;cin >> T;for(int t = 0;t < T;t++){cin >> s;int n = s.size();int k;if(n&1) k = n/2 + 1;else k = n/2;int flag = 0;for(int i = 0;i < k;i++){if(s[i] != s[n - i - 1]){//不是回文s.insert(i+1,"a");cout << "YES" << endl;cout << s << endl;flag = 1;break;}else if(s[i] != 'a'){//是回文s.insert(i,"a");cout << "YES" << endl;cout << s << endl;flag = 1;break;}}if(flag)continue;cout <<"NO" << endl;}//system("pause");return 0;
}
这篇关于A. Déjà Vu的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
