2020-2021:teams:running_chicken:2020_summer_week8_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/09/04 14:42] selia [题目] |
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/09/04 15:17] (当前版本) yyxzhj |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ======团队====== | ======团队====== | ||
| + | |||
| + | 2020.09.01 [[.hdu_2020_5|2020杭电多校第五场]] | ||
| ======个人====== | ======个人====== | ||
| 行 48: | 行 50: | ||
| ====专题==== | ====专题==== | ||
| - | 大质数分解 | + | 最小生成树 |
| + | |||
| + | 最短路 | ||
| ====比赛==== | ====比赛==== | ||
| - | Codeforces Round #665 (Div. 2) | + | Codeforces Round #666 (Div. 1) |
| ====题目==== | ====题目==== | ||
| - | ecr 94 F | + | 2020杭电多校第五场 J |
| =====ZRX===== | =====ZRX===== | ||
| ====专题==== | ====专题==== | ||
| - | 平衡树专题 | + | 哈希专题 |
| - | + | ||
| - | 拓扑排序与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===== | ||
| 行 79: | 行 79: | ||
| ====专题==== | ====专题==== | ||
| - | 后缀自动机与广义后缀自动机：添加一道典型题目，添加map实现后缀自动机的写法 | + | 无 |
| - | + | ||
| - | AC自动机：添加两道题目 | + | |
| - | + | ||
| - | FFT：添加模板，添加两道题目 | + | |
| ====比赛==== | ====比赛==== | ||
| 行 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===== | ||
| - | |||
| - | ecr 94 F | ||
| **题意** | **题意** | ||
| - | 有一个由1-9组成的字符串，定义x-prime串为该串所有数字之和等于x并且不存在连续字串使得和是x的真约数。 | + | 一个N*N的网格，在上面放T个石子，要求每行每列不超过2个，问方案数？(N小于等于200，T小于等于400) |
| - | 求最少删多少字串可以使得不存在x-prime。($x\leq20$，$|S|\leq1000$) | + | **思路**： |
| - | **思路**： | + | 直接动态规划，$f_{ijk}$表示已经填了i行，上面有j列填了1个，k列填了2个的方案数。 |
| - | 直接状压dp是不太可能的，如果能细心一下，可以发现所有不合法的x-prime串实际上在字典树上的节点个数非常少，因此我们可以在AC自动机上 | + | 转移的时候枚举这一行填0，1还是2。修改j和k即可。 |
| - | dp，这样就能通过这道题。 | + | 时间复杂度是O($N^3$) |
| **评论**： | **评论**： | ||
| - | 本题巧妙在于它存储状态是采用了AC自动机来存储，而不是状压，这个题可以好好琢磨琢磨。 | + | 一定要注意，这类转移状态比较少的，不要把它转换成二部图找环去考虑，因为那样复杂度太大了。 |
| =====XX===== | =====XX===== | ||
2020-2021/teams/running_chicken/2020_summer_week8_report.1599201757.txt.gz · 最后更改: 2020/09/04 14:42 由 selia
