2020-2021:teams:running_chicken:2020_summer_week8_report
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/08/29 16:42] chenjiyuan3 创建 |
2020-2021:teams:running_chicken:2020_summer_week8_report [2020/09/04 15:17] (当前版本) yyxzhj |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ======团队====== | ======团队====== | ||
| + | |||
| + | 2020.09.01 [[.hdu_2020_5|2020杭电多校第五场]] | ||
| ======个人====== | ======个人====== | ||
| 行 19: | 行 21: | ||
| 2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D | 2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D | ||
| - | 2020牛客暑期多校训练营（第七场）CJY E ZRX A | + | 2020牛客暑期多校训练营（第七场）CJY E ZRX **A** |
| 2020牛客暑期多校训练营（第八场）XX J ZRX B/C | 2020牛客暑期多校训练营（第八场）XX J ZRX B/C | ||
| 行 27: | 行 29: | ||
| 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 E XX B/C ZRX D |
| 2020加赛2 CJY E | 2020加赛2 CJY E | ||
| 行 33: | 行 35: | ||
| 2015ICPC北京 ZRX E (B/F/H) | 2015ICPC北京 ZRX E (B/F/H) | ||
| - | 2020杭电多校第一场 ZRX C | + | 2020杭电多校第一场 ZRX **C** |
| - | 2020杭电多校第二场 CJY B/D ZRX K (C) | + | 2020杭电多校第二场 CJY B ZRX **K** (C) |
| 2020杭电多校第三场 CJY B XX A ZRX C (K) | 2020杭电多校第三场 CJY B XX A ZRX C (K) | ||
| 行 41: | 行 43: | ||
| 2020杭电多校第四场 XX F ZRX J (A/H) | 2020杭电多校第四场 XX F ZRX J (A/H) | ||
| + | 2020杭电多校第四场 XX F ZRX J (A/H) | ||
| + | 2020杭电多校第五场 CJY E/**J** XX B ZRX K (D/F/M) | ||
| =====CJY===== | =====CJY===== | ||
| ====专题==== | ====专题==== | ||
| - | 大质数分解 | + | 最小生成树 |
| + | |||
| + | 最短路 | ||
| ====比赛==== | ====比赛==== | ||
| - | 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===== | ||
| 行 77: | 行 79: | ||
| ====专题==== | ====专题==== | ||
| - | 后缀自动机与广义后缀自动机：添加一道典型题目，添加map实现后缀自动机的写法 | + | 无 |
| - | + | ||
| - | AC自动机：添加两道题目 | + | |
| - | + | ||
| - | FFT：添加模板，添加两道题目 | + | |
| ====比赛==== | ====比赛==== | ||
| - | Atcoder Beginner Contest 176 | + | Atcoder Beginner Contest 177 |
| ====题目==== | ====题目==== | ||
| - | Codeforces 1383/C 1389/F 1392/F | + | Codeforces 1381/D 1388/E 1389/G 1391/E 1400/G |
| - | hdu多校第二场 H | ||
| ======本周推荐====== | ======本周推荐====== | ||
| 行 96: | 行 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===== | ||
| - | ====[SCOI2012]喵星球上的点名==== | + | ====CF 1388 E Uncle Bogdan and Projections==== |
| - | 来源：SCOI | + | 来源：[[https://codeforces.com/contest/1388/problem/E|CF 1388]] |
| - | 算法：广义后缀自动机 | + | 算法：凸包、二分、区间 |
| - | **题意**：每一个人的名字由两个字符串构成，如果询问串为某个人的某个串的子串，那么这个人即被点到。对于每一个询问串，输出点到了几个人。全部询问结束后，输出每个人被点到的次数。 | + | **题意**： |
| + | 给n($n\leq$ 2000)条水平线段，求一个方向向量，使得这些直线按照该方向向量向x轴做投影后，所有线段不相交，求这些线段所覆盖的位置的最左端的和最右端的距离最小。 | ||
| **思路**： | **思路**： | ||
| + | 考虑两条线段AB、CD，只有AC、BD才可能成为答案。同时，斜率处于AC与BD之间的向量不能作为答案，否则会使AB、CD的投影相交。 | ||
| - | 对名字建广义后缀自动机。 | + | 所以，我们需要枚举出所有可能的答案，然后用区间覆盖的方式除去矛盾的线段，然后再比较哪一个向量求得的答案最小的答案。 |
| - | 询问一：预处理每一个节点会被多少个人的名字包含。枚举每一个人的名字，对于每一个节点，向上跳fa，对其所有后缀的sz进行更新。对每一个询问，找到对应节点，输出sz即可。 | + | 对于一个已知向量，我们需要求出投影后最左端和最右端的点。可以建凸包，然后根据叉积（或者斜率）进行二分即可。 |
| - | 询问二：对于每一个询问串，对其所在节点vist更新。全部询问结束后，枚举每一个人的名字，对于其中每一个节点，向上统计其所有后缀的出现次数。 | + | 注意，可能所有直线都在同一高度，此时需要特判垂直的情况（见样例3）。 |
| + | [[https://blog.csdn.net/micaudience/article/details/108381788|代码]] | ||
| **评论**： | **评论**： | ||
| - | 在广义后缀自动机上的统计问题要注意利用自动机的性质。 | + | 运用凸包+二分可以快速找最左/右端点，但需要注意每次凸包只能左/右侧跑一半！！ |
| + | |||
| + | 注意特殊处理垂直的情况 | ||
| + | |||
| + | 尽量使用long long代替long double来减少浮点误差。(用叉积代替斜率，用乘法代替除法) | ||
2020-2021/teams/running_chicken/2020_summer_week8_report.1598690523.txt.gz · 最后更改: 2020/08/29 16:42 由 chenjiyuan3
