2020-2021:teams:too_low:cf655ef_hj
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:cf655ef_hj [2020/09/02 09:44] jim |
2020-2021:teams:too_low:cf655ef_hj [2020/09/04 17:51] (当前版本) jim [E. Omkar and Last Floor] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===== E. Omkar and Last Floor ===== | ===== E. Omkar and Last Floor ===== | ||
| + | |||
| + | * 题意：一个n*m矩阵，每一行被分割成了多个片段，每个片段中填一个1，使每列1个数的平方和最大。输出最大结果。m，n<100 | ||
| + | |||
| + | * 分类：dp、贪心 | ||
| 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | ||
| - | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。 | + | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。考虑1尽可能集中到第i列，那么有dp[l][r] = dp[l, i-1] + dp[i+1, r] + 被i分割，且位于[l,r]区间内的的片段数 |
| - | 考虑1尽可能集中到第i列，那么有dp[l][r] = dp[l, i-1] + dp[i+1, r] + 被i分割，且位于[l,r]区间内的的片段数 | ||
| 对枚举i后取最大值即可得到dp[l][r] | 对枚举i后取最大值即可得到dp[l][r] | ||
| + | * comment: 这道题m，n较小，可以容纳维度更高的dp。主要是需要确定dp时分割片段的标准。 | ||
| <code cpp> | <code cpp> | ||
| 行 61: | 行 65: | ||
| ===== F. Omkar and Modes ===== | ===== F. Omkar and Modes ===== | ||
| + | * 题意：存在一个不减的数列，每次询问可以返回区间内出现次数最多的数字和其个数，在4k-4个询问内确定这个数列 | ||
| + | |||
| + | * 分类：CDQ分治 | ||
| 显然需要用类似二分的方式询问，不过二分的次数为log k * k，log k可能会大于4 | 显然需要用类似二分的方式询问，不过二分的次数为log k * k，log k可能会大于4 | ||
| 行 70: | 行 77: | ||
| 另外，为了尽可能阻止出现左子区间和父区间结果完全相同，需要再次二分的情况，二分的中值设定为了父区间的数字最大重复个数。 | 另外，为了尽可能阻止出现左子区间和父区间结果完全相同，需要再次二分的情况，二分的中值设定为了父区间的数字最大重复个数。 | ||
| - | 因此大约每两次可以询问定位一个数字。 | + | 因此大约每两次询问可以定位一个数字。 |
| + | |||
| + | * comment：这道题的询问次数限制很少，分治时要特别注意log的消除 | ||
| <code cpp> | <code cpp> | ||
2020-2021/teams/too_low/cf655ef_hj.1599011040.txt.gz · 最后更改: 2020/09/02 09:44 由 jim
