CSP-J 2022 入门级复赛真题及详细题解来啦！

关注code鸭，跟博士学编程

2022年的CSP-J/S复赛已经圆满结束啦！虽然咱们大山东因为疫情原因复赛取消。不过复赛题目的难度大家还是要关注起来，了解赛事趋势变化，方便选手们制定下一年的信奥规划！现在就跟鸭鸭一起去看看入门级的题目和题解吧！ 第一题 ：乘方（pow） 第一题 难度很小， 主要考察大家对数据范围的分析能力 。有的同学 不看数据范围 ，对于int和long long的范围没有概念， 直接使 用pow导致丢大分 。

题解： 本题数据规模较小，直接进行b次乘以a即可。不过要注意使用long long类型，因为 a和b输入的时候*大到10^9，只要乘一次就会超过int的范围。

第二题：解密（decode） 第二道题主要考查大家的数学功底，难度适中。选手可以 通过一些数学方法比如二元一次方程来推出公式， 进行解题。 没有学过二元一次方程的选手，正常解答至少可以拿到部分分数。

题解： 方法一：

方法二：

第三题：逻辑表达式（expr） 第三题和往年相比难度适中。 如果仅运用“骗分”技巧能够拿到10-20分，但是想拿满分就需要很厚的代码功底。 虽然到dfs同学们基本都能做对，但在前期建立表达式树的过程中，需要协调好优先级，非常考验同学们的代码和思维能力。

题解： 括号里的优先级更高，所以碰到括号优先算括号。在表达式树中，一个括号就是一个子树。 可以使用两个栈来维护信息。一个栈维护数字，一个栈维护运算符。运算符栈里的优先级应该维护严格单调性，比如1&0|1这里，处理到|的时候应当优先计算1&0，让1&0先算出结果也就是形成一棵由&为根的子树。而碰到0|0|1的时候也应当先计算0|0。 字符串中一共会出现0 1 | & ( ) 六种字符。 •遇到左括号，左括号入操作符栈 •遇到右括号，将整个括号建立成一棵子树 •遇到操作符，维护操作栈的单调性 •遇到数字，建立叶子节点 不要忘了如果处理结束后栈里还有剩余元素，应当不断建树直到栈为空。 至于建完树后的计算，dfs即可。每次先算左子树判断是否短路。

上下滚动查看完整代码 第四题：上升点列（point） 最后一道题主要考查动态规划问题， 在往年的入门级复赛题目中，这道题算是一道比较直接的动态规划递推求解类问题。 基本上不需要什么动态规划的优化，如果选手对二维动态规划的递推有了基本掌握的话，就可以解出来。

题解： 本题是比较套路的DP，将所有的点按照先x升序再y升序的顺序排好，然后设为以第 i 个点为结尾，使用了 j 个点连接的*大长度。转移也很简单，对于第 i 个点，在第 1 到 i-1 个点中找一个点连接一下，维护一下*大值即可。 不过要注意，假设*多用5个点，中间连接用了3个点，多的两个点可以放在*前面。题目中说自由点的坐标不受限制，所以放在前面就算形成了很长的链，有的自由点的坐标成了负数也没有关系。