"2020年CSP-J入门级复赛真题第一题解析：寻找优秀的拆分方案"

2020年CSP-J入门级复赛真题主要考察了一个正整数能否拆分为若干个相同的2的正整数次幂，并要求输出拆分方案。题目给出了一个正整数n，需要判断n的所有拆分中是否存在优秀的拆分，如果存在，则需要从大到小输出拆分方案的每个数，如果不存在，则输出-1。 首先，我们需要明确什么是优秀的拆分。根据题目描述，一个优秀的拆分是指将正整数n拆分为若干个相同的2的正整数次幂的和。换句话说，如果一个数能够表示为2的正整数次幂的乘积，那么它就是一个优秀的拆分。 为了解决这个问题，我们可以使用动态规划的思想。我们定义一个dp数组，dp[i]表示正整数i是否可以被拆分为若干个相同的2的正整数次幂的和。对于dp[i]，我们可以遍历所有小于i的2的正整数次幂j，判断i-j是否可以被拆分为若干个相同的2的正整数次幂的和。如果i-j可以被拆分，则dp[i]=true，否则dp[i]=false。 接下来，我们需要找出拆分方案。我们可以定义一个方案数组ans，ans[i]表示正整数i的拆分方案中的最后一个数。在判断dp[i]为true的同时，我们可以更新ans[i]为j，并且继续向前找到ans[i-j]，以此类推，直到找到ans[i]为止。最终，我们可以从ans[n]开始，通过递归的方式依次输出拆分方案中的每个数。 接下来，我们具体实现一下。首先，读取输入文件中的正整数n。然后，我们可以定义一个长度为n+1的dp数组，并将其中所有元素初始化为false。再定义一个长度为n+1的ans数组，并将其中所有元素初始化为-1。然后，对于i从1到n，依次进行动态规划判断。判断dp[i]时，我们可以遍历所有小于i的2的正整数次幂j，并判断dp[i-j]是否为true。如果是，则更新dp[i]为true，并将ans[i]更新为j。最后，如果dp[n]为false，则输出-1，否则，通过递归调用函数来输出拆分方案。 下面是完整的实现代码： ```python def printSplit(n, ans): if n == 0: return printSplit(n - ans[n], ans) print(ans[n], end=" ") with open("power.in", "r") as fin, open("power.out", "w") as fout: n = int(fin.readline()) dp = [False] * (n + 1) ans = [-1] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if i - (2 ** j) >= 0 and dp[i - (2 ** j)]: dp[i] = True ans[i] = 2 ** j break if not dp[n]: fout.write("-1") else: printSplit(n, ans) ``` 这样，我们就完成了对正整数n的拆分判断和输出拆分方案的任务。通过动态规划的方法，我们可以高效地解答这个问题。 总结：本题主要考察了动态规划的思想和递归的应用，以及对拆分方案的输出。首先，我们将问题抽象为一个动态规划问题，并定义了dp数组来保存每个状态的结果。然后，使用循环来遍历所有状态，通过动态规划的转移方程进行状态转移。在状态转移的过程中，我们也同时更新了拆分方案数组。最后，我们使用递归的方式输出拆分方案。整个过程中，我们需要注意边界条件的处理和循环的顺序。通过对于题目描述的仔细阅读和理解，我们可以很好地完成这道题目。