CF1673A的题解

osfly / 2023-08-25 / 原文

~~好久没做CF的水题了~~

由于每一个人都以最佳策略进行游戏且Alice先手。

设字符串长度为 \(|s|\)。

我们可以考虑：

\(|s|\) 为偶数，此时Alice可以直接全部取走，不给Bob任何机会 ~~（人心险恶啊）~~。
\(|s|\) 为奇数，此时Alice最多取 \(|s|-1\) 个字符，也就剩下头和尾。

对比头和尾，哪一个大就取哪一个。

注意：

如果长度为 \(1\) 的话，因为Alice只能取偶数长度的字串，所以取走的长度为 \(0\)。这时候，Bob必胜。

特别的，因为Alice先手且使用最佳策略，所以除了长度为 \(1\) 的情况，Alice必胜。

~~（突然觉得Bob好惨~~

code

#include<cstdio>
#include<cstring>
int t;
char s[200010];
int len;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		len=strlen(s+1);
		if(len==1)
			printf("Bob %d\n",s[1]-'a'+1);
		else
		{
			if(len%2==0)
			{
				int sum=0;
				for(int i=1;i<=len;i++)
					sum+=s[i]-'a'+1;
				printf("Alice %d\n",sum);
			}
			else
			{
				int sum=0;
				if(s[1]>s[len])
				{
					for(int i=1;i<=len-1;i++) sum+=s[i]-'a'+1;
					sum-=(s[len]-'a'+1);
				}
				else
				{
					for(int i=2;i<=len;i++) sum+=s[i]-'a'+1;
					sum-=(s[1]-'a'+1);
				}
				printf("Alice %d\n",sum);
			}
		}
	}
	return 0;
}