题意:
给一个小写字母组成的字符串,每回合轮到某人时,此人可以选择让某位+1(如果是z则变回a),或者直接结束游戏。
先手希望游戏结束时字符串字典序尽量小,后手希望游戏结束时字符串字典序尽量大,求游戏结束时的字符串。
题解:
定理0:先手只能操作z
证明:如果先手操作非z元素,后手直接结束游戏,对于先手而言,局面一定比先手直接结束游戏更劣。
定理1:后手不应操作字符串的前导y
证明:
(1)假设轮到后手时字符串呈如下状态:yyyyy*****
(2)如果后手操作了某个y,此时字符串变成了这样:yyzyy*****
(3)先手可以操作z:yyayy*****
(4)如果后手再操作此a后面的字符,则先手直接结束游戏,否则先手将刚刚被操作,变成z的字符再操作一次变成a,此时则回到了情况(3)或者后手也可以直接结束游戏,无论何种情况,局面对于后手而言都劣于(1)
定理2:如果字符串中的第一个z前面有字符且不全是y,则先手应该直接结束游戏
证明:
(1)不妨假设轮到先手时,字符串呈如下状态:yabz****
(2)如果先手操作了某个z,变成yaba****
(3)则由定理1,后手可以操作第一个非y字符,且这个字符一定在z前面,变为ybba****
(4)如果此时a直接结束游戏,对于先手局面一定比(1)更劣。如果先手选择操作,那么无论先手操作什么,后手都直接结束游戏,对于先手而言局面一定比(1)更劣。
定理3:如果字符串最前若干个是y,紧接着是z,如yyz***,则先手能获得的最好局面是yyb***
(1)如果先手操作后面的z,后手直接结束游戏,对于先手局面一定比yyb***更劣
(2)先手操作第一个z,变为yya***后,如果后手选择结束游戏,或者后手操作其他非y元素,先手结束游戏,则局面定比yyb***对后手更劣
(3)所以后手只能操作a,将之变为yyb***
(4)此时若没有z,则根据定理0先手应直接结束游戏,若后面有z,则根据定理2先手应直接结束游戏。
定理0,2,3列出了先手开局时所有可能遇到的三种情况,模拟即可。
#include<iostream>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
char s[];
scanf("%s",s);
for(int i=;s[i]!='\0';i++){
if(s[i]<'y'){
printf("%s",s+i);
break;
}
if(s[i]=='y')printf("y");
if(s[i]=='z'){
printf("b%s",s+i+);
break;
}
}
printf("\n");
}
return ;
}