自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:20:57，当前版本为作者最后更新于2023-05-14 23:10:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目解析

一个取数游戏，有以下规则：

• 第一次取数的玩家可以取任意一个数；

• 第二次取数的玩家只能从上一次取得数的左右两边相邻的两个数中取一个；

• 第三次取数的玩家可以从之前所有取过的任意一个数的左右两边相邻的两个数中取一个；

其中，与第一个数和第 $n$ 个数相邻的只有一个数。

要你统计有多少种必赢的开局。

容易想到破环成链。

$numb_{i,j}$ 表示 $i-j$ 这条链可以从两边开始选，先手能比后手多拿到最多的奇数个数。

也就是说：当 $numb_{i,i} - numb_{i+1, i+n-1} > 0$ 符合时，就统计答案。

$AC$ 码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[110],numb[210][210];cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]%=2;
		numb[i][i]=numb[i+n][i+n]=a[i];
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i<=(n<<1);i++){
			int j=i+l-1;
			if(j>(n<<1)){
				break;
			}
			numb[i][j]=max(numb[i][i]-numb[i+1][j],numb[j][j]-numb[i][j-1]);
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(numb[i][i]-numb[i+1][i+n-1]>0){
			cnt++;
		}
	}
	cout<<cnt;
}