CSP-J 2020
T1 优秀的拆分
题目的本质是求 \(n\) 的二进制表示。求 \(n\) 的二进制表示,或者每次暴力分解出小于等于 \(n\) 的最大的 \(2\) 的正整数次幂。时间复杂度 \(O(\log {n})\)。
T2 直播获奖
给定 \(n\) 个人的分数,对于每个 \(i\),请你求出前 \(i\) 个人的第 \(k = \max (1, \lfloor p * w \% \rfloor)\) 大的分数。
求排名时避免使用浮点数运算。
50 分
对于前 \(i\) 个人的分数,暴力模拟。
时间复杂度 \(O(n^2 \log n)\)。
85 分
每次只新增一个人的成绩,用插入排序维护。
时间复杂度 \(O(n^2)\)。
100 分
分数最大为 \(600\),用桶排序求第 \(k\) 大分数。
时间复杂度 \(O(600 * n)\)。
考场造测试数据
T3 表达式
20 分
特殊考虑全为 &
或者 |
的情况,暴力模拟。
50 分
在 \(20\) 分的基础之上,模拟后缀表达式计算。
时间复杂度 \(O(q * n)\)。
100 分
T4 方格取数
25 分
暴搜。
35 分
考虑使用最优性剪枝,令 \(f[i][j]\) 表示到 \((i, j)\) 的最大得分,如果走到 \((i, j)\) 时得分不优于 \(f[i][j]\) 就不用搜下去。尝试后发现这样的局部剪枝是错误的。
这里忽略了一个问题,向上、向下、向右走到 \((i, j)\) 时,后续能够走的路径是不相同的。应该将其定义为 \(f[i][j][0], f[i][j][1], f[i][j][2]\) 表示向下、向右、向上走到 \((i, j)\) 时的最大得分,再做剪枝。
100 分
只能向右走,状态转移图存在拓扑序(所有状态朝着一个“方向”进行转移),满足无后效性。
又由于从某个方向到达某个格子的分数肯定越大越好,存在最优子结构。
因此分析得到本题的正解为动态规划,考虑使用记忆化搜索求解。
状态数 \(3 * n * m\),每个状态最多做三个方向转移,因此总时间复杂度 \(3 * n * m * 3 = O(n * m)\)。
标签:分数,剪枝,复杂度,2020,讲解,100,CSP From: https://www.cnblogs.com/xhr0817-blog/p/17446388.html