csp-s2提高组2021第二轮题解

CSP-S2提高组是中国计算机学会(CCF)主办的一项全国性计算机竞赛，旨在挑选出优秀的高中生并为他们提供提高计算机科学和编程能力的平台。2021年第二轮题解分为以下几个部分。

第一题是关于石头游戏的思考。题目给出了一堆石头的数量，两位玩家轮流选择石头进行取走，每次可以取走1个或者2个石头，最后无法继续取走者输掉游戏。通过观察可以发现，如果一开始给定的石头数量是3的倍数，那么第一个选手必胜；否则，第一个选手无法必胜。这是因为无论第一个选手怎么选取，第二个选手总可以使得每一轮选取后的石头数量保持在3的倍数。因此，只需要判断起始时石头数量是否为3的倍数即可。

第二题是关于好书的购买。题目给出了若干种书的价格和折扣情况，要求在有限的预算下买到尽可能多的书籍。这是一个经典的背包问题。使用动态规划算法可以解决，按照价格从小到大的顺序遍历书籍，设置一个二维数组dp[i][j]表示在前i本书中，花费j的预算能够买到的最多书籍数量。状态转移方程为：dp[i][j]=max(dp[i-1][j], dp[i-1][j-price[i]]+1)。最终的结果即为dp[n][budget]，其中n为书籍总数，budget为预算。

第三题是关于均匀生成所有正整数的问题。题目给出了一个区间[L, R]，要求输出在该区间内存在的所有正整数。首先通过观察可以发现，对于任意的正整数x，若2x在区间[L, R]内，那么x也在该区间内；若2x+1在区间[L, R]内，那么x也在该区间内。基于这个思路，可以使用递归的方式实现。若L<=R，则输出L，然后递归输出从2*L到R的所有整数。若L>R，则结束递归。

以上就是CSP-S2提高组2021第二轮题解的简要概述。希望这些解题思路对参与竞赛的同学有所帮助！