经过整理,老师已经整理了今年CSP-J复赛的题目和代码解析!
T4题目名称有误,更正:接龙!
需要PDF版本的→malaoshi606
T1 扑克牌 poker
- 算法:模拟,桶数组
- 思路:创建一个标记数组
vis
,vis[a][b]
表示a花色的牌b是否拥有。统计vis
数组中牌的数量cnt
,答案为52减去cnt
。 - 时间复杂度:O(n)
T2 地图探险 explore
- 算法:模拟
- 思路:模拟转向和移动,使用
vis
数组标记是否走过。 - 时间复杂度:O(n+k)
T3 小木棍 sticks
- 算法:贪心,构造
- 思路:
- 对于
n<=7
的情况,可以直接打表得到答案。 - 对于
n>7
的情况,优先数位越少越好,从低位开始放木棒,优先放8,然后根据剩余的棍子数n%7
进行分类讨论,以构成最小值。
- 对于
- 时间复杂度:O(n/7)
T4 地图探险 explore(再次出现,可能是文件内容重复)
- 算法:模拟,桶,dp
- 思路:
- 使用二维桶
cnt[i][j]
记录第i
轮接龙时,能否使用数字j
结尾。 - 记录每个人的数字,循环遍历他们,更新本轮的
cnt
。 - 考虑同一个人不可以连着接两次龙,记录上一轮接龙结尾的数字。
- 使用二维桶
- 时间复杂度:O(100n)