HBOI2018

省选计划

Posted by Panda2134's Blog on February 12, 2018

古人之观于天地、山川、草木、虫鱼、鸟兽，往往有得，以其求思之深而无不在也。夫夷以近，则游者众；险以远，则至者少。而世之奇伟、瑰怪，非常之观，常在于险远，而人之所罕至焉，故非有志者不能至也。有志矣，不随以止也，然力不足者，亦不能至也。有志与力，而又不随以怠，至于幽暗昏惑而无物以相之，亦不能至也。然力足以至焉，于人为可讥，而在己为有悔；尽吾志也而不能至者，可以无悔矣，其孰能讥之乎？此余之所得也。 ——王安石《游褒禅山记》

省选计划

省选知识点如下，希望大家能监督我QAQ

如果发现这边很久都没有打勾的话就在QQ上面喷我吧

以及如果看到我水群就让我回去学OI

希望能在省选之前把 $3/4$ 的勾打上吧……

暴力 - 3 days

  • 模拟退火
  • 爬山
  • DLX

动态规划 - 12.5 days

  • LCIS - 2h
  • 树上DP - 4 days
  • 数位DP - 2 days
  • 概率DP - 4 days - [ ] 复习换教室 - [x] 亚瑟王 - [ ] 概率充电器
  • 插头DP - 2 days
  • 斜率优化 - 1day
  • 四边形不等式 - 1day

图论 - 15 days

  • A*求k短路 - 3h
  • DFS - [ ] 2-SAT - 4h - [x] 点双联通分量 - 2h - [ ] 边双联通分量 - 2h - [x] 割点、桥 - 4h
  • 树 - [x] 树链剖分 - [ ] Link-cut Tree (做完QTREE) - 8h - [ ] Prufer编码（做2个Prufer+DP练手）- 3h - [x] 重心、直径（树网的核+加强版）- 5h - [x] 点分治 - 8h（needs improvement）
  • 网络流 - [x] 二分图 - [x] 看完蓝书网络流 + 做部分练习题 - 3 days - [ ] ppt题目 - 3 days - [x] 做历年各省省选网络流 - 3 days - [x] 网络流24题（除机器人路径规划+某个看不懂题面的题） - 1 day

数据结构 - 6 days

  • 单调栈、单调队列（复习） - 2h
  • 左偏树+pb_ds - 30min
  • hash_table（复习）- 30min
  • 并查集 - 1 day - [ ] 带权
  • 启发式合并 - 0.5 day(一定不能再错了！)
  • 01-Trie - 4h 2*Problems - [ ] Xor-Mex
  • 线段树 - 0.5 day - [x] Lazy-tag（做题） - [x] 动态开点 - [x] 线段树合并 - [x] 二维线段树（二维数点）
  • 平衡树 1 day - [x] Treap - [x] Splay - [ ] 可持久化平衡树 - [ ] 替罪羊树 - [ ] Template - [ ] 紫荆花之恋
  • 树套树 2 days - [x] 二逼平衡树 - [ ] Gty的妹子树 - [ ] 各省省选题目

数学 - 24 days

  • 数论 - 10.5 days - [ ] 看《具体数学》 - 5 days （求和和数论） - [ ] ExGCD - 1 day - [ ] Miller Rabin（复习) - 30min - [ ] Pollard Rho - 1h - [ ] BSGS - 4h 2*Problems - [ ] 线性筛（复习）1 day - [ ] 省选题 - [ ] CF某个F题 - [ ] 线性筛求积性函数 - [ ] 莫比乌斯反演 3 days - [ ] 省选题 - [x] CF某个G题 （被卡了）
  • 高等数学 - 9h
    • 导数基本公式 - 10min
      • 练习数学作业 - 2h
    • 牛顿莱布尼茨公式 \(\int_{a}^{b}f(x)\text{d}x = F(b) - F(a)\)
    • 练习数学作业 - 2h
    • Simpson’s Integral \(\int_{a}^{b}f(x)\text{d}x \approx \frac{b-a}{6} (f(a) + 4f(\frac{a+b}{2})+f(b))\)
  • 偏导数 - 1.5h - [ ] 泰勒公式（复习） - 20min - [ ] 抄5遍 - [ ] 与生成函数结合
    • 拉格朗日乘数法 - 1.5h
    • 拉格朗日插值法 - 1.5h

  • 多项式 4 days 1 h - [x] FFT,NTT（复习） - 30min - [x] MTT - 30min - [ ] 生成函数 - 2 days - [ ] 多项式除法，求逆，多点求值，求 $\exp$ ，求 $\ln$ - 2 days

  • 群论 - 1 day - [x] 各种定义 - [ ] Burnside Lemma & Polya Theorem（复习） - [ ] 例题

  • 博弈论 - [ ] Nim游戏 - 3 days - [ ] SG函数 - [ ] 做题

  • 线性代数 - [ ] 矩阵 - 3 days - [x] Gauss Elimination - [x] 矩阵快速幂 - [x] 行列式 - 2 days - [x] Matrix-Tree定理 - 2h - [ ] 线性基 - [ ] 其他

字符串 - 2.2 days

  • KMP（复习板子） - 20min
  • AC自动机（复习板子）- 20min - [x] 与DP结合 - 1 day
  • Manacher - 1h
  • 后缀数组 - 1 day - [x] LCP - [ ] 前几年NOI某题
  • 后缀自动机 ???

计算几何 - 9 days

  • 简单二维计算几何（还差一点点……） - 2h
  • 凸包 - 2 days
  • 半平面交 - 2 days
  • 旋转卡壳 - 1 day
  • 几何图形布尔运算 - 4 days
  • 三维计算几何 - [ ] 暂时弃疗

其他 - 6 days

  • 三分 - 1h
  • 哈夫曼树（复习） - 2h
    • 荷马史诗
  • cdq分治 - 3 days
  • 莫队 - 3 days
    • 普通莫队
    • 带修改莫队
    • 无修改莫队
    • 树上莫队
      • 糖果公园

2018.2.25:洛谷课上完的第一天，也是开学的一天。
该进入状态了。

  • 看完蓝书网络流
  • 写负权费用流
  • 写ppt题
    • bzoj3118
    • bzoj1937 - 找一天再写一遍。。。调太久了
  • 写省选题
    • Luogu-P2153
    • Luogu-P2053
    • Luogu-P3159

=> 睡觉 起晚了，而且有些别的事情，计划只弄了一半。。。明天弄完+把洛谷省选试炼场费用流做完

2018.2.26: 找时间填上多项式求逆的坑。 记得改模测T1…还有找3天填前几次cf的坑

  • 写省选题
    • Luogu-P2604
    • Luogu-P3980
    • Luogu-P2050（被卡常了……）
    • Luogu-P3980

2018.2.27:

  • 学Primal - Dual算法
  • Delight for a cat

2018.2.28:

  • 补习堆
    • 算法导论第六章
    • 堆排序
    • 用手写带decrease-key的二叉堆替换pb_ds写一遍Dijkstra
  • Luogu-P2754

2018.3.1

  • 模测T1
  • 打比赛
  • 补完之前的锅 80%
  • POJ chessboard - http://poj.openjudge.cn/challenge2/5/

2018.3.2

  • 整理网络流建模（天坑）

2018.3.3 - 2018.3.11

  • 做bzoj网络流题(约20道)

2018.3.13 - 2018.3.14

  • SHOI2017

2018.3.15

  • 看训练指南数学（除递推）

2018.3.16

  • 模拟退火 - [x] 吊打gty
  • 《入门经典》数论 - [x] 沙拉公主的困惑
  • 树上DP - [x] 骑士

2018.3.17

  • 树上DP - [x] 访问美术馆 - [x] [ZJOI2007]时态同步（其实是贪心……）
  • 修Blog

2018.3.18

  • 修Blog（终于不那么鬼畜了……404调了将近一天……）
  • 树网的核加强版

2018.3.19

  • 学斜率优化/决策单调性

  • 刷完洛谷训练场的DP!

2018.3.20

  • 亚瑟王
  • Problem a

2018.3.21

  • 虚树DP - [ ] 改世界树

2018.3.22

  • 数论 - [x] 看Sengxian的总结 - [ ] 训练场莫比乌斯反演
  • 点分治*2

2018.3.23

  • 喵星球上的点名
  • 试炼场主席树
  • 再写一遍永无乡
  • NEERC ‘16 M
  • 聪聪和可可

2018.3.26

  • 补EduRound A-F 题解
  • 熟练掌握 CDQ 分治

2018.3.27

  • 后缀数组模板
  • PoPoQQQ的莫比乌斯反演题
  • 1*后缀数组训练场题

2018.3.28

  • String - [x] 复习AC自动机 - [x] 喵星球上的点名 - [ ] 看完SA论文

2018.3.29 - 复习

  • AC自动机DP * 1（好像写成拓扑排序题了= =）
  • 练点分治
  • 试炼场期望题
  • 单调数据结构
  • 01-trie
  • 并查集
  • 整理网络流

2018.4.1

  • 重学矩阵和矩阵乘法优化DP
  • CF Edu Round补题
  • 数字计数！

复习：

周四开始

此前学完cdq分治和后缀数组，练树套树和点分治

写完PoPoQQQ的课件里的莫比乌斯反演

主要复习内容：

数据结构（试炼场+模板）
  • AC自动机
  • 打熟练LCT并做QTREE（时间不够就挑着做）
  • 特别是lazy-tag线段树！弱项！
    • (SDOI2017相关分析，过了就说明lazy-tag过关了)
网络流建模（练几个题目，看经典题，补完建模整理）
DP
  • 期望DP（试炼场！）
  • 矩阵快速幂优化DP
数学与递推
  • 重学矩阵，看懂例题
数论（看例题+整理）
写一个Simpson积分，一个三分
复习KMP
补题
  • 六省联考2017，CodeForces，vijos模拟赛

数据结构TODO:

  • 主席树
  • BIT/线段树
  • 树套树
  • QTREE
  • AC自动机
  • 后缀数组
  • 点分治

期望题TODO:

  • 概率充电器
  • bzoj3450
  • bzoj4318
  • cf518d
FEATURED TAGS
并查集 生成树 倍增LCA 字符串 KMP 单调栈 单调队列 动态规划 LIS 组合数学 LCS 序列型DP 二维平面DP 平衡树 二分 状压DP 数学 背包 递推 悬线法 排序 贪心 数论 树状数组 最短路 图论 构造 莫队 二分图 网络流 缩点 最小割 莫比乌斯反演 期望 线段树 高斯消元 斜率优化 分治 Codeforces 后缀数组 树链剖分 多项式 FFT 线性代数 常系数齐次线性递推 javascript
FRIENDS