欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
编程题
P10376 游戏
【题目来源】
洛谷：[P10376 GESP202403 六级] 游戏 - 洛谷
【题目描述】
你有四个正整数 \(n,a,b,c\)，并准备用它们玩一个简单的小游戏。
在一轮游戏操作中，你可以选择将 \(n\) 减去 \(a\)，或是将 \(n\) 减去 \(b\)。游戏将会进行多轮操作，直到当 \(n \leq c\) 时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将 \(n\) 减去 \(a\)，而另一种操作序列选择将 \(n\) 减去 \(b\)。如果 \(a=b\)，也认为将 \(n\) 减去 \(a\) 与将 \(n\) 减去 \(b\) 是不同的操作。
由于答案可能很大，你只需要求出答案对 \(10^9 + 7\) 取模的结果。
【输入】
一行四个整数 \(n,a,b,c\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
1 1 1 1
【输出样例】
1
【算法标签】
《洛谷 P10376 游戏》 #动态规划DP# #深度优先搜索DFS# #记忆化搜索# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int mod = 1e9 + 7; // 模数
const int N = 2e5 + 5; // 最大范围
int n, a, b, c, ans; // n: 初始值, a,b: 减少值, c: 目标范围上限, ans: 答案
int f[N << 1]; // DP数组，大小为2N，通过+N来避免负数下标int main()
{// 输入参数cin >> n >> a >> b >> c;// 初始化：从n开始有1种方案f[n + N] = 1; // 为了防止下标为负数，统一加N偏移量// 从n向下递推到c+1for (int i = 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 (int i = 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;return 0;
}
【运行结果】
114 51 4 1
176
P10377 好斗的牛
【题目来源】
洛谷：[P10377 GESP202403 六级] 好斗的牛 - 洛谷
【题目描述】
你有 \(10^9\) 个牛棚，从左到右一字排开。你希望把 \(n\) 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 \(i\) 头牛的攻击范围是 \((a_i, b_i)\)，这意味着，如果他的左边 \(a_i\) 个牛棚或者右边 \(b_i\) 个牛棚有其他牛，它就会去挑事。
你想留下一段连续的牛棚，并把其他牛棚都卖掉。请问您最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的 \(n\) 头牛都安置进剩余的牛棚里，且没有牛会挑事？
【输入】
第一行一个正整数 \(n\)。
第二行 \(n\) 个正整数 \(a_1, a_2, \dots a_n\)。
第三行 \(n\) 个正整数 \(b_1, b_2, \dots b_n\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
2
1 2
1 2
【输出样例】
4
【算法标签】
《洛谷 P10377 好斗的牛》 #模拟# #搜索# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 牛的数量
int flag[15]; // 标记数组，用于记录牛是否被使用
int a[15]; // 排列数组，存储当前排列的牛的顺序
int minn = 1e9; // 最小总距离，初始化为一个大数struct Node
{int a; // 牛的左边距离int b; // 牛的右边距离
}cow[15]; // 牛的信息数组// 深度优先搜索生成全排列
void dfs(int step)
{// 如果已经排列完所有牛，计算当前排列的总距离if (step > n){int tot = 1; // 初始化总距离，第一头牛需要一个牛棚for (int i = 2; i <= n; i++) // 从第二头牛开始计算{// 计算相邻两头牛之间的栅栏距离// 取左边牛的右边距离和右边牛的左边距离的最大值tot += max(cow[a[i]].a, cow[a[i-1]].b);tot += 1; // 当前这头牛也需要一个牛棚}// 更新最小总距离minn = min(minn, tot);return;}// 生成全排列for (int i = 1; i <= n; i++) // 尝试将每头牛放在当前位置{if (!flag[i]) // 如果这头牛还没有被使用{flag[i] = 1; // 标记为已使用a[step] = i; // 将牛i放在第step个位置dfs(step + 1); // 递归放置下一头牛flag[i] = 0; // 回溯，取消标记}}
}int main()
{// 输入牛的数量cin >> n;// 输入每头牛左边的距离for (int i = 1; i <= n; i++){cin >> cow[i].a;}// 输入每头牛右边的距离for (int i = 1; i <= n; i++){cin >> cow[i].b;}// 从第一个位置开始深度优先搜索dfs(1);// 输出最小总距离cout << minn << endl;return 0;
}
【运行结果】
2
1 2
1 2
4