LWLAymh的备忘录

OI中的常见套路

发表于 2024-10-05 更新于 2025-04-15 分类于 OI Waline：

本质相同
- Example1
排列转环
- Example1(P8416)
- Example2
规定转移顺序
- Example1
- Example2(P7142)
复杂度均摊
- Example1
字典序相关
- Example1([2022noip十连测day8]8ady)
前缀和与差分
- Example1(loj3266)
- Example2
二分答案
- Example1([2022qbxt国庆Day6]kth)
- Example2
整体二分
- Example1([AGC002D]Stamp Rally)
- Example1(平面最近点对)
- Example2([CF1764G3] Doremy’s Perfect DS Class (Hard Version))
- Example3(XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan(opentraisn contest 1489)D Nice Set of Points)
- Example4([CF1442D]Sum)
- Example5(AGC044D)
倍增
- Example1([SCOI2015]国旗计划)
- Example4(loj3665)
- Example5(CF1707E)
- Example6([22zr提高组十连测day6]百分号)
对称/建立双射
- Example1(CF1627F)
- Example2([AH2017/HNOI2017]抛硬币)
- Example4(ARC115D)
- Example5(Hihocoder1230)
- Example6(23省选10连测 day5B)
拆多项式
- Example1([22zr提高组十连测day5]可)
抽屉原理
- Example1([UNR #6]小火车)
- Example2([NOI2021]量子通信)
拆贡献
- Example1([2022qbxt国庆Day7]fenwick)
- Example2([QOJ5097] 小 P 爱学习)
- Example3(Luogu4211 [LNOI2014]LCA)
二进制拆位
- Example1(Luogu5354 [Ynoi2017]由乃的OJ)
bitset优化暴力
- Example1([2022qbxt国庆Day4]D)
- Example2([NOI2020] 制作菜品)
简化能更新答案的集合
- Example1(CF1149D Abandoning Roads)
- Example2
- Example3
- Example4([Petrozavodsk Winter-2014. Moscow SU Tapir Contest(openstrain contest 1435) C]Combinations Strike Back)
- Example5([CF1621G]Weighted Increasing Subsequences)
- Example6(CF919F A Game With Numbers)
- Example7([IOI2014]holiday)
- Example8(CF1446D2)
- 支配对问题
  - 第一类支配对
    - Example1(luoguP7880 [Ynoi2006] rldcot)
    - Example2(luoguP8528 [Ynoi2003] 铃原露露)
  - 第二类支配对
奇偶染色
- Example1
- Example2(CF1521E)
- Example3(CF1615F)
- Example4(CF1517G)
捆绑更新答案
- Example1([2022qbxt国庆Day6]binary)
- Example2
单独更新答案
- Example1
- Example2([Petrozavodsk Summer-2015. Moscow IPT Contest(openstrain contest 1464) J]Two Airlines)
寻找不变量
- Example1([NOIP2021] 方差)
- Example2([AGC030E] Less than 3)
组合意义
- Example1(ARC110D)
- Example2(ABC231G)
- Example3(AGC060D)
复杂度抵消
- Example1(CF1439B)
寻找关系式
- Example1
特判边界
- Example1(2022ICPC杭州E)
摩尔投票
- Example1([CF643G]Choosing Ads)
寻找周期性
- Example1([CF1463F]Max Correct Set)
补集转化
- Example1
二进制分组
- Example1(loj3273)
- Example2(Luogu7447 [Ynoi2007] rgxsxrs)
- Example3(CF1515I Phoenix and Diamonds)

阅读全文 »

字符串

发表于 2024-10-05 更新于 2025-04-15 分类于 OI Waline：

KMP
- Example1(zr23省选第一轮集训day5b)
- Example2(NOI2014 动物园)
border理论
- 定理
  - 定理1
  - 定理2(周期引理)
  - 定理3
  - 定理4
  - 定理5
  - 定理6
- Example
  - Example1([POI2011]OKR-Periodicity)
SA
- Example1
ACAM
- Example1(uoj772企鹅游戏)
- Example2(loj3396 novel)
PAM
- 引理
- 算法
SAM

阅读全文 »

多项式与生成函数

发表于 2024-10-05 更新于 2025-04-15 分类于具体数学 Waline：

高数基础补档
- 复数相关
  - 分圆多项式
    - Example(尺规做正n边形问题)
- 泰勒展开
多项式
生成函数

阅读全文 »

图论

发表于 2024-10-05 更新于 2025-04-15 分类于 OI Waline：

约定
树的性质
圆方树的性质
任意图的性质
dsu on tree
- Example(QOJ5020)
最小生成树
- Example1(CF1550F Jumping Around)
Kruskal重构树
最短路
差分约束
- Example1([AGC056C] 01 Balanced)
2-SAT
- Example1(CF1697F)
- Example2(2021集训队互测序列)
对偶图
- Example1([CSP-S 2021] 交通规划)
广义串并联图/三度化
点分治
- Example1(CFgym101002K)
- 点分树的性质
  - Example1(codechef [BTREE])
  - Example2
边分治
- 边分树的性质
二分图

阅读全文 »

反演与容斥

发表于 2024-10-05 更新于 2025-04-15 分类于具体数学 Waline：

子集反演
- Example1(2019zrpzt七连day1D)
- Example2(有标号DAG计数)
二项式反演
斯特林反演
莫比乌斯反演
多重子集反演
单位根反演(离散傅里叶变换)
一般情况

阅读全文 »

博弈论

发表于 2024-10-05 更新于 2025-04-15 分类于 OI Waline：

Bash游戏
Nim游戏
- Example1(Nimk游戏)
- Example2(Multi-Nim游戏)
SG游戏
斐波那契博弈
二分图博弈
- Example1([2022qbxt国庆Day5]C)
树上博弈
- Example1(zr[23省选10连 day1] Clashmas)
散题

阅读全文 »

北大相关选拔数学真题汇总

发表于 2024-10-05 更新于 2025-04-15 分类于大学课程 Waline：

2024寒假学堂(部分)
- Problem4
  - Solution4
- Problem10
  - Solution10
- Problem11
  - Solution11
- Problem14
  - Solution14
- Problem15
  - Solution15
- Problem18
  - Solution18
- Problem19
  - Solution19
- Problem20
  - Solution20
2023强基(部分)
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem8
  - Solution8
- Problem10
  - Solution10
- Problem11
  - Solution11
- Problem12
  - Solution12
- Problem14
  - Solution14
- Problem15
  - Solution15
- Problem16
  - Solution16
- Problem17
  - Solution17
- Problem18
  - Solution18
- Problem19
  - Solution19
- Problem20
  - Solution20
2024强基(部分)
- Problem1
  - Solution1
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
- Problem8
  - Solution8
- Problem9
  - Solution9
- Problem11
  - Solution11
- Problem12
  - Solution12
- Problem20
  - Solution20
2022图选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
2023图选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
2024图选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
2019茶选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
2022茶选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
- Problem6
  - Solution6
2023茶选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
2024茶选
- Problem1
  - Solution1
- Problem2
  - Solution2
- Problem3
  - Solution3
- Problem4
  - Solution4
- Problem5
  - Solution5
- Problem6
  - Solution6

阅读全文 »

动态规划相关

发表于 2024-10-05 更新于 2025-04-15 分类于 OI Waline：

动态规划的设计
动态规划的优化

阅读全文 »