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();
 }
}

http://www.bkjia.com/cjjc/993293.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/993293.htmlTechArticleYZOI Easy Round 2_回文串 string,yzoiround
原文链接:http://laphets1.gotoip3.com/?id=18 Description
给出一个由小写字母组成的字符串,其中一些字母被染黑…

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

发表评论

电子邮件地址不会被公开。 必填项已用*标注