CCPC题目
文章目录
- **题目1：网格路径计数（动态规划·中等）**
- *题目描述**
- **题目2：最短环路（图论·较难）**
- **题目描述**
- **题目3：区间众数（数据结构·中等偏难）**
- **题目描述**
- **题目4：异或方程组（数学·难题）**
- **题目描述**
- **题解**
- ** 题目5、中等题：动态规划（背包变形）
- **题目名称**：分割等和子集
- **题目6 简单题：贪心/模拟**
- **题目名称**：任务调度器
题目1：网格路径计数（动态规划·中等）
题目描述*
在n×m的网格中，某些格子有障碍物。每次只能向右或向下移动，求从左上角到右下角的路径数。答案对10^9+7取模。
输入：
- 第一行：n,m（1≤n,m≤1000）
- 接下来n行：网格矩阵（
.表示空地，#表示障碍）
输出：路径数，若不可达输出0。
示例：
输入：
3 3
...
.#.
...
输出：2
命题意图：考察基础DP模型和取模运算的细节（避免负数）。
题目2：最短环路（图论·较难）
来源参考：类似2021年四川省赛F题
题目描述
给定带权无向图，求图中包含至少3个顶点的最小权值环路。若不存在则输出-1。
输入：
- 第一行：n,m（3≤n≤500，边数m≤20000）
- 接下来mmm行：u,v,w（边权1≤w≤ 10^6）
输出：最小环权值和。
示例：
输入：
4 5
1 2 1
2 3 2
3 4 3
4 1 4
2 4 5
输出：7（环路1-2-4-1）
题目3：区间众数（数据结构·中等偏难）
来源参考：类似2020年四川省赛D题
题目描述
给定长度为n的数组和q次查询，每次查询区间[l,r]的严格众数（出现次数超过（r−l+1）/2的数），若无则输出-1。
输入：
- 第一行：n,q,1≤n,q≤10^5）
- 第二行：数组ai（1≤ai≤10^9）
- 接下来q行：l,r
输出：每个查询的答案。
题目4：异或方程组（数学·难题）
来源参考：类似2019年四川省赛H题
题目描述
给定nnn个异或方程组成的方程组（模2），判断是否有解。若有解，求一组可行解。
输入：
- 第一行：n,m（方程数、变量数，1≤n,m≤500）
- 接下来nnn行：每行m+1m个0/1，前m个数为系数，最后一个为等号右侧值
输出：无解输出No solution，否则输出任意解。
示例：
输入：
3 3
1 1 0 1
0 1 1 0
1 0 1 1
输出：
1 0 1
题解
核心考点：高斯消元（异或版）
** 题目5、中等题：动态规划（背包变形）
题目名称：分割等和子集
题目描述
给定数组a，判断是否能将其分成两个子集，使得两子集和相等。
输入：
- 第一行：n（1≤n≤200）
- 第二行：a1,a2,…,an（1≤ai≤100）
输出：YES或NO。
示例：
输入：
4
1 5 11 5
输出：YES（分割为[1,5,5]和[11]）
题目6 简单题：贪心/模拟
题目名称：任务调度器
题目描述
有n个任务，每个任务需要时间ti且必须在截止时间di前完成。求最多能完成多少个任务。
输入：
- 第一行：n（1≤n≤10^5）
- 接下来n行：ti,di（1≤ti≤di≤ 10^9）
输出：最多可完成任务数。
示例：
输入：
3
2 4
1 5
3 6
输出：3