原文链接:http://laphets1.gotoip3.com/?id=18
Description
给出一个由小写字母组成的字符串，其中一些字母被染黑了，用？表示。已知原来的串不是
一个回文串，现在让你求出字典序最小的可能的串。像’a’,’aba’,’abba’这样对称的串叫做回
文串。
每个测试点有5 组小测试点。
Input
5 行，5 个字符串。
Output
5 行，5 个字符串。若无解，输出”Orz,I can not find it!”
这个题目主要就是利用了一种贪心的思想 总的思路就是先把所有的问号先将用最小的字母'a'来代替 假如说不行的话 就将最后一个问号用b来代替 这样得到的便一定是最优的
接下来便是分类讨论的事了 :
如果这个给出的串没有问号 那么便直接判断这个串是不是回文 如果是的话我们便肯定无法再将其变成回文 这里直接输出ORZ便行 反之如果本来就不是回文 直接输出当前的串即可
接下来 对于只有一个问号的情况 我们便先判断有没有这样一种情况存在 即是否只有一个问号 并且这个问号刚好在这个奇数串的中间位置 如果存在 那么便不需要管这个问号是什么(他对该串是否为回文无影响)那么只需要再做一遍回文的check() 同理进行输出 那么如果这个处于中间的问号之前还有一个或多个问号呢 这是我们只需要再将中间问号之前的那个串再看做一个新串 再次找出他这个串中最后一个问号的所处位置 并把这些所有的问号都代以a 再用check()做一遍 如果还是回文 那么我们便把这个新串里的最后一个问号改成 b 即可
另外,对于不符合以上情况的情况(即这个串不是奇数串 然后有一个及以上的问号) 我们便可直接扫一遍 把所有的问号变成 a 并把最后一个 问号记录下来 并再执行一次check() 如果不是回文 那么当然便是最优解了 此时输出即可 当然如果还是回文 那么同样把新串的最后一位标记变成 b 输出即可 此时则一定为最优解 ......
代码如下:
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=10000;
char s[maxn];
int n,cnt,last;
bool check()
{
for(int i=1;i<=n;i++)
if(s[i]!=s[n+1-i])
return false;
return true;
}
void print()
{
for(int i=1;i<=n;i++)
printf("%c",s[i]);
printf("\n");
}
void work()
{
if(cnt==1)
{
if(check())
printf("Orz,I can not find it!\n");
else
{
s[last]='a';
print();
return;
}
}
int t=0;
for(int i=1;i<last;i++)
if(s[i]=='?')
t=i;
for(int i=1;i<=n;i++)
if(s[i]=='?')
s[i]='a';
if(check())
s[t]='b';
print();
}
void solve()
{
cnt=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='?')
{
cnt++;
last=i;
}
}
if(cnt==0)
{
if(check())
{
printf("Orz,I can not find it!\n");
return;
}
else
{
print();
return;
}
}
if((n&1)&&(last==(n+1)>>1))
{
work();
return;
} for(int i=1;i<=n;i++)
if(s[i]=='?')
s[i]='a';
s[last]='b';
print();
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
for(int t=1;t<=5;t++)
{
scanf("%s",s+1);
n=strlen(s+1);
solve();
}
}