2020-2021:teams:no_morning_training:weekly:week11
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:week11 [2020/08/14 15:38] shaco |
2020-2021:teams:no_morning_training:weekly:week11 [2020/08/14 19:18] (当前版本) 发源于 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| 无 | 无 | ||
| ===专题=== | ===专题=== | ||
| + | 无 | ||
| ===== 冯宇扬 ==== | ===== 冯宇扬 ==== | ||
| ====比赛=== | ====比赛=== | ||
| + | cf 664 div 2 | ||
| + | 因为一些事 开始打的时候已经过去接近一个小时了 | ||
| + | 于是跳过前两道 | ||
| + | 最后因为浏览器的问题（最后排查发现是我改了ua）没交成 | ||
| ===专题=== | ===专题=== | ||
| ===== 常程 ===== | ===== 常程 ===== | ||
| 行 20: | 行 25: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| + | 无 | ||
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| + | 664 div 2 D \\ | ||
| + | 题意: 有序列 a[n], 每天可以选择里面一个数, 加到ans。 如果该数 > m, 则之后的 d 天不能选择数。 | ||
| + | |||
| + | 解法: 反过来贪心。最后一天放最大的，然后对于每一天，如果前面至少还有 d+1 天，并且 "<=m的数" 中 最大的 d 个的和（用前缀和维护）比 "没取的数" 中最大的小，就在这 d+1 天中放最大的， 否则放一个 <=m 的。\\ | ||
| + | 主要要注意一些细节，比如 <=m 的 / >m 的会不够用（会一个都没有）。 | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| + | **来源**：洛谷 p3067 Balanced Cow Subsets G | ||
| + | |||
| + | **tag**：搜索、贪心 | ||
| + | |||
| + | **概述**：给n个数，从中任意选出一些数，使这些数能分成和相等的两组。求有多少种选数的方案。 | ||
| + | |||
| + | **答案**：每一个数分成三种状态：不加入集合、加入第一个集合、加入第二个集合。在一个子集中，加入第一个集合记为加这个数，加入第二个集合记为减这个数，那么一个集合的sum为0即符合条件（空集除外）。分别得出前一半、后一半的选择情况，排序后利用指针简化组合过程。 | ||
| + | |||
| + | **comments**：折半搜索比较重要的一点就是得到快速的判断状态是否符合要求的算法，可以得到那么通常折半就可以实现。 | ||
| + | |||
2020-2021/teams/no_morning_training/weekly/week11.1597390721.txt.gz · 最后更改: 2020/08/14 15:38 由 shaco
