题目大意
- A(Alice)和B (Bob)有一个字符串 \(\texttt s\)(所有字符都是小写字母),他们在玩一个游戏:对于这个字符串 \(\texttt s\),A可以删除其中长度为偶数的一串子串,B则可以删除其中长度为奇数的字串(也可以选择不删)。每次删除都能获得相应的分数,即将删除字串中的字符都累加起来。其中:a 为1,b 为2,c 为3,. . . , z 为26。A先手,轮流操作,每回合只能操作一次。当 \(\texttt s\) 为空时比赛结束,得分高者胜。假设A,B都绝顶聪明,问谁能赢下比赛,并输出两人分差。
思路
因为这是Div.2的A题,所以不会很难,都是思维题。仔细想想,不难发现:每一次消除所得到的分数都是正整数,因为每个字母的分都是正的。所以每一次尽量多选才能让收益最大化,因此作为先手的Alice:
- \(\texttt s\) 长度为偶:一次选完,
干翻Bob。 - \(\texttt s\) 长度为奇:在 \(0\) ~ \(l-2\) 和 \(1\) ~ \(l-1\) 这两个区间之和中取最大值,再与剩下的那个字符之值比较。(\(l\) 为 \(\texttt s\) 的长度。剩下的一个字符就是Bob的得分)。
于是,此题结束,代码奉上。(还有点没说到:他们一共要玩 \(t\) 轮!)。
代码
#include <bits/stdc++.h>
using namespace std;
int t,ans,c1,l,num,sum;
string s;
void sol(){
ans=c1=l=0;//ans记录s的总和。
cin>>s;
l=s.size();
if(s.size()%2==0){//长度为偶直接选完。
cout<<"Alice ";
for(int i=0;i<s.size();++i){
ans+=s[i]-'a'+1;
}
cout<<ans<<'\n';
return;
}
else{
for(int i=0;i<l;++i)ans+=s[i]-'a'+1;
num=s[0]-'a'+1;sum=s[l-1]-'a'+1;//num为第一个字符,sum为最后一个。
if(num>sum){//因为要让Alice的得分最大,所以num和sum哪个大就选哪个。
c1=ans-sum;
if(c1>sum){
cout<<"Alice ";
cout<<c1-sum<<'\n';
return;
}
else{
cout<<"Bob "<<sum-c1<<'\n';
return;
}//判断谁赢谁输。
}
else{//sum>=num同理
c1=ans-num;
if(c1>num){
cout<<"Alice ";
cout<<c1-num<<'\n';
return;
}
else{
cout<<"Bob "<<num-c1<<'\n';
return;
}
}
}
}
int main(){
cin>>t;
while(t--)sol();//一共有t回合
return 0;
}