【T1T2】hrz学英语

题解

从序列左边开始，下标不断右移，若当前字母没有被访问过，标记，记录字母在子串中的位置，并加入子串序列；若当前字母被访问过，那么意味着原先序列中，与该字母相同的字母和它之前的所有字母都是无效的，故将它们踢出子串，维护标记数组和位置数组。特别的，字符’?‘直接加入序列，不必判断。重复以上操作，直到遍历完所有字符，或者子串长度到达26.
若最终的子串长度不足26，输出-1.否则，对于子串中为’?'的字符，按顺序填充标记数组中未标记字符。

注意下标和字母的映射。

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<list>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mem(a,s) memset(a,s,sizeof(a))
list<char> a;
int main(){
    //freopen("in.txt", "r", stdin);
    bool b[26];mem(b, false);
    int index[26];//下标
    char x;//序列
    while(cin>>x){
        int xi = x - 'A';
        if(x == '?')
            a.push_back(x);
        else if(b[xi]){
            rep(i,0,index[xi])
                b[a.front()-'A']=0,a.pop_front();
            b[xi] = 1;
            a.push_back(x);
            int sum=0;
            for(auto v:a){
                index[v - 'A'] = sum;
            sum++;
            }

        }else
            b[xi] = 1, index[xi] = a.size(), a.push_back(x);
        if(a.size()==26)
            break;
    }
    if(a.size()!=26)cout<<-1;
    else{
        int tt = 0;
        char c[26];
        rep(i, 0, 25) 
        if (!b[i])
            c[tt++] = char(i + 'A');
        tt = 0;
        for(auto v:a)
        if(v=='?')
            cout << c[tt++];
        else cout << v;
    }
    return 0;
}