前言

联合省选 rp++

不想开学/kk

学习内容

  • 分数规划
  • 整体二分
  • cdq 分治
  • Matrix-Tree 定理
  • Borůvka 算法
  • 长链剖分
  • dsu on tree
  • 点分治

做题记录

21/03/01

  • CF126B Password

KMP 算法的理解问题,找到 \max_{1\le i\lt n}fail_i,然后判定哪个最长的 Border 能作为答案即可。

21/03/02

  • P3435 [POI2006]OKR-Periods of Words

涉及到 KMP 的理解。需要求出每个前缀的最小 Border——直接跳 fail 跳到 fail = 0 即可,但是不能暴跳,需要记忆化递推。

  • P3538 [POI2012]OKR-A Horrible Poem

字符串哈希判循环串模板。考虑枚举循环节的长度(分解质因数),然后通过哈希实现判定

  • P4503 [CTSC2014]企鹅QQ

哈希,枚举每一位判定即可,通过 sort 加速判断。

  • P1659 [国家集训队]拉拉队排练

manacher 求奇数长度回文串,需要前缀和一下而且还要快速幂

21/03/03

  • LOJ#149. 01 分数规划

01 分数规划裸题,二分答案

  • P1404 平均数

01 分数规划

  • P4377 [USACO18OPEN]Talent Show G

01 分数规划套了个背包而已

  • UVA11475 Extend to Palindrome

求一个最长回文后缀即可

21/03/04

  • P4824 [USACO15FEB]Censoring S

KMP + 栈

21/03/05

  • P3121 [USACO15FEB]Censoring G

上题的 AC 自动机版本

21/03/06

  • CF526D Om Nom and Necklace

KMP 循环节

  • P3193 [HNOI2008]GT考试

KMP + 矩阵快速幂加速 dp

  • Codeforces Round #705 (Div. 2)

A + B + D rk1057

21/03/07

  • U155026 给给

紫书题变种

  • P4986 逃离

牛顿迭代法

21/03/09

  • P7115 [NOIP2020] 移球游戏

构造

  • CF622F The Sum of the k-th Powers

拉格朗日插值

21/03/10

  • P2055 [ZJOI2009]假期的宿舍

最大流

  • Codeforces Round #706 (Div. 2)

A + B+ C

21/03/11

  • CF1495B Let’s Go Hiking

博弈论,补题

21/03/12

  • CF1495C Garden of the Sun

构造,赛后补题

  • P5431 【模板】乘法逆元2

21/03/13

  • Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)

A + B

  • P5104 红包发红包

先分析第一个人能得到多少: \int_0^w \frac 1w x\mathrm dx = \frac w 2,所以这样推下去知答案为 \frac{w}{2^k}

  • CF1500A Going Home

毒瘤暴力题分析复杂度

21/03/15

  • ARC069D Flags

二分答案 + 线段树优化建图 + 2-SAT

21/03/16

  • POJ 3352 Road Construction

求最小添加的边数使得去掉所有桥,答案为边双连通分量缩点后叶子的数量加一除以二。

21/03/17

  • BZOJ#4398. 福慧双修

将 1 号点拆点之后二进制分组连边跑最短路保证每对出点都被枚举到。

21/03/18

  • P5958 [POI2017]Sabotaż

f_u = \max\lbrace\min\lbrace \frac{size_v}{size_u – 1}, f_v \rbrace\rbrace

  • P3177 [HAOI2015]树上染色

毒瘤树形dp,细节繁多,只需考虑每条边产生的贡献。需要注意状态转移的合法性,可以使用 tmp 数组进行暂存

21/03/19

  • CF708C Centroids

换根 dp,考虑找到一个大小大于 n/2 的子树然后将其接走即可

  • P2515 [HAOI2010]软件安装

tarjan 缩点 + 树上背包,注意图不连通的情况,需要特判

  • P5304 [GXOI/GZOI2019]旅行者

二进制分组跑最短路

21/03/23

  • P4298 [CTSC2008]祭祀

构造一个 DAG 的最长反链。

  • UVA11419 SAM I AM

把横行和纵列作为二分图的左部和右部,中间的点连边,跑最小覆盖即可。

21/03/24

  • P6062 [USACO05JAN]Muddy Fields G

把所有极长木板看作点,左右部分别为横和纵

  • P7112 【模板】行列式求值

任意模数行列式求值,考虑两行之间辗转相减

21/03/25

  • P6178 【模板】Matrix-Tree 定理

Matrix-Tree 定理的带权版本

  • P4336 [SHOI2016]黑暗前的幻想乡

Matrix-Tree 加容斥

  • P4455 [CQOI2018]社交网络

Matrix-Tree 模板

21/03/27

  • NOI Online #1 提高组

[0, 10] + [80,100] + 20

21/03/28

  • P3810 【模板】三维偏序(陌上花开)

cdq 分治

  • P1429 平面最近点对(加强版)

平面最近点对,分治法

21/03/29

  • HDU4343 Interval query

倍增优化贪心

  • HDU6031 Innumerable Ancestors

两点集 LCA 查询,树上倍增+二分答案

  • P3366 【模板】最小生成树

Borůvka 算法通过

21/03/30

  • CF888G Xor-MST

最小 xor 生成树

  • P5903 【模板】树上 k 级祖先

长链剖分

  • U41492 树上数颜色

dsu on tree 模板

21/03/31

  • CF600E Lomsat gelral

dsu on tree

  • CF570D Tree Requests

dsu on tree

  • LOJ#6669. Nauuo and Binary Tree

交互好题,树链剖分

  • CF1009F Dominant Indices

长链剖分优化 dp

  • P3806 【模板】点分治1

点分治

  • NOIOL 1 0 + 80 + 20 = 100
最后修改日期: 2021年3月31日

作者

留言

撰写回覆或留言

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