题解

Smile_love · 2023-05-14 23:10:17 · 题解

题目解析

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

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

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

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

容易想到破环成链。

也就是说：当 $numb_{i,i} - numb_{i+1, i+n-1} > 0$ 符合时，就统计答案。 $AC$ 码: ```cpp #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; } ```