Codeforces Round #372 (Div. 2) B. Complete the Word __ two pointers、队列(queue)

Source

Codeforces Round #372 (Div. 2)

My Solution

two pointers、队列(queue)

用 queue que;维护一个除了 '?'以外所有字符最多在该队列中出现一次的队列，当que里的合法元素达到 26 个是就是 nice substring 了。

在这过程中用 map<char, int> ch 维护队列中每个字符出现的次数，且用 ind 维护队列的首元素的在s中的下标。

得到要求的que以后，扫一遍map，把没有出现过的大写字母丢到队列 ans里去，

然后输出 s[ 0 ~ ind-1]，输出 nice substring，输出s[ind + 26 ~ sz -1]。

最开始的时候，脑残的只输出了处理以后的 nice substring。Wrong answer on pretest 6

之后想了很久才发现 (┬＿┬)，其中又有个小注意点，即非nice substring 部分的 '?' 在输出的时候也要用字母代替掉，比如全用'A'。

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 


using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

map<char, int> ch;
queue que, ans;

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 6;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    string s;
    cin >> s;
    int sz = s.size();
    if(sz < 26) cout << -1 << endl;
    else{
        int ptr = 0, ind = 0;

        while(que.size() < 26){ que.push(s[ptr]); ch[s[ptr]]++; while(s[ptr] != '?' && ch[s[ptr]] > 1){
                ch[que.front()]--;
                que.pop();
                ind++;
            }
            ptr++;
            if(ptr >= sz) break;
        }
        if(que.size() == 26){
            for(int i = 0; i < 26 ; i++){
                if(ch[i + 'A'] == 0){
                    ans.push(i + 'A');
                }
            }

            for(int i = 0; i < ind; i++){
                if(s[i] != '?') cout << s[i];
                else cout << 'A';
            }
            while(!que.empty()){
                if(que.front() != '?'){
                    cout << que.front();
                }
                else{
                    cout << ans.front();
                    ans.pop();
                }
                que.pop();
            }
            for(int i = ind + 26; i < sz; i++){
                if(s[i] != '?') cout << s[i];
                else cout << 'A';
            }
            cout << endl;
        }
        else{ cout << -1 << endl;}
    }



    #ifdef LOCAL
    ch.clear();
    while(!que.empty()) que.pop();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #372 (Div. 2) B. Complete the Word __ two pointers、队列(queue)

相关推荐

Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet last数组、预处理、优化

UESTC 1591 An easy problem A ST表、简单题

POJ – 3321 Apple Tree dfs序+线段树简单题

UESTC 1592 An easy problem B 线段树区间合并

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

Codeforces Round #372 (Div. 2) B. Complete the Word __ two pointers、队列(queue)

相关推荐

Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet last数组、预处理、优化

UESTC 1591 An easy problem A ST表、简单题

POJ – 3321 Apple Tree dfs序+线段树 简单题

UESTC 1592 An easy problem B 线段树区间合并

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

POJ – 3321 Apple Tree dfs序+线段树简单题