省选计划

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
    • 牛顿莱布尼茨公式
    • 练习数学作业 - 2h
    • Simpson’s Integral
  • 偏导数 - 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