欧酷网

您的位置:主页>其它>

[codeforces 1303C] Perfect Keyboard 写好一一映射f[x]=y,g[y]=x

[codeforces 1303C] Perfect Keyboard  写好一一映射f[x]=y,g[y]=x

总目录详见

https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址

https://codeforces.com/contest/1303/problem/C

ProblemLangVerdictTimeMemory

C - Perfect Keyboard

GNU C++11Accepted31 ms0 KB

写好一一映射f[x]=y,g[y]=x

开始时有些蒙,想了不切合编写的算法,之后,主动从计算机处理角度思维,对输入自左往右,一个字母一个字母的处理,思路自然而来。

铺开一个空间,将输入中的第一个字母加入开设空间的中间位置,

第二个字母,加在第一个字母的右边,

第三个字母,看是否与前面字母雷同,若是,就不处理......感觉说了些废话,还是用例子来模拟吧,这样看得清楚。

样例YES数据模拟如下

1
codedoca
 YES
edocabfghijklmnpqrstuvwxyz
 模拟如下
加入c          c
加入o          co
加入d          cod
加入e          code
加入d          code
加入o          code
加入c          code
加入a         acode
 acodebfghijklmnpqrstuvwxyz

样例NO数据模拟如下

1
abcda
 NO
 数据模拟如下
 加入a       a
加入b       ab
加入b       abc
加入d       abcd
加入a    按题意,发现加不进
 输出
NO

会想与会编,还是有一定差距的,放在非比赛时期,这样的问题,因该很快就编好,无奈是比赛,种种状况都容易出。

程序编好后,对着样例,突然发现一组数据对不上,怎么回事,提交AC.

事后回看,样例中的输入行与输出行看错位了,比赛时,太容易出状况。

#include <stdio.h>
#include <string.h>
char s[210];
int pos[30],b,a[100],d;
int min(int a,int b){
 return a<b?a:b;
}
int max(int a,int b){
 return a>b?a:b;
}
int main(){
 int t,l,r,len,flag,i;
 scanf("%d",&t);
 while(t--){
  scanf("%s",s+1);
  memset(a,0,sizeof(a)),memset(pos,0,sizeof(pos));
  l=r=50;
  pos[s[1]-'a']=50,a[50]=s[1],l=r=50;
  len=strlen(s+1);
  flag=0;
  for(i=2;i<=len;i++){
   b=pos[s[i-1]-'a'],d=pos[s[i]-'a'];
   if(d){
    if(d==b+1||b==d+1)continue;
    else{
     flag=1;
     break;
    }
   }
   if(a[b+1]==0)a[b+1]=s[i],pos[s[i]-'a']=b+1,r=max(r,b+1);
   else if(a[b-1]==0)a[b-1]=s[i],pos[s[i]-'a']=b-1,l=min(l,b-1);
   else{
    flag=1;
    break;
   }
  }
  if(flag)printf("NO\n");
  else{
   printf("YES\n");
   for(i=l;i<=r;i++)printf("%c",a[i]);
   for(i=0;i<26;i++)
    if(pos[i]==0)
     printf("%c",'a'+i);
   printf("\n");
  }
 }
 return 0;
}

 

 

相关文章推荐