100 分题目
题目描述 抢 7 游戏
A、B 两个人玩抢 7 游戏，游戏规则为：
A 先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B 报下一个数字 Y （X - Y
< 3），A 再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到 7，抢到 7
即为胜者；
在 B 赢得比赛的情况下，一共有多少种组合？
输入描述
起始数字 M
10 ≤ M ≤ 10000
输出描述
B
能赢得比赛的组合次数
用例
输入
10
输出
1
说明
只有一种赢的组合，A 起始选择 10，B 接着选择 9，A 接着选择 8，B 接着选择 7
赢得胜利。
解题思路
游戏由两位玩家
A
和
B
进行，其中
A
先报数，
B
跟报数，以此类推，直到某一方
报出数字
7
为止。
报数的规则是，每一次报出的数字必须比前一次报出的数字小，且两数之差小于
3
（即每次至少减
1
，最多减
2
）。
解题步骤
初始化动态规划数组：
创建两个数组
dpA
和
dpB
，长度为
M+2
。这两个数组分别用于存储在每个可能的
游戏状态下，
A
和
B
赢得游戏的方式的数量。数组长度之所以选择
M+2
，是为了
处理边界条件，避免在计算时数组越界。
基础状态设定：
dpA[M]
被初始化为
1
，意味着如果游戏从
M
开始，且轮到
A
报数，
A
有一种方
式直接赢得游戏 ，直接喊。
动态规划递推关系：
从
M-1
开始递减至
6
，迭代计算每个状态下
A
和
B
赢得游戏的方式的数量。这个
迭代过程基于游戏的规则：每次报数至少减
1
，最多减
2
。
对于玩家
B
，在状态
i
下赢得游戏的方式的数量等于
A
玩家在状态
i+1
和
i+2
下赢
得游戏的方式的数量之和。这表示，如果
B
要赢，
A
在接下来的两个状态（
B
的
可能报数）中必须无法赢得游戏。
同理，对于玩家
A
，在状态
i
下赢得游戏的方式的数量等于
B
玩家在状态
i+1
和
i+2
下赢得游戏方式的数量之和。这表示，
A
的胜利依赖于
B
在接下来的两个状
态中的报数。
当用例输入为
10
时，可以通过模拟计算过程来理解动态规划数组如何更新。下
面是详细的步骤：
初始状态
输入
M = 10
。
初始化
dpA
和
dpB
数组，每个数组的大小为
M+2 = 12
，以便能访问到
dpA[10+1]
和
dpA[10+2]
而不越界。
初始时，
dpA[10] = 1
，因为
A
玩家从
10
开始并且直接结束游戏（这里的游戏规
则简化处理，实际上如果
M
不是
7
，
A
并不能在起始步骤赢得游戏，但这是按照
代码逻辑的初始化）。
计算过程
从
M-1=9
开始向下计算到
7
，更新
dpB
和
dpA
数组。
i = 9
：
dpB[9] = dpA[10] + dpA[11] = 1 + 0 = 1
。这表示
B
在
9
的状态下赢得游戏的方式有
1
种，即
A
在下一步选择
10
或
11
（实际上不可能选择
11
，但按初始化条件）。
dpA[9] = dpB[10] + dpB[11] = 0 + 0 = 0
。因为
B
不能直接从
10
或
11
状态赢得游戏，
所以
A
在
9
状态的胜利方式为
0
。
i = 8
：
dpB[8] = dpA[9] + dpA[10] = 0 + 1 = 1
。
B
在
8
的状态下赢得游戏的方式有
1
种，即
A
在下一步选择
9
或
10
。
dpA[8] = dpB[9] + dpB[10] = 1 + 0 = 1
。
A
在
8
状态的胜利方式有
1
种，即
B
在下一
步选择
9
或
10
。
i = 7
：
dpB[7] = dpA[8] + dpA[9] = 1 + 0 = 1
。
B
在
7
的状态下赢得游戏的方式有
1
种，即
A
在下一步选择
8
或
9
。
结果
最终，
dpB[7]
的值为
1
，这意味着在起始数字为
10
的情况下，
B
能赢得比赛的组
合次数为
1
种。
C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//
字符串表示的大数加法函数
//
参数
a
和
b
分别为两个大数的字符串表示
string addBigNumbers(const string &a, const string &b) {
string result; //
用于存储加法结果的字符串
int carry = 0; //
进位，初始为
0
int i = a.size() - 1, j = b.size() - 1; //
分别设置两个指针指向
a
和
b
的最后一个
字符（即最低位）
while (i >= 0 || j >= 0 || carry) { //
当任一字符串未遍历完或存在进位时循环
int sum = carry; //
当前位的和，初始为进位值
if (i >= 0) sum += a[i--] - '0'; //
如果
a
未遍历完，加上
a
当前位的值，并
将指针
i
向前移动
if (j >= 0) sum += b[j--] - '0'; //
如果
b
未遍历完，加上
b
当前位的值，并
将指针
j
向前移动
result.push_back(sum % 10 + '0'); //
将当前位的和模
10
的结果转为字符
后加到结果字符串中
carry = sum / 10; //
计算新的进位
}
reverse(result.begin(), result.end()); //
将结果字符串反转，因为加法是从低位
到高位进行的
return result;
}
int main() {
int M; //
用于存储输入的整数
M
cin >> M; //
从标准输入读取整数
M
