2020-2021:teams:running_chicken:2020_summer_week7_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week7_report [2020/08/24 22:36] selia [比赛] |
2020-2021:teams:running_chicken:2020_summer_week7_report [2020/08/30 00:17] (当前版本) chenjiyuan3 [todolist（补题）] |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ======团队====== | ======团队====== | ||
| - | 2020.08.19 [[.hdu_2020_1|2020杭电多校第一场]] | + | 2020.08.25 [[.hdu_2020_3|2020杭电多校第三场]] |
| - | 2020.08.21 [[.hdu_2020_2|2020杭电多校第二场]] | + | 2020.08.28 [[.hdu_2020_4|2020杭电多校第四场]] |
| ======个人====== | ======个人====== | ||
| 行 31: | 行 31: | ||
| 2020牛客暑期多校训练营（第十场）CJY G XX B ZRX F | 2020牛客暑期多校训练营（第十场）CJY G XX B ZRX F | ||
| - | 2020加赛1 CJY A/E XX B/C ZRX D | + | 2020加赛1 CJY **A**/E XX B/C ZRX D |
| 2020加赛2 CJY E | 2020加赛2 CJY E | ||
| 行 39: | 行 39: | ||
| 2020杭电多校第一场 ZRX C | 2020杭电多校第一场 ZRX C | ||
| - | 2020杭电多校第二场 CJY B/D ZRX K (C) | + | 2020杭电多校第二场 CJY B/**D** ZRX K (C) |
| + | |||
| + | 2020杭电多校第三场 CJY B/**H**/**J** XX A ZRX C (K) | ||
| + | |||
| + | 2020杭电多校第四场 CJY **I** XX F ZRX J (A/H) | ||
| 行 46: | 行 50: | ||
| ====专题==== | ====专题==== | ||
| + | 大质数分解 | ||
| ====比赛==== | ====比赛==== | ||
| + | Codeforces Round #665 (Div. 2) | ||
| ====题目==== | ====题目==== | ||
| + | ecr 94 F | ||
| =====ZRX===== | =====ZRX===== | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | 平衡树专题 | ||
| + | |||
| + | 拓扑排序与2-sat专题 | ||
| ====比赛==== | ====比赛==== | ||
| + | |||
| + | 2020.08.25 [[.hdu_2020_3|2020杭电多校第三场]] | ||
| + | |||
| + | 2020.08.28 [[.hdu_2020_4|2020杭电多校第四场]] | ||
| + | |||
| + | abc 176 | ||
| ====题目==== | ====题目==== | ||
| + | |||
| + | cf 1791g | ||
| =====XX===== | =====XX===== | ||
| 行 62: | 行 81: | ||
| ====专题==== | ====专题==== | ||
| - | [后缀自动机与广义后缀自动机]：添加一道典型题目，添加map实现后缀自动机的写法 | + | 后缀自动机与广义后缀自动机：添加一道典型题目，添加map实现后缀自动机的写法 |
| - | [AC自动机]：添加两道题目 | + | AC自动机：添加两道题目 |
| - | [FFT]：添加模板，添加两道题目 | + | FFT：添加模板，添加两道题目 |
| ====比赛==== | ====比赛==== | ||
| 行 80: | 行 99: | ||
| **题意** | **题意** | ||
| + | |||
| + | 序列里有k种不同的数，你每次可以询问l~r，可以得到其中众数是多少，这个众数出现了多少次，最多询问4*k次。 | ||
| **思路**： | **思路**： | ||
| + | |||
| + | 如果这个众数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是众数 | ||
| + | |||
| + | 4*k很容易想到线段树 | ||
| + | |||
| + | 每次在线段树上询问，如果能确定的话，就询问剩下两个区间，否则询问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的真约数。 | ||
| + | |||
| + | 求最少删多少字串可以使得不存在x-prime。($x\leq20$，$|S|\leq1000$) | ||
| **思路**： | **思路**： | ||
| + | |||
| + | 直接状压dp是不太可能的，如果能细心一下，可以发现所有不合法的x-prime串实际上在字典树上的节点个数非常少，因此我们可以在AC自动机上 | ||
| + | |||
| + | dp，这样就能通过这道题。 | ||
| **评论**： | **评论**： | ||
| + | |||
| + | 本题巧妙在于它存储状态是采用了AC自动机来存储，而不是状压，这个题可以好好琢磨琢磨。 | ||
| =====XX===== | =====XX===== | ||
| - | ====Twilight and Ancient Scroll==== | + | ====[SCOI2012]喵星球上的点名==== |
| - | 来源： | + | 来源：SCOI |
| - | 算法： | + | 算法：广义后缀自动机 |
| - | **题意**： | + | **题意**：每一个人的名字由两个字符串构成，如果询问串为某个人的某个串的子串，那么这个人即被点到。对于每一个询问串，输出点到了几个人。全部询问结束后，输出每个人被点到的次数。 |
| **思路**： | **思路**： | ||
| - | [[https://codeforces.com/contest/1393/problem/E2|题目]] | + | 对名字建广义后缀自动机。 |
| + | |||
| + | 询问一：预处理每一个节点会被多少个人的名字包含。枚举每一个人的名字，对于每一个节点，向上跳fa，对其所有后缀的sz进行更新。对每一个询问，找到对应节点，输出sz即可。 | ||
| + | |||
| + | 询问二：对于每一个询问串，对其所在节点vist更新。全部询问结束后，枚举每一个人的名字，对于其中每一个节点，向上统计其所有后缀的出现次数。 | ||
| - | [[https://blog.csdn.net/micaudience/article/details/108036020|代码]] | ||
| **评论**： | **评论**： | ||
| + | 在广义后缀自动机上的统计问题要注意利用自动机的性质。 | ||
2020-2021/teams/running_chicken/2020_summer_week7_report.1598279795.txt.gz · 最后更改: 2020/08/24 22:36 由 selia
