As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:


One day, Yuta got a string which contains n letters but Rikka lost it in accident. Now they want to recover the string. Yuta remembers that the string only contains lowercase letters and it is not a palindrome string. Unfortunately he cannot remember some letters. Can you help him recover the string?


It is too difficult for Rikka. Can you help her?

This problem has multi test cases (no more than 20). For each test case, The first line contains a number n(1≤n≤1000). The next line contains an n-length string which only contains lowercase letters and ‘?’ – the place which Yuta is not sure.

For each test cases print a n-length string – the string you come up with. In the case where more than one string exists, print the lexicographically first one. In the case where no such string exists, output “QwQ”.

5
a?bb?
3
aaa

aabba
QwQ

BestCoder Round #37 ($)

hujie   |   We have carefully selected several similar problems for you:  5213 5212 5211 5209 5208 

1001 Rikka with string
如果没有不是回文串的限制可以把所有的?都变成a，这样一定是字典序最小的。而现在有了回文串的限制，我们可以从小到大枚举最靠后的不在字符串正中心的问号选什么，其他的问号依然换成a，显然如果有解，这样一定可以得到字典序最小的解。注意特判没有问号以及问号在正中心的情况。
时间复杂度O(n)
Hack点：pretest挺强的也没有什么能hack的了吧

这题博主，还没有AC（博主太水了），学习一下zzuspy博友的DFS方式......

不管怎样先写个博文先!感谢Acmer zzuspy分享他的源码！

附上原文地址:http://blog.csdn.net/u014355480/article/details/45000903

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char str[1005];
int len;
int flag;

int judge()                                                  //判断是否是回文数!
{
    for(int i = 0; i <= len / 2; i++)
    {
        if(str[i] != str[len - i - 1]) return 1;
    }
    return 0;
}

void dfs(int x)                                                        //DFS！
{
    if(flag == 0) return;                                             //flag=0,即递归出口已到
    if(x == len)
    {
        if(judge())<span style="white-space:pre">						</span>      //如果不为回文数！
        {
            printf("%s\n", str);
            flag = 0;
        }
        return;
    }
    if(str[x] <= 'z' && str[x] >= 'a')                                //不是'?'往下一位搜索
    {
        dfs(x + 1);
        return;
    }

    if(str[x] == '?')
    {
        for(int i = 'a'; i <= 'z'; i++)                               //如果是'?'则按照字典序来全部替换
        {
            str[x] = (char)i;                                   
            dfs(x + 1);                                               //替换之后继续往下一位深搜
            str[x] = '?'; <span style="white-space:pre">					</span>      //因为每一次只判断一个问号，所以深搜完后要还原!
        }
    }
}

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        scanf("%s", str);
        len = strlen(str);
        flag = 1;
        dfs(0);
        if(flag)
        {
            printf("QwQ\n");
        }
    }
    return 0;
}

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
有一天勇太得到了一个长度为n的字符串，但是六花一不小心把这个字符串搞丢了。于是他们想要复原这一个字符串。勇太记得这个字符串只包含小写字母而且这个串不是回文串。然而不幸的是他已经不记得这个字符串中的一些字符了，你可以帮他复原这个字符串吗？
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？

多组数据，数据组数不超过20，每组数据第一行两个正整数n。接下来一行一个长度为n的只包含小写字母和’?’的字符串，’?’表示勇太已经忘了这一个位置的字符了。
1≤n≤103

每组数据输出仅一行一个长度为n的仅包含小写字母的字符串，如果有多种合法解，请输出字典序最小的，如果无解，请输出”QwQ”

5
a?bb?
3
aaa

aabba
QwQ