YZOI Easy Round 2_回文串 string，yzoiround

YZOI Easy Round 2_回文串 string，yzoiround

原文鏈接: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();
	}
}