2020-2021:teams:running_chicken:2020_summer_week8_report
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/09/04 15:11] chenjiyuan3 |
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/09/04 15:17] (当前版本) yyxzhj |
||
|---|---|---|---|
| 行 63: | 行 63: | ||
| ====专题==== | ====专题==== | ||
| - | 平衡树专题 | + | 哈希专题 |
| - | + | ||
| - | 拓扑排序与2-sat专题 | + | |
| ====比赛==== | ====比赛==== | ||
| - | 2020.08.25 [[.hdu_2020_3|2020杭电多校第三场]] | + | 2020.09.01 [[.hdu_2020_5|2020杭电多校第五场]] |
| - | 2020.08.28 [[.hdu_2020_4|2020杭电多校第四场]] | + | abc 177 |
| - | + | ||
| - | abc 176 | + | |
| ====题目==== | ====题目==== | ||
| - | cf 1791g | + | abc 177f |
| =====XX===== | =====XX===== | ||
| 行 97: | 行 93: | ||
| **题意** | **题意** | ||
| - | 序列里有k种不同的数，你每次可以询问l~r，可以得到其中众数是多少，这个众数出现了多少次，最多询问4*k次。 | + | （n+1）*m网格，第2-n+1行每一行li-ri不能向下 |
| + | |||
| + | 你可以从第1行任意一个位置出发，问到第i行的最小步数，每行独立。 | ||
| **思路**： | **思路**： | ||
| - | 如果这个众数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是众数 | + | 存一个map pre ai 维护，每个位置最靠右可以从第1行哪来， |
| - | 4*k很容易想到线段树 | + | li ri相当于删去li到ri，并加入ri+1即可 |
| - | + | ||
| - | 每次在线段树上询问，如果能确定的话，就询问剩下两个区间，否则询问l，mid和mid+1，r | + | |
| - | + | ||
| - | 算一下最坏情况也是4*k | + | |
| **评论**： | **评论**： | ||
| - | 4*k的操作数可以想线段树 | + | 考虑特殊的位置 |
| - | + | ||
| - | 一个数如果在区间出现次数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是它 | + | |
| =====cjy===== | =====cjy===== | ||
2020-2021/teams/running_chicken/2020_summer_week8_report.1599203484.txt.gz · 最后更改: 2020/09/04 15:11 由 chenjiyuan3
