快来估分！2020CSP-J2题解和自测

快来估分啦！

今天上午进行了J组的第二轮认证，小编程家的老师们马不停蹄的完成了考题解题。

为选手们提供第二轮认证线上自测。

请关注【小编程家信奥赛】公众号，点击中间菜单领取课程短码后，到电脑上进行自测。

网址是：www.itbegin.com

以下是每个题目的解题思路

供选手参考

【题目概要】

把一个整数n拆分成 2的正整数次幂的和 (不存在2的零次幂)

因为不存在2^0 所以在求和的时候是不可能存在奇数,所以奇数就直接输出负一

只要是偶数都可以写成2的正整数次幂的和

例如 18 = 2^4 + 2^1;

【暴力思路】

这题把n减去最接近他的 2次幂即可最大复杂度为O(276) 可得满分

外层循环为n!=0

内层循环找最接近n的2次幂,每找到一个就输出

【题目概要】

给定n名同学的成绩,和p%的获奖率,每读入一名同学的成绩输出当前读入人数中获奖的最低分.

【暴力思路】

外层循环i举例读入i名同学的成绩,设t为前max(1 , i*p%) 的获奖人数,

内层循环在i名同学中找第t高分.

复杂度为O(N^2)，可得到75分。

【优化思路】

100%数据范围：n=10000。

在外层循环读入第i名同学时,我们可以设to数组记录当前分数出现的次数,根据题目分数是不超过600的整数,

那么内层循环找第t高分时,可以选择从高到低范围to数组,记录所有分数出现次数和t进行比较,只要次数不超过t就继续找低分,直到超过为止

时间复杂度为 O(600*n)

【题目概要】

一个&、|、!和变量xi（i从1..n）组成的表达式，对于q次查询，每次查询把xi改成!xi的情况下，表达式重新运算的结果。每次查询都是临时的，即xi的修改只在当次输出有效。

【暴力思路】

循环q，对每个修改重新计算表达式，输出结果。

复杂度为O(q * n)，可得到30分。

【优化思路】

100%数据范围：q<=10^5, n<=10^5。

思考：

对每个xi的修改，重新运算可分为两部分来考虑：

l 第一部分：从前面到xi-1的运算。

l 第二部分：从xi修改过后，往后运算。

其中，第一部分跟xi的修改无关，因此可以预处理缓存起来，记为f[i]

第二部分，如果xi修改过后，往后运算某个位置k，运算结果（架设g[k]）还是原来的f[k]的话，那么再往后就无需运算了，显然答案不会有变化。

但对每个xi的修改往后运算，直到g[k]==f[k]停止，这样的复杂度还是O(q * n)。

再思考－q次查询，每次修改一个xi，先后顺序有没有可重用的点？

假设两个查询xi < xj：

l 对xj来说，往后求g[k]，直到g[k]==f[k]停止，最坏的可能是k==n

l 对于xi<xj来说，往后求g[k]，如果到g[j]还是不等于f[j]，意味着进入了xj的节奏，那么在j位置就可以停止了，答案就是j位置修改过后的结果。

依次类推，对q次查询排序，从后往前计算，则每次xi的修改最多只需要运算到xi+1，同时考虑第一部分的重用，算法复杂度变成了O(n)。

【题目概要】

一个n*m的矩阵，从左上到右下，每次只能往右、下、上，求路径上和的最大值。

【暴力思路】

搜索回溯，对每个位置递归往右、下、上，走过的不能再走，走到右下角时计算最大值。

复杂度为O(3^n)，可得到20分。

【优化思路】

如果只能往右、下走，那就是一个DP模板题，递推方向很明显。

那么增加了往上走，递推方向就大大变难了，对某格子(x , y)来说，可以从左边、上边、下边过来，但从上边过来的最大值又可能会从下过来，出现了回路。

结论：用一个状态f[x][y]表示走到(x,y)位置的最大和，不好做。

思考：分成三个状态呢？

l fl[x][y]表示(x,y)位置，最后从左边过来的最大和。

l fu[x][y]表示(x,y)位置，最后从上边过来的最大和。

l fd[x][y]表示(x,y)位置，最后从下边过来的最大和。

分析一下就知道，结合题目里不能重复走的约束，还是可以递推的，没有回路。

再设f[x][y]为走到位置(x,y)的最大和。

得到递推方程：

fl[x][y] = f[x][y-1]+a[x][y]

fu[x][y] = max(fl[x-1][y],  fu[x-1][y]) + a[x][y]

fd[x][y] = max(fl[x+1][y],  fd[x+1][y]) + a[x][y]

f[x][y] = max(fl[x][y],  fu[x][y],  fd[x][y]);

算法复杂度为O(n*m)。

如果觉得递推方向还是比较难实现的话，可以用记忆递归来实现。

需要参考代码

可加陈老师微信咨询

---