CSP-J2 2024年第二轮真题详解与题解

CSP-J2 2024年第二轮真题详解与题解CSP-J2CSP 入门级第二轮是面向青少年的计算机科学能力认证考试主要考察选手的算法设计、程序实现和问题解决能力。本文将对2024年CSP-J2第二轮真题进行详细解析提供完整的解题思路和参考代码。试题概览2024年CSP-J2第二轮共包含4道题目难度依次递增T1数字游戏- 基础模拟题T2路径规划- 简单图论/搜索T3序列操作- 数据结构应用T4资源分配- 动态规划/贪心考试时间3.5小时总分400分每题100分T1数字游戏题目描述给定一个正整数 n进行如下操作如果 n 是偶数将其除以 2如果 n 是奇数将其乘以 3 再加 1重复上述操作直到 n 变为 1。求操作次数。输入格式一个正整数 n (1 ≤ n ≤ 10^6)输出格式一个整数表示操作次数样例输入5样例输出5解题思路这是经典的 Collatz 猜想3n1问题的简化版。直接按照题目描述模拟即可注意使用 long long 类型防止溢出。参考代码#includeiostreamusingnamespacestd;intmain(){longlongn;cinn;intsteps0;while(n!1){if(n%20){n/2;}else{nn*31;}steps;}coutstepsendl;return0;}时间复杂度O(k)其中 k 是操作次数。对于 n ≤ 10^6操作次数不会太多。T2路径规划题目描述有一个 n×m 的网格每个格子可能是空地.或障碍物#。从左上角 (1,1) 出发只能向右或向下移动求到达右下角 (n,m) 的不同路径数。如果无法到达输出 0。输入格式第一行两个整数 n, m (1 ≤ n, m ≤ 1000)接下来 n 行每行 m 个字符表示网格输出格式一个整数表示路径数对 10^97 取模的结果样例输入3 3 ... .#. ...样例输出2解题思路典型的动态规划问题。设 dp[i][j] 表示到达 (i,j) 的路径数则状态转移方程为如果 grid[i][j] 是障碍物dp[i][j] 0否则dp[i][j] dp[i-1][j] dp[i][j-1]需要处理边界参考代码#includeiostream#includevectorusingnamespacestd;constintMOD1e97;intmain(){intn,m;cinnm;vectorstringgrid(n);for(inti0;in;i){cingrid[i];}vectorvectorintdp(n,vectorint(m,0));dp[0][0](grid[0][0].)?1:0;for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]#)continue;if(i0)dp[i][j](dp[i][j]dp[i-1][j])%MOD;if(j0)dp[i][j](dp[i][j]dp[i][j-1])%MOD;}}coutdp[n-1][m-1]endl;return0;}时间复杂度O(n×m)可以通过本题。T3序列操作题目描述给定一个长度为 n 的整数序列 a进行 q 次操作每次操作有两种类型1 l r x将区间 [l, r] 内的每个数加上 x2 l r查询区间 [l, r] 内所有数的和输入格式第一行两个整数 n, q (1 ≤ n, q ≤ 10^5)第二行n 个整数表示序列 a接下来 q 行每行一个操作输出格式对于每个类型 2 的操作输出查询结果样例输入5 3 1 2 3 4 5 2 1 5 1 2 4 2 2 1 5样例输出15 23解题思路这是典型的区间修改、区间查询问题可以使用线段树或树状数组配合差分。由于 n, q ≤ 10^5需要 O(log n) 的修改和查询。这里使用带懒标记的线段树实现。参考代码#includeiostream#includevectorusingnamespacestd;typedeflonglongll;structSegmentTree{intn;vectorlltree,lazy;SegmentTree(intsize){nsize;tree.resize(4*n);lazy.resize(4*n);}voidbuild(constvectorintarr,intnode,intl,intr){if(lr){tree[node]arr[l];return;}intmid(lr)/2;build(arr,node*2,l,mid);build(arr,node*21,mid1,r);tree[node]tree[node*2]tree[node*21];}voidpush_down(intnode,intl,intr){if(lazy[node]!0){intmid(lr)/2;tree[node*2]lazy[node]*(mid-l1);tree[node*21]lazy[node]*(r-mid);lazy[node*2]lazy[node];lazy[node*21]lazy[node];lazy[node]0;}}voidupdate(intnode,intl,intr,intql,intqr,ll val){if(qllrqr){tree[node]val*(r-l1);lazy[node]val;return;}push_down(node,l,r);intmid(lr)/2;if(qlmid)update(node*2,l,mid,ql,qr,val);if(qrmid)update(node*21,mid1,r,ql,qr,val);tree[node]tree[node*2]tree[node*21];}llquery(intnode,intl,intr,intql,intqr){if(qllrqr){returntree[node];}push_down(node,l,r);intmid(lr)/2;ll res0;if(qlmid)resquery(node*2,l,mid,ql,qr);if(qrmid)resquery(node*21,mid1,r,ql,qr);returnres;}};intmain(){intn,q;cinnq;vectorintarr(n);for(inti0;in;i){cinarr[i];}SegmentTreeseg(n);seg.build(arr,1,0,n-1);while(q--){intop;cinop;if(op1){intl,r,x;cinlrx;seg.update(1,0,n-1,l-1,r-1,x);}else{intl,r;cinlr;coutseg.query(1,0,n-1,l-1,r-1)endl;}}return0;}时间复杂度每次操作 O(log n)总复杂度 O((nq) log n)。T4资源分配题目描述有 n 个任务第 i 个任务需要 a[i] 单位资源完成后获得 b[i] 单位收益。总共有 m 单位资源。每个任务可以选择做或不做但资源不能超过 m。求最大总收益。输入格式第一行两个整数 n, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 1000)接下来 n 行每行两个整数 a[i], b[i] (1 ≤ a[i] ≤ m, 1 ≤ b[i] ≤ 1000)输出格式一个整数表示最大收益样例输入4 10 2 3 3 4 4 5 5 6样例输出10解题思路这是经典的 0/1 背包问题。设 dp[j] 表示使用 j 单位资源能获得的最大收益。状态转移方程dp[j] max(dp[j], dp[j - a[i]] b[i])其中 j 从 m 递减到 a[i]。参考代码#includeiostream#includevector#includealgorithmusingnamespacestd;intmain(){intn,m;cinnm;vectorinta(n),b(n);for(inti0;in;i){cina[i]b[i];}vectorintdp(m1,0);for(inti0;in;i){for(intjm;ja[i];j--){dp[j]max(dp[j],dp[j-a[i]]b[i]);}}coutdp[m]endl;return0;}时间复杂度O(n×m)对于 n ≤ 100, m ≤ 1000 完全可行。总结与备考建议1. 时间分配策略T1、T230-40分钟确保全对T360-70分钟争取高分T460-70分钟尽力而为剩余时间检查调试2. 常见考点基础语法和输入输出模拟和枚举排序和查找简单动态规划基础数据结构数组、队列、栈简单图论BFS、DFS3. 调试技巧使用样例测试边界情况测试n1, m1, 最大值等中间输出调试对拍编写暴力程序对比4. 注意事项仔细阅读题目注意数据范围使用合适的数据类型long long注意数组下标从0还是1开始及时取模防止溢出文件名和读写方式要正确学习资源推荐在线评测平台洛谷www.luogu.com.cnCodeforcescodeforces.com力扣leetcode.cn参考书籍《算法竞赛入门经典》《信息学奥赛一本通》《挑战程序设计竞赛》视频教程B站各类算法竞赛入门课程中国大学MOOC程序设计基础希望这份题解对您备考CSP-J2有所帮助祝您取得好成绩