目录
取数游戏 题目描述 背景 输入 输出 数据范围 题解 解法 优化 打赏取数游戏
题目描述
背景
两人将 n n n个正整数围成一个圆环，规则如下：
第一名玩家随意选取数字； 第二名玩家从与第一名玩家相邻的两个数字中选择一个； 而后依次在到目前为止所取的任何数字旁边取一个数字，直到数字用完，选择更多奇数的玩家获胜第一个选取数字的玩家想知道他能做出多少不同的第一步，使他有机会获胜
输入
第一行一个整数 n n n； 第二行 n n n个整数 n u m i num_i numi，表示围在地上的数字输出
输出一个整数，表示有机会获胜的不同的第一步的数量
数据范围
1 ≤ n ≤ 100 , 1 ≤ n u m i ≤ 1000 1 \le n \le 100 , 1 \le num_i \le 1000 1≤n≤100,1≤numi≤1000
题解
解法
由于要算的是有机会获胜的不同第一步的数量，所以对于每个可能的第一步，只要后续所有选择情况中，第一名玩家获得最多奇数的那一种情况下超过了第二名玩家即可
为此可以定义一个二维数组
f
[
]
[
]
f[][]
f[][]，
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示在第
i
i
i至
j
j
j个数已经被选择后（
i
i
i可以大于
j
j
j），直到所有数都被选择，该过程中第一名得到的奇数最多可超出第二名多少
使用动态规划来更新这个数组，先由大到小枚举已经被选的数的数量
i
(
n
−
1
≥
i
≥
1
)
i(n - 1 \ge i \ge 1)
i(n−1≥i≥1)，再枚举被选数的区间，定义变量
l
,
r
l , r
l,r表示枚举到的区间的左右边界下标，变量
l
l
,
r
r
ll , rr
ll,rr分别表示表示圆环中
l
l
l的前一个数和
r
r
r的后一个数，再根据
i
+
1
i + 1
i+1的奇偶判断接下来是第一名还是第二名玩家选数，这样就得到了状态转移方程：
f
[
l
]
[
r
]
=
m
a
x
(
f
[
l
l
]
[
r
]
±
n
u
m
[
l
l
]
%
2
,
f
[
l
]
[
r
r
]
±
n
u
m
[
r
r
]
%
2
)
f[l][r] = max(f[ll][r] \pm num[ll] \% 2 , f[l][rr] \pm num[rr] \% 2)
f[l][r]=max(f[ll][r]±num[ll]%2,f[l][rr]±num[rr]%2)（
i
+
1
i + 1
i+1为奇时取
+
+
+，反之取
−
-
−）
全部更新完后，统计满足
f
[
i
]
[
i
]
+
n
u
m
[
i
]
%
2
>
0
f[i][i] + num[i] \% 2 > 0
f[i][i]+num[i]%2>0（因为第一个数一定是第一名玩家选的）的
i
i
i有几个即可
代码如下：
#include<cstdio>
#define il inline
const int M = 105;
int f[M][M], num[M];
int main() {
int n, ans = 0;
scanf("%d%", &n);
for(int i = 1; i <= n; ++i) scanf("%d%", &num[i]);
for(int i = n - 1; i >= 1; --i) {
if(i % 2 ^ 1) //等于(i + 1)%2
for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] + num[ll] % 2, s2 = f[l][rr] + num[rr] % 2;
f[l][r] = s1 > s2 ? s1 : s2, r = rr;
}
else for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] - num[ll] % 2, s2 = f[l][rr] - num[rr] % 2;
f[l][r] = s1 < s2 ? s1 : s2, r = rr;
}
}
for(int i = 1; i <= n; ++i) ans += num[i] % 2 + f[i][i] > 0;
printf("%d", ans);
return 0;
}
优化
可以发现全程只用到了
n
u
m
[
i
]
num[i]
num[i]的奇偶性，所以可以在输入时就把
n
u
m
[
i
]
num[i]
num[i]处理成
0
0
0或
1
1
1，这样
n
u
m
[
]
num[]
num[]只需要为
b
o
o
l
bool
bool数组
代码如下：
#include<cstdio>
#define il inline
const int M = 105;
il int read() {
int x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x;
}
bool num[M];
int f[M][M];
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n; ++i) num[i] = read() % 2;
for(int i = n - 1; i >= 1; --i) {
if(i % 2 ^ 1)
for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] + num[ll], s2 = f[l][rr] + num[rr];
f[l][r] = s1 > s2 ? s1 : s2, r = rr;
}
else for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] - num[ll], s2 = f[l][rr] - num[rr];
f[l][r] = s1 < s2 ? s1 : s2, r = rr;
}
}
for(int i = 1; i <= n; ++i) ans += num[i] + f[i][i] > 0;
printf("%d", ans);
return 0;
}
打赏
制作不易，若有帮助，欢迎打赏！
总结
### 文章总结 ——《取数游戏》#### 题目背景
两人围成一个由n个正整数组成的圆环进行取数游戏，规则是第一名玩家随意选一个数字开始，之后每名玩家轮流从上一个被选数字旁边选择一个，直到所有数字被选完，最后选择更多奇数的玩家获胜。首名玩家希望知道有多少种不同的第一步选择能使他有取胜的机会。
#### 输入
- 第一行输入一个整数n（1 ≤ n ≤ 100），代表数字的个数。
- 第二行n个整数，每个整数numi表示环绕地上的一个数字（1 ≤ numi ≤ 1000）。
#### 输出
输出一个整数，表示能使首名玩家获胜的第一步选择的不同数量。
#### 解题思路
1. **定义状态**：使用二维数组f[][]记录从第i至第j个数（i可以大于j，因为圆环结构）被选后，至所有数选取完毕过程中，第一名玩家所得奇数对第二名玩家的超出数量。
2. **状态转移**：
- 由大到小枚举已被选的数的数量i（n-1到1）。
- 对每个i值，枚举所有可能的区间[l, r]（r从l开始逐步增加至i），分别考虑左右边界ll和rr（处理圆环形结构）。
- 基于当前是奇数步（第一名玩家）还是偶数步（第二名玩家）来更新f[l][r]的值，即考虑当前步玩家选择ll还是rr所对应的数量差异更新f[l][r]。
3. **结果计算**：通过统计f[i][i]+num[i]%2大于0的i的数量确定第一步的不同取胜选择数量。
#### 代码实现
- **初步实现**：num使用int数组存储数字原始值，通过num[x]%2取得奇偶性进行比较。
- **优化实现**：将num数组优化为bool数组，仅存储每个数字的奇偶性（1表示奇数，0表示偶数），简化计算过程，减少内存占用。
#### 示例代码（优化后）
```cpp
#include
#define il inline
const int M = 105;
il int read() {
int x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x;
}
bool num[M];
int f[M][M];
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n; ++i) num[i] = read() % 2;
for(int i = n - 1; i >= 1; --i) {
if(i % 2 ^ 1)
for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] + num[ll], s2 = f[l][rr] + num[rr];
f[l][r] = s1 > s2 ? s1 : s2, r = rr;
}
else for(int l = 1, r = i; l <= n; ++l) {
int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;
int s1 = f[ll][r] - num[ll], s2 = f[l][rr] - num[rr];
f[l][r] = s1 < s2 ? s1 : s2, r = rr;
}
}
for(int i = 1; i <= n; ++i) ans += num[i] + f[i][i] > 0;
printf("%d", ans);
return 0;
}
```
#### 小贴士
- 该题通过动态规划的方式求解，并考虑了圆环状结构的特殊性。
- 优化过程中的主要考量为减少不必要的计算和存储占用。
- 打赏提示体现了文章