题单 | Feijoa

基础与入门

欢迎来到基础与入门的世界，这里是程序员的修炼地，也是二次元迷们的算法战场。
在这里，每一行代码都可能召唤出萌妹子（Bug），每一个循环都可能触发技能（优化）。

双指针

D. Tandem Repeats? (1700 : 双指针暴力字符串)

模拟

A. Preparing for the Olympiad (200 : 模拟)
A. Be Positive (200 : 模拟)
B. Unconventional Pairs (400 : 模拟)
B. Journey (600 : 模拟)
A. Rook (800 : 模拟)
B. YetnotherrokenKeoard (1000 : 模拟)

贪心

A. Lever(200 : )
B. Alternating Series(200 : )
C. Rudolf and the Ugly String (900 : 字符串构造)
D. Arboris Contractio(1200 : 暴力)
C. Removal of Unattractive Pairs (1200 : 贪心)
E. Adjacent XOR(1400 : 暴力)
C. Watering an Array (1600 : 模拟)
D. Array Painting (1700 : )
F. Shift and Reverse (1800 : 贪心排序 STL)
F. Joker (2000 : 区间操作)

前缀和

D. A and B (1400 : 前缀和 guess)
E. Best Price (1600 : 前缀和)
C. Smilo and Minecraft (1700 : 二维前缀和)

二分

D. Jumping Through Segments (1400 : 二分贪心)
F. Unjust Binary Life (1600 ：二分 xor)
D. Counting Pairs (1600 : 二分)
E. Binary Search (1600 : 二分)
E. Rudolf and k Bridges (1600 : 二分贪心双指针)
F. Rudolf and Imbalance (1700 : 二分数学贪心)
F. Nezuko in the Clearing (1700 : 二分数学)

根号分治

构造

E. Good Triples (1600 : digsum)

小Tricks / 摩尔投票

169. 多数元素 (200 : 摩尔投票)
2780. 合法分割的最小下标 (1400 : 摩尔投票)
229. 多数元素 II (1400 : 摩尔投票)
G. Buratsuta 3 (2000 : 摩尔投票线段树)

数据结构

栈 / 队列 / 单调栈 / 单调队列

链表

哈希表 / 字典树 (Trie)

堆 (优先队列)

E. Kolya and Movie Theatre (1600 : 优先队列贪心)

并查集

(DSU / Union-Find)

树状数组

(Fenwick Tree)

H. Bro Thinks He’s Him (1900 : Fenwick 组合数学)

线段树

(含 Lazy / 可持久化 / 动态开点 / 线段树合并)

P3870 [TJOI2009] 开关 (1200 : 线段树)
P3740 [HAOI2014] 贴海报 (1600 : 线段树)
P2184 贪婪大陆 (1600 : 线段树类前缀和)
P1471 方差 (1600 : 线段树数学)
P1438 无聊的数列 (1700 : 线段树差分)
P4145 上帝造题的七分钟 2 / 花神游历各国 (1900 : 线段树特殊合并)
D. The Child and Sequence (2000 : 线段树特殊合并)

平衡树

(Treap / Splay / AVL / 红黑树)

可并堆

(左偏树, 配对堆)

ST 表 / RMQ / Sparse Table

莫队

图论

图论的世界，就是把各种奇奇怪怪的点和线拉在一起，然后问你：“你能走到终点吗？”
在这里，点可以代表城市、房间或者你家猫喜欢睡的沙发，线可以是道路、电线或者微信好友关系.
但同样的，点也可能不是点，图也可能不是图.

BFS

D. Rudolf and the Ball Game (1200 : bfs 搜索 dp)

DFS

G. Wafu! (1900 : dfs变种搜索 dp)
G. Lights (2200 : dfs 环涂色)

dijkstra

G. Rudolf and Subway (2000 : 虚点 dijkstra)

动态规划 (DP)

背包 DP

(01 / 完全 / 多重 / 分组)

区间 DP

(石子合并 / 括号匹配)

树形 DP

(树的直径 / 换根 DP)

状压 DP

(TSP / 集合覆盖 / 子集转移)

数位 DP

概率 DP / 期望 DP

线性 DP

(LIS / LCS)

DP 优化

(单调队列 / 斜率优化 / 四边形不等式)

字符串

KMP

Z-Algorithm

Manacher（最长回文子串）

后缀数组 (SA) + LCP

后缀自动机 (SAM)

字典树 / AC 自动机

回文自动机 (PAM)

字符串哈希 (Rolling Hash)

P10468 兔子与兔子 (1200 : 单字符串哈希)
P10474 [ICPC-Beijing 2011] Matrix 矩阵哈希 (1400 : 二维字符串哈希)

数论

欢迎来到数论的圣域，这里是程序员的炼金实验室，也是二次元魔法师的符文书。
每一个数字都可能隐藏秘密，每一个公式都可能爆发技能特效。准备好你的脑力与萌力！