CodeForces 716B Complete the Word

题目链接：http://codeforces.com/problemset/problem/716/B

题目大意：

　　给出一个字符串，判断其是否存在一个子串（满足：包含26个英文字母且不重复，字串中有‘？’表示占位符可表示字母），如果存在则输出该字串‘？’位置用替换后的字母代替，其他不在子串中的‘？’用字母代替即可。如果该字串不存在满足条件的子串，则输出-1.

举例：

----------------------------------

input

ABC??FGHIJK???OPQR?TUVWXY?

output

ABCDEFGHIJKLMNOPQRZTUVWXYS

------------

input

ABC??FGHIJK???OPQR?TUVWXY?WW??W

output

ABCDEFGHIJKLMNOPQRZTUVWXYSWWAAW

-------------

input

AABCDEFGHIJKLMNOPQRSTUVW??M

output

-1

--------------------------------------

解题思路：

　　暴力即可。

　　首先判断是否满足长度为26，<26 直接输出 -1.

否则：双重for 扫描，内循环每次从 i -> i+25 即可，如果字符出现的个数+？的个数=26，则该子串满足，则记录左边的下标即可。

然后找出没有出现的字符，放在数组x[]。for循环，从记录下标开始-》下标+25，如果是‘？’，则用x[k++]代替‘？’。替换完子串‘？’，遍历整个字串，如果是‘？’用‘A’代替即可。

然后输出。

-->本次代码写low了。。。见谅。

AC Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=50000+2;
 4 char ca[N];
 5 int main()
 6 {
 7     int i,j;
 8 
 9     while(scanf("%s",ca)!=EOF)
10     {
11 
12         if(strlen(ca)<26)
13         {
14             printf("-1
");
15             continue;
16         }
17         int cut,l,r,w;int dp[500];
18         for(i=0; i<strlen(ca); i++)
19         {
20             memset(dp,0,sizeof(dp));
21             cut=w=l=r=0;
22             for(j=i; j<i+26; j++)
23                 if(ca[j]=='?')w++;
24                 else if(!dp[ca[j]]&&(int)ca[j]!=0)
25                     ++cut,dp[ca[j]]=1;
26             if(cut+w==26)
27             {
28                 l=i;
29                 r=l+25;
30                 break;
31             }
32         }
33         if(r==0)
34         {
35             printf("-1
");
36             continue;
37         }
38         else
39         {
40             char s[26],tem[26];
41             int k=0,x,w;
42             for(x=l; x<=l+25; x++)
43                 if(dp[ca[x]])s[k++]=ca[x];
44             k=0;
45             for(x=0; x<=25; x++)
46             {
47                 int flag=1;
48                 for(w=0; w<strlen(s); w++)
49                 {
50                     if((int)s[w]-'A'==x)
51                     {
52                         flag=0;
53                         break;
54                     }
55                 }
56                 if(flag)tem[k++]=(char)(x+'A');
57             }
58             k=0;
59             for(x=l; x<=l+25; x++)
60                 if(ca[x]=='?')ca[x]=tem[k++];
61             for(i=0; i<strlen(ca); i++)
62                 if(ca[i]=='?')ca[i]='A';
63             puts(ca);
64         }
65     }
66     return 0;
67 }

CodeForces 716B Complete the Word

相关推荐