Contents
前言
仍旧菜的抠脚。
WC 2021 rp ++
学习内容
- 轮廓线 dp
- 上下界网络流
- Manacher
- 最小表示法
- exKMP
- SA
- 多项式乘法逆
做题记录
21/02/01
- CF1198D Rectangle Painting 1
二维区间 dp，以 x 和 y 方向分别划分即可
- HDU4283 You Are The One
比较清奇的区间 dp，考虑第 i 个人放到第 k 个出场造成的影响
- UVA11270 Tiling Dominoes
插头 dp，参见大佬题解
- HDU3507 Print Article
斜率优化 dp
21/02/02
- P3254 圆桌问题
网络流。源向单位连大小为单位人数的边，餐桌向汇连大小为餐桌人数的边，每个单位连每个餐桌，跑最大流，满流有解，找流有东西的边输出即可
- P2763 试题库问题
网络流。试题向属于的类型连 1，类型向汇连需要的题数，跑最大流，满流有解，输出方案。
- P2891 [USACO07OPEN]Dining G
拆点，源->食物->牛in->牛out->饮料->汇，保证流过牛的流量为 1，跑最大流即可
- P3805 【模板】manacher算法
manacher
- P1368 【模板】最小表示法
最小表示法
21/02/03
- CF734E Anton and Tree ————————AC500 祭
- CF911F Tree Destruction
21/02/04
- CF1000E We Need More Bosses
- P2766 最长不下降子序列问题
拆点 + 最大流
21/02/05
- WC 2021
-
Codeforces Round #699 (Div. 2)
A + B + C rk2134 该死终于能做三道题出来了/kk
21/02/06
- WC2021 10 + 50 + 20 = 80，Cu
-
LOJ#115. 无源汇有上下界可行流
上下界网络流
- LOJ#116. 有源汇有上下界最大流
上下界网络流
- P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流
建模 + 上下界网络流
21/02/07
- P2764 最小路径覆盖问题
最小路径覆盖数 = 点数 – 最大匹配数
- P2765 魔术球问题
上题的加强版，从小往大枚举答案，每次在残量网络上继续跑 Dinic
- P2754 [CTSC1999]家园 / 星际转移问题
最大流
- P4015 运输问题
费用流。套路：费用取负可以得到最大费用最大流
- P4016 负载平衡问题
费用流
21/02/08
- CF1475D Cleaning the Phone
补题，贪心 + 二分
- CF1475F Unusual Matrix
异或运算的性质：考虑先异或两个矩阵，然后判断这个矩阵是否能变为 0
- CF1475G Strange Beauty
比较神奇的数论dp
- CF1476C Longest Simple Cycle
dp，注意 long long
- P2770 航空路线问题
最大费用最大流
- P4014 分配问题
二分图最大权匹配，费用流
- P4013 数字梯形问题
拆点 + 费用流，注意细节
21/02/09
- CF1476D Journey
记忆化搜索/dp。注意到其实就是最多往左走的加上最多往右走的。
- CF1476E Pattern Matching
字符串哈希/Trie + 拓扑排序。找到 s 能匹配的所有 p，然后加边，拓扑。
- P2580 于是他错误的点名开始了
Trie 模板，注意数组开够
- SP4033 PHONELST – Phone List
Trie，如果在插入过程中遇到结束标记或者没有建立新的节点，则说明有前缀包含
- HDU4825 Xor Sum
01-Trie 模板，考虑将每个数字化成 01 二进制串插入 Trie 树。为了找到异或的最大值需往反方向下跳（相同为 0，不同为 1）
- HDU5536 Chip Factory
01-Trie。要开够空间，多测清空。注意 i,j,k 两两不同，需要删点/加点。
- P4551 最长异或路径
01-Trie。考虑处理每个点到根异或和 d_i，则答案为 \max\lbrace d_x, d_y\rbrace。因为到根重复的一段会被消去（异或运算的性质）
- P3358 最长k可重区间集问题
比较精巧的网络流建模，费用流。
21/02/10
- P3808 【模板】AC自动机（简单版）
AC 自动机
- P3796 【模板】AC自动机（加强版）
AC 自动机
- P2375 [NOI2014] 动物园
KMP，首先求出所有的 fail 然后建好 fail 树，在 fail 树上面进行动态统计即可。
21/02/11
- P5357 【模板】AC自动机（二次加强版）
避免每次跳 fail，直接建 fail 树最后树上差分即可。
21/02/13
- CF1485B Replace and Keep Sorted
dp
21/02/15
- P4782 【模板】2-SAT 问题
2-SAT
- P4171 [JSOI2010]满汉全席
2-SAT，读清楚题意是每种食材要么满要么汉
- P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
tarjan 求 scc，只需要找出出度为 0 的 scc 即可
- P2002 消息扩散
tarjan scc，找入度为 0 的点，即没有别的城市传信的城市
- Educational Codeforces Round 104 (Rated for Div. 2)
A + D，赛后补 B，C
21/02/16
- P3357 最长k可重线段集问题
费用流
- P4012 深海机器人问题
费用流
- P1251 餐巾计划问题
费用流
- Codeforces Round #702 (Div. 3)
赛中 A + B + C + D + F，赛后补 E
不开 long long 见祖宗
21/02/17
- CF1490G Old Floppy Drive
赛后补题
- CF1481D AB Graph
图论 + 构造。比较巧妙的构造题
21/02/18
- UVA1660 电视网络 Cable TV Network
最小割
21/02/19
- CF1481E Sorting Books
比较诡诈的 dp
- P3809 【模板】后缀排序
学习 SA
- P4051 [JSOI2007]字符加密
断环为链，即倍长串之后跑 SA
- BZOJ#3771. Triple
- P2408 不同子串个数
SA
- P4391 [BOI2009]Radio Transmission 无线传输
KMP 求循环节：N – fail(N)
- UVA10298 Power Strings
同上
- CF1200E Compress Words
找后缀和前缀的最长公共部分，那就 KMP
- P5410 【模板】扩展 KMP（Z 函数）
Z 算法
21/02/20
- P4238 【模板】多项式乘法逆
多项式乘法逆，倍增
21/02/21
- P4173 残缺的字符串
NTT 做带通配符的字符串匹配
- CF528D Fuzzy Search
myy 论文题，单独考虑每个字符跑 NTT
留言