AT2153 [ARC064B] An Ordinary Game

题目传送门

结论

根据题意以及我和我妈的多次试验,结论大致如下:

  1. 如果字符串的第一个字符与最后一个字符相等:

    • 字符串长度为偶数第一个人赢

    • 字符串长度为奇数第二个人赢

  2. 如果字符串的第一个字符与最后一个字符不相等:

    • 字符串长度为偶数第二个人赢

    • 字符串长度为奇数第一个人赢

举例验证:

假设现在字符串是“abcab”,第一个人先把“c”删掉,就会形成一个“abab”的字符串,由于字符串的两边无法删除,所以说第二个人无论怎么删都赢不了,第一个人获胜。

我们可以发现当字符串删除到无法删除时总会出现一个只有两个字符交替出现的字符串,因为不可能出现只有一种字符的字符串(不能有相邻的两个字符相等),而且两边的字符无法删除,所以也不会出现只有一个字符的情况。

如果要获胜,就要让对方无论怎么删除都会使两个相同的字符相邻,也就是说要让 $ s_{i-1} = s_{i+1} $ ,即所有奇数下标位置上的字符相同,所有偶数下标位置上的字符相同,并且奇偶交替出现(不懂的可以再看看上面的例子)。

若字符串长度为奇数,则首尾下标都为奇数,若字符串长度为偶数,则首位下标都为偶数。这时若首尾相同,长度为偶数时第一个人必胜。反之,则第二个人必胜。而当首尾不相同时长度为奇数时第一个人必胜。反之,则第二个人必胜。

代码如下:


#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int len=s.size();
    if(s[0]==s[len-1])//如果首尾相同
    {
    	if(len%2==0) cout<<"First"<<endl;//长度为偶数第一个人赢
    	else         cout<<"Second"<<endl;//否则第二个人赢
    	return 0;
	}
	else//如果首尾不相同
	{
		if(len%2==0) cout<<"Second"<<endl;//长度为偶数第二个人赢
		else         cout<<"First"<<endl;//否则第一个人赢
		return 0;
	}
	return 0;
}

上一篇:Split Game翻译


下一篇:【C语言小游戏】扫雷