GESP认证C++编程真题解析 | P10376 [GESP202403 六级] 游戏-深圳市維司達科技有限公司

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P10376 GESP202403 六级] 游戏 - 洛谷

【题目描述】

你有四个正整数n , a , b , c n,a,b,cn,a,b,c，并准备用它们玩一个简单的小游戏。

在一轮游戏操作中，你可以选择将n nn减去a aa，或是将n nn减去b bb。游戏将会进行多轮操作，直到当n ≤ c n \leq cn≤c时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n nn减去a aa，而另一种操作序列选择将n nn减去b bb。如果a = b a=ba=b，也认为将n nn减去a aa与将n nn减去b bb是不同的操作。

由于答案可能很大，你只需要求出答案对10 9 + 7 10^9 + 7109+7取模的结果。

【输入】

一行四个整数n , a , b , c n,a,b,cn,a,b,c。

【输出】

输出一行一个整数表示答案。

【输入样例】

1 1 1 1

【输出样例】

【算法标签】

《洛谷 P10376 游戏》 #动态规划DP# #深度优先搜索DFS# #记忆化搜索# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintmod=1e9+7;// 模数constintN=2e5+5;// 最大范围intn,a,b,c,ans;// n: 初始值, a,b: 减少值, c: 目标范围上限, ans: 答案intf[N<<1];// DP数组，大小为2N，通过+N来避免负数下标intmain(){// 输入参数cin>>n>>a>>b>>c;// 初始化：从n开始有1种方案f[n+N]=1;// 为了防止下标为负数，统一加N偏移量// 从n向下递推到c+1for(inti=n;i>c;i--){// 转移方程1：从i可以通过减a到达i-af[i-a+N]=(f[i-a+N]+f[i+N])%mod;// f[i-a] += f[i]// 转移方程2：从i可以通过减b到达i-bf[i-b+N]=(f[i-b+N]+f[i+N])%mod;// f[i-b] += f[i]}// 统计f[0]到f[c]的所有方案数之和for(inti=0;i<=N+c;i++)// 注意：这里应该是i <= c，但代码中有偏移{// 实际上，由于偏移N，f[i]对应原f[i-N]// 循环中的i是实际下标，需要减去N// 但代码直接累加f[i]，这意味着i的范围是0到N+c// 这似乎有问题ans=(ans+f[i])%mod;}// 输出结果cout<<ans<<endl;return0;}