Contents

计划

  • 全面推进 dp 能力
  • 学习提高组树上相关算法
  • 学习提高组数论及组合
  • 搞过联赛这一关

做题记录

20/08/28

CF543A Writing Code

二维费用完全背包求方案数

P4316 绿豆蛙的归宿

拓扑排序+期望dp

P1107 [BJWC2008]雷涛的小猫

稍加优化的线性dp

CF414B Mashmokh and ACM

线性dp

20/08/29

P6064 [USACO05JAN]Naptime G/SP283 NAPTIME

P6064 [USACO05JAN]Naptime G/SP283 NAPTIME 线性dp

P2933 [USACO09JAN]The Baric Bovine G

P2933 [USACO09JAN]The Baric Bovine G 线性dp

20/09/03

poj2524 Ubiquitous Religions

并查集+连通块

20/09/04

P1197 [JSOI2008]星球大战

逆向思维并查集+连通块

poj2236 Wireless Network

并查集

P1525 关押罪犯

种类并查集

P2024 [NOI2001]食物链

种类并查集

hdu3092 Least common multiple

hdu3092 Least common multiple 完全背包+数论+对数背包

hdu2182 Frog

简单线性dp

20/09/05

hdu4489 The King’s Ups and Downs

hdu4489 The King’s Ups and Downs 组合数学+dp,OEIS A001250

hdu1003 Max Sum

需要记录状态的最大子段和

hdu1087 Super Jumping!

线性dp

hdu1503 Advanced Fruits

LCS变形(记录方案+混合字符串)

20/09/06

hdu2476 String Painter

洛谷P4170变形,两次dp

P2016 战略游戏

简单树形dp

20/09/07

P2458 [SDOI2006]保安站岗

树形dp

P2563 [AHOI2001]质数和分解

完全背包

20/09/08

P3379 【模板】最近公共祖先(LCA)

倍增求 LCA

20/09/09

P4281 [AHOI2008]紧急集合 / 聚会

LCA的一些性质

20/09/10

P1395 会议

树的重心

P1133 教主的花园

线性dp

P1266 速度限制

P1266 速度限制 二维状态限定的最短路(分层图)

20/09/12

校内模拟赛 25+100+65=190 rk2

20/09/14

P1273 有线电视网

P1273 有线电视网 树上背包

20/09/15

P1613 跑路

P1613 跑路 倍增优化 dp

P3811 【模板】乘法逆元 线性求逆元

P3811 【模板】乘法逆元

20/09/16

P1082 同余方程

P1082 同余方程 拓欧求逆元

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

P1495 【模板】中国剩余定理(CRT)/曹冲养猪 CRT

20/09/17

P1516 青蛙的约会

P1516 青蛙的约会 exgcd

20/09/18

校内练习赛

20/09/19

校内模拟赛 80+8+85=193 rk2

20/09/21

P1364 医院设置

带点权的树的重心

P1122 最大子树和

f_u=max(f_v+f_u,f_u)

只需统计 f_{u_{max}} 即可,因为选出来最后的结果必然有一个节点是子树的根节点,所以不用考虑过多。

20/09/22

P4310 绝世好题

求给定序列的最长子序列 \lbrace b_i\rbrace 满足 b_i 按位与 b_{i-1} 不为0

f_i 表示当前子序列第 i 位为 1 的最大长度,读入时按位转移,复杂度 O(n)

P2015 二叉苹果树

树上背包,f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w);

20/09/23

P1131 [ZJOI2007]时态同步

树上dp,直接 O(n) 扫描并计算即可

20/09/25

P1440 求m区间内的最小值

单调队列裸体

20/09/26

P2627 [USACO11OPEN]Mowing the Lawn G && P2034 选择数字

f(i,0)=\max\lbrace f(i-1,0),f(i-1,1)\rbrace

f(i,1)=\max_{j\in(i-k,i)}\lbrace f(j,0)+s_i-s_j\rbrace=\max_{j\in(i-k,i)}\lbrace f(j,0)-s_j\rbrace+s_i

开一个单调队列维护 \max\lbrace f(j,0)-s_j\rbrace 即可。

20/09/28

P3384 【模板】轻重链剖分

轻重链剖分模板

20/09/29

P3379 【模板】最近公共祖先(LCA)

这次使用树剖求解 lca

最后修改日期:2020年11月26日

作者

留言

撰写回覆或留言

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