bLue的字符串游戏
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 所能得到的字典序最大的字符串，每组输出数据占一行。
Example Input
7 CAB JAM CODE ABAAB CABCBBABC ABCABCABC ZXCASDQWE
Example Output
Case #1: CAB Case #2: MJA Case #3: OCDE Case #4: BBAAA Case #5: CCCABBBAB Case #6: CCCBAABAB Case #7: ZXCASDQWE
Hint
Author
「2016级ACM集训队第二次选拔赛」Johsnows
#include <stdio.h>
char a[35];
char b[35];
int main()
{
int t;
scanf("%d", &t);
int e=1;
while(t--)
{
scanf("%s", a);
int i;
int head=16, tail=16;
b[head]=a[0];
for(i=1; a[i]; i++)
{
if(a[i]>=b[head])b[--head]=a[i];
else b[++tail]=a[i];
}
printf("Case #%d: ", e++);
for(i=head; i<=tail; i++)
{
printf("%c", b[i]);
}
printf("\n");
}
}
京公网安备 11010502036488号