bLue的字符串游戏(sdut3715)&&stl双向队列模板

Problem Description

这不,bLue 巨巨又要出去打比赛了,但是在火车上实在太无聊,于是他和队友 PBH 玩起了字符串游戏。游戏的玩法是这样的,bLue 根据自己已经写好的一个字符串,按次序给出一个字母,bLue 会把第一个字母直接写在纸上,bLue 每给出一个字母,PBH 需要把这个字母加到纸上的字符串中,PBH 可以选择把 bLue 给出的字母放在纸上的字符串的最前面或者最后面。例如,bLue 事先写好的字符串 s=cab,那么他会先在纸上写下的情况有四种:

把 a 放在 c 的前面,把 b 放在 a 的前面,得到字符串 bac;

把 a 放在 c 的前面,把 b 放在 c 的后面,得到字符串 acb;

把 a 放在 c 的后面,把 b 放在 c 的前面,得到字符串 bca;

把 a 放在 c 的后面,把 b 放在 a 的后面,得到字符串 cab;

bLue 的要求是,PBH 最后的得到的字符串字典序最大,但是 PBH 作为已经掌握 kmp,AC自动机,后缀自动机等一系列字符串处理技能的高手,当然不屑于玩这种简单游戏,于是他把这个任务交给了你,让你来替他找到能得到的字典序最大的字符串。

如果你能够找到,他将会奖励你一个 Accepted,并且你可以拿着这个 Accepted 去找他教你 AC自动机, 有木有一点小激动呢!

Input

第一行输入T (1 <= T <= 100),代表 T 组数据。

每组数据输入一个字符串,字符串长度不超过 15。

Output

每组数据输出 Case #x: y。x 代表第几组数据,组数从 1 开始,y 代表 PBH 所能得到的字典序最大的字符串,每组输出数据占一行。

Sample Input

7
CAB
JAM
CODE
ABAAB
CABCBBABC
ABCABCABC
ZXCASDQWE

Sample Output

Case #1: CAB
Case #2: MJA
Case #3: OCDE
Case #4: BBAAA
Case #5: CCCABBBAB
Case #6: CCCBAABAB
Case #7: ZXCASDQWE

stl中的双向队列

deque<***>q;

操作基本与queue相同
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int k=1;k<=t;k++)
    {
        char a[20];
        cin>>a;
        deque<char>q;
        for(int i=0;a[i]!='\0';i++)
        {
            if(q.empty())
            {
                q.push_back(a[i]);
            }
            else if(a[i]>=q.front())
            {
                q.push_front(a[i]);
            }
            else q.push_back(a[i]);
        }
        cout<<"Case #"<<k<<": ";
        while(!q.empty())
        {
            cout<<q.front();
            q.pop_front();
        }
        cout<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注