题意:

给一个小写字母组成的字符串,每回合轮到某人时,此人可以选择让某位+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 ;
}
05-11 16:04