前言

NOIOL 有点小爆炸

省选 ++rp

学习内容

  • Link-Cut Tree
  • 线性基
  • 后缀数组

做题记录

21/04/01

  • P3565 [POI2014]HOT-Hotels
  • P5904 [POI2014]HOT-Hotels 加强版

长链剖分优化 dp

  • P5384 [Cnoi2019]雪松果树

长链剖分

21/04/02

  • P3899 [湖南集训]谈笑风生

长链剖分

  • CF208E Blood Cousins

长链剖分

21/04/03

  • CF246E Blood Cousins Return

dsu on tree

21/04/04

  • P6625 [省选联考 2020 B 卷] 卡牌游戏

sb 贪心

  • P4178 Tree

点分治,使用树状数组维护贡献

  • P6626 [省选联考 2020 B 卷] 消息传递

点分治

  • P3690 【模板】Link Cut Tree (动态树)

LCT

  • P6136 【模板】普通平衡树(数据加强版)

新码风 Splay

21/04/06

  • P3203 [HNOI2010]弹飞绵羊

LCT。建边,然后找根到该节点的路径长(一遍 access 和一遍 splay 即可)

  • P1501 [国家集训队]Tree II

注意标记的下传即可

21/04/07

  • P2870 [USACO07DEC]Best Cow Line G

SA。

21/04/08

  • P2852 [USACO06DEC]Milk Patterns G

SA,求出现超过 k 次的子串的最大长度,即为寻找每 k – 1 个相邻的 ht[i] 的最小值的最大值。可以使用 multiset<int> 维护。

  • P4149 [IOI2011]Race

点分治

  • P3812 【模板】线性基

线性基

  • HDU3949 XOR

线性基求异或 k

  • BZOJ#3513. [MUTC2013]idiots

求随机选三个数边长可以组成三角形的概率。正难则反,算不能拼成三角形的方案数。考虑自身卷积,并去重,得到两个木棍能拼出的方案数,然后再做一下前缀和,得到两边之和小于等于该边的方案数,对于所有木棍长度求个和就得到了不能的方案数,直接算即可。

  • BZOJ#2194. 快速傅立叶之二

推式子,C_k = \sum_{k\le i\lt n} a_ib_{i – k},推完之后换元化为卷积形式然后 FFT。

21/04/09

  • P2659 美丽的序列

单调栈

  • [AGC005B] Minimum Sum

单调栈

  • P4248 [AHOI2013]差异

SA 与单调栈

21/04/10 省选 Day 1

100 + [40, ?] + [0, 16] = [140, 156?]

炸干净了,T3 暴力爆炸了,希望 Day 2 能翻盘吧

最后修改日期: 2021年4月10日

作者

留言

撰写回覆或留言

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