【Week8CSP模拟II-B】HRZ 学英语 Gym - 270737D

算法

尺取法

题目描述

给出一个数列，找出数列中第一个出现的位置连续的且由26个字母构成的字符串（26个字母可以任意排列），需要注意的时，‘?’可以替代任何字母。

解题思路

使用尺取法，从第一个26个字符的字符串开始，记录其中每个字母的个数，判断其是否由26个字母构成（即每个字母的个数都小于等于1）；如果不是，则向后推一位（将后一位字母加入并将前一位字母减去即可更改原本的记录），继续判断其是否由26个字母构成；直到找到位置；若到最后仍然未找到，则输出-1。
输出时注意‘?’应用第一个找到字符串中未出现的字母替代已达到输出最小字典序字符串的要求。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int sum[512];
bool ans(int st){
    for(int i='A';i<='Z';i++)
        if(sum[i]>1){
            return 0;
        }
    return 1;
}
int main(){
    string s;
    cin >> s;
    int n = s.length();
    int ansst = -1;
    for(int i=0;i<26;i++){
        sum[s[i]]++;
    }
    for(int i=26;i<=n;i++){
        int st=i-26;
        int nt=i;
        if(ans(st)){
            ansst=st;
            break;
        }
        sum[s[st]]--;
        sum[s[nt]]++;
    }
    if(ansst==-1){
        cout << ansst << endl;
    }
    else{
        for(int i=ansst;i<ansst+26;i++){
            if(s[i]=='?'){
                for(int i='A';i<='Z';i++)
                    if(sum[i]==0){
                        printf("%c",i);
                        sum[i]++;
                        break;
                    }
            }
            else{
                cout<<s[i];
            }
        }
        cout<<endl;
    }
    return 0;
}
    

题目总结

应注意记录字母时的代码，尽可能精简已减少产生错误的可能。
注意输出要求字典序最小。

题目原文

题目描述

瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符‘?’，特殊字符‘?’可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序先按照第一个字母，以A、B、C......Z的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH和SIGHT），那么把短者排在前。例如

AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ

上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。注意，题目要求的是第一个出现的，字典序最小的！

输入格式

输入只有一行，一个符合题目描述的字符串。

输出格式

输出只有一行，如果存在这样的子串，请输出，否则输出-1

样例输入1

ABC??FGHIJK???OPQR?TUVWXY?

样例输出1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

样例输入2

AABCDEFGHIJKLMNOPQRSTUVW??M

样例输出2

-1