前言

仍旧菜的抠脚。

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

NTT + 容斥

  • 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

最后修改日期:2021年2月21日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。