学习资源¶
题单：https://kdocs.cn/l/cgWHLWmGVGFS
课件(包含代码)：https://www.jianguoyun.com/p/DSEJCNkQ-JizBhjopIoE
2021-10-17 BIT&RMQ&Treap&笛卡尔树¶
树状数组
POJ2299 Ultra-QuickSort
POJ3321 Apple Tree
[CQOI2006]简单题
POJ2481 Cows
[JSOI2009]计数问题
[USACO17JAN P]Promotion Counting
RMQ
[USACO07JAN G]Balanced Lineup
NOIP2011 选择客栈
Frequent Values, POJ3368
BST
Efficient Solutions, UVa11020 用 Multiset
POJ1785 Binary Search Heap Construction 用笛卡尔树
POJ2559 Largest Rectangle in a Histogram 用笛卡尔树
Graph and Queries, Tianjin 2010, HDU3726 用 Treap
二分图判断：
Codeforces 687A:
https://codeforces.com/problemset/problem/687/A
2021-11-07 String Hashing¶
课件：TG_C3_03_HASH_v2021.pdf
入门级别：
Seek the Name, Seek the Fame, POJ2752 http://poj.org/problem?id=2752
Power Strings, POJ2406 http://poj.org/problem?id=2406
Stammering Aliens, SWERC 2009, POJ3882 http://poj.org/problem?id=3882
[USACO17 OPEN G]Bovine Genomics https://www.luogu.com.cn/problem/P3667
金牌级别：
HDU5732 Subway https://acm.hdu.edu.cn/showproblem.php?pid=5732
[CEOI2017]Palindromic Partitions https://www.luogu.com.cn/problem/P4656
[USACO16 JAN G]Lights Out https://www.luogu.com.cn/problem/P3134
[COCI2016-2017#4] Osmosmjerka https://www.luogu.com.cn/problem/P7538
[COCI2020-2021#3] Sateliti https://www.luogu.com.cn/problem/P7170
Baltic OI 2018 – Genetics https://open.kattis.com/problems/genetics2
2021-11-14 线段树¶
TGC3.2线段树-V2021.pdf
| POJ2828-Buy Tickets | http://poj.org/problem?id=2752 |
|---|---|
| Ray,Pass me the Dishes, UVa1400 | https://www.luogu.com.cn/problem/UVA1400 |
| POJ3468 A Simple Problem with Integers | http://poj.org/problem?id=3468 |
| USACO13Jan G, P3. Seating | https://www.luogu.com.cn/problem/P3071 |
| 维护序列(AHOI 2009) | https://www.luogu.com.cn/problem/P2023 |
| [NOIOnline2020 #2 提高] ：子序列问题 | https://www.luogu.com.cn/problem/P6477 |
|---|---|
| USACO14March G, P1 The Lazy Cow | https://www.luogu.com.cn/problem/P4876 |
| IOI 2014 – Wall | https://www.luogu.com.cn/problem/P4560 |
| USACO14Dec G, P2 Marathon | https://www.luogu.com.cn/problem/P3113 |
| [POI2014]KAR-Cards | https://www.luogu.com.cn/problem/P3569 |
| COCI 2020/2021 #5 – Sjeckanje | https://www.luogu.com.cn/problem/P7402 |
2021121-一维 DP¶
C09 提高级-线性 DP-V2021.pdf
| USACO 2017 Jan G, Hoof, Paper, Scissors | https://www.luogu.com.cn/problem/P3609 |
|---|---|
| USACO 2020 Jan G, Time is Mooney | https://www.luogu.com.cn/problem/P6005 |
| USACO 2018 Dec, G Teamwork | https://www.luogu.com.cn/problem/P5124 |
| USACO 2019 Open G, Snakes | https://www.luogu.com.cn/problem/P5424 |
| Partitioning by Palindromes, UVa11584 | https://www.luogu.com.cn/problem/UVA584 |
| Lighting System Design, UVa11400 | https://www.luogu.com.cn/problem/UVA11400 |
| IOI '04 P4 – Phidias | https://vjudge.net/problem/SPOJ-PHIDIAS |
|---|---|
| USACO 2016 Feb G, Circular Barn Revisited | https://www.luogu.com.cn/problem/P3140 |
| USACO 2018 Feb G, Taming the Herd | https://www.luogu.com.cn/problem/P4267 |
| USACO 2019 Dec G, Moortal Cowmbat | https://www.luogu.com.cn/problem/P5839 |
| USACO 2016 Dec P, Team Building | https://www.luogu.com.cn/problem/P2098 |
| Color Length, Daejeon 2011, UVa1625 | https://www.luogu.com.cn/problem/UVA1625 |
| Barisal Stadium, UVa10641 | https://www.luogu.com.cn/problem/UVA10641 |
20211128-贪心算法¶
课件：C0802贪心_提高&NOI 级-V2021.pdf
20211205-搜索类问题¶
课件：C07暴力求解与搜索提高级-V2021.pdf
| 困难的串（Krypton Factor, UVa129） | https://www.luogu.com.cn/problem/UVA129 |
|---|---|
| 骑士移动(Knight Moves, POJ1915) | http://poj.org/problem?id=1915 |
| The Morning after Halloween, UVa1601) | https://www.luogu.com.cn/problem/UVA1601 |
| 天平难题(Mobile Computing, UVa1354) | https://www.luogu.com.cn/problem/UVA1354 |
| 编辑书稿(Editing a Book,UVa11212) | https://www.luogu.com.cn/problem/UVA11212 |
| 旋转游戏(The Rotation Game,UVa1343) | https://www.luogu.com.cn/problem/UVA1343 |
| 快速幂计算(Power Calculus, ,UVa1374) | https://www.luogu.com.cn/problem/UVA1374 |
| Lattice Animals, NEERC2004, UVa1602 | https://www.luogu.com.cn/problem/UVA1602 |
| Pipeline Scheduling, UVa690 | https://www.luogu.com.cn/problem/UVA690 |
| 破坏正方形(Square Destroyer, UVa1603) | https://www.luogu.com.cn/problem/UVA1603 |
20211212-区间 DP¶
课件：C09_提高级-区间 DP-v2021.pdf
| [NOI1995] 石子合并 | https://www.luogu.com.cn/problem/P1880 |
|---|---|
| POJ1159 Palindrome | http://poj.org/problem?id=1159 |
| POJ2955 Brackets | http://poj.org/problem?id=2955 |
| Brackets Sequence, NEERC2001,UVa1626 | https://www.luogu.com.cn/problem/UVA1626 |
| HDU4283 You Are the One | https://acm.hdu.edu.cn/showproblem.php?pid=4283 |
| [NOIP2006 提高组] 能量项链 | https://www.luogu.com.cn/problem/P1063 |
| [CQOI2007]涂色 | https://www.luogu.com.cn/problem/P4170 |
| USACO2016 Open, G P3. 248 | https://www.luogu.com.cn/problem/P3146 |
| HDU2476 String painter | https://acm.hdu.edu.cn/showproblem.php?pid=2476 |
|---|---|
| POJ2292 Optimal Keypad | http://poj.org/problem?id=2292 |
| [NOIP2007 提高组] 矩阵取数游戏 | https://www.luogu.com.cn/problem/P1005 |
| 串折叠(Folding, NEERC 2001, UVa1630) | https://www.luogu.com.cn/problem/UVA1630 |
| CF077B Zuma | https://codeforces.com/problemset/problem/607/B |
| 阿里巴巴(Alibaba, SEERC2004,UVa1632) | https://www.luogu.com.cn/problem/UVA1632 |
| USACO2019Dec P, P1. Greedy Pie Eaters | https://www.luogu.com.cn/problem/P5851 |
| [SDOI2008] Sue 的小球 | https://www.luogu.com.cn/problem/P2466 |
| USACO2017Jan P, P3 Subsequence Reversal | https://www.luogu.com.cn/problem/P3607 |
20211219-图论 DFS¶
课件：C06图论 DFS 应用提高&NOI 级.pdf
| 基础 DFS | kattis Birthday Party | https://open.kattis.com/problems/birthday |
|---|---|---|
| 树染色问题 | USACO2019 Jan, S P1. Grass Planting | https://www.luogu.com.cn/problem/P5197 |
| 图染色问题 | USACO2019 Feb B P2. The Great Revegetation | https://vjudge.net/problem/Gym-331106T |
| 树上思维 | USACO2019 Open, B P2. Milk Factory | https://vjudge.net/problem/Gym-331106W |
| 编程实现 | USACO2019 Dec, B P3. Livestock Lineup | https://www.luogu.com.cn/problem/P5833 |
| DFS 思维 | Tree Reconstruction,UVa10410 | https://www.luogu.com.cn/problem/UVA10410 |
| 二分图 | CF862B Mahmoud and Ehab and the bipartiteness | https://codeforces.com/contest/862/problem/B |
| 二分图 | CF1176E Cover it! | https://www.luogu.com.cn/problem/CF1176E |
| 欧拉道路 | Inspector'sDilemma, Dhaka2007, UVa12118 | https://www.luogu.com.cn/problem/UVA12118 |
| DFS | SWERC Birdwatching | https://codeforces.com/gym/102501/problem/K |
|---|---|---|
| 树上思维 | USACO2019 Open, B P3. Cow Evolution | https://vjudge.net/problem/Gym-331106X |
| 树上思维 | USACO2018 Open, B P3. Family Tree | https://vjudge.net/problem/Gym-331106L |
| 补图计算 | CF920E. Connected Components? | https://codeforces.com/problemset/problem/920/E |
| 二分图染色 | Baltic OI 2020 – Graph | https://www.luogu.com.cn/problem/P6696 |
| DFS | Spreadsheet Calculator, WF1992, UVa215 | https://www.luogu.com.cn/problem/UVA215 |
| 二分图染色 | APIO 2011 - Table Coloring | https://www.luogu.com.cn/problem/P3631 |
20220103-Floodfill & BFS
课件：C06图论_floodfillBFS提高 NOI 级.pdf
| FloodFill | USACO2017 Open S Where's Bessie? | https://www.luogu.com.cn/problem/P3671 |
|---|---|---|
| FloodFill | USACO2017FebS. Why Did the Cow Cross the Road III | https://www.luogu.com.cn/problem/P3663 |
| BFS/模拟 | USACO 2018 Dec S. Mooyo Mooyo | https://www.luogu.com.cn/problem/P5121 |
| BFS/模拟 | USACO2021 Feb S. Comfortable Cows | https://www.luogu.com.cn/problem/P7411 |
| BFS/状态压缩 | USACO 2021 Open S Maze Tac Toe | https://www.luogu.com.cn/problem/P7555 |
| BFS | USACO 2018 Open, S. Multiplayer Moo | https://www.luogu.com.cn/problem/P4380 |
| 多段 BFS | USACO2014 Dec S. Piggyback | https://www.luogu.com.cn/problem/P3110 |
| BFS/模拟 | USACO 2015 Dec G. Bessie's Dream | https://www.luogu.com.cn/problem/P4818 |
| BFS/模拟 | USACO 2016 Dec G. Lasers and Mirrors | https://www.luogu.com.cn/problem/P3036 |
|---|---|---|
| BFS/分层图 | USACO 2021 Jan Gold. Telephone | https://www.luogu.com.cn/problem/P7297 |
| 二分/BFS | IOI2009 - Mecho | https://oj.uz/problem/view/IOI09_mecho |
| BFS/状态压缩 | USACO2017 Jan G. Cow Navigation | https://www.luogu.com.cn/problem/P3610 |
| BFS/思维 | USACO 2020 Dec G. Replication | https://www.luogu.com.cn/problem/P7151 |
| BFS/思维 | USACO 2017 Dec G. A Pie for a Pie | https://www.luogu.com.cn/problem/P4083 |
20220123-二分搜索算法
| 派(Pie, NWERC2006, POJ3311) | https://open.kattis.com/problems/pie | |
|---|---|---|
| USACO 2017 Jan S P1. Cow Dance Show | 离散事件模拟 | https://www.luogu.com.cn/problem/P3611 |
| USACO 2020 Open S P1. Social Distancing | 贪心 | https://www.luogu.com.cn/problem/P6281 |
| CF702C Cellular Network | https://codeforces.com/contest/702/problem/C | |
| CEOI2012 - Job Schedulingfor | 贪心,任务规划 | https://www.luogu.com.cn/problem/P6092 |
| CF1223C Save the Nature | 贪心 | https://codeforces.com/problemset/problem/1223/C |
| Caravan Robbers, NEERC 2012, UVa1616 | 区间选择 | https://www.luogu.com.cn/problem/UVA1616 |
| POJ2796 Dropping tests | 分数规划 | http://poj.org/problem?id=2976 |
| CF1486D Max Median | 中位数判断 | https://codeforces.com/problemset/problem/1486/D |
|---|---|---|
| Copying Books, UVa714 | 贪心 | https://www.luogu.com.cn/problem/UVA714 |
| BalticOI2012 - Mobile | 几何思维 | https://www.luogu.com.cn/problem/P7249 |
| CF780B The Meeting Place Cannot Be Changed | 区间贪心 | https://codeforces.com/contest/782/problem/B |
| CF847B. Preparing for Merge Sort | 模拟 | https://codeforces.com/contest/847/problem/B |
| CF847E Packmen | 贪心 | https://codeforces.com/contest/847/problem/E |
| USACO 2016 Feb P P1. Load Balancing | BIT, 贪心 | https://www.luogu.com.cn/problem/P6172 |
| CF1117C Magic Ship | 模型转换 | https://codeforces.com/problemset/problem/1117/C |
20220213-图论之并查集¶
| UVa1160 X-Plosives | 模板题 | https://www.luogu.com.cn/problem/UVA1160 |
|---|---|---|
| USACO2016 DecG P1. Moocast | MST | https://www.luogu.com.cn/problem/P2847 |
| USACO2016 OpenG P2. Closing the Farm | 离线 | https://www.luogu.com.cn/problem/P6121 |
| POJ1962 Corporative Network | 加权并查集 | http://bailian.openjudge.cn/practice/1962?lang=en_US |
| USACO2020 Jan S P3. Wormhole Sort | 连通性 | https://www.luogu.com.cn/problem/P6004 |
| USACO2013 Feb S P2. Tractor | MST | https://www.luogu.com.cn/problem/P3073 |
| USACO2018 Jan G P1. MooTube | 离线算法 | https://www.luogu.com.cn/problem/P4185 |
| USACO 2014 Jan G P3. Ski Course Rating | 连通性 | https://www.luogu.com.cn/problem/P3101 |
| UVa10158 - War | 二分图 | https://www.luogu.com.cn/problem/UVA10158 |
| USACO2020 Open G P2. Favorite Colors | 图的合并 | https://www.luogu.com.cn/problem/P6279 |
| Baltic OI 2016 Park | 几何思维 | https://www.luogu.com.cn/problem/P4675 |
20220220-DAGDP&SCC&2SAT¶
20220227-基础数论¶
https://www.jianguoyun.com/p/DSEJCNkQ-JizBhjopIoE
做过的口胡题解即可！找自己不会的做起！
偏基础部分：：
| UVa10168, Summation of Four Primes | 提高 | https://www.luogu.com.cn/problem/UVA10168 |
|---|---|---|
| UVa10871, Primed Subsequence | 普及 | https://www.luogu.com.cn/problem/UVA10871 |
| POJ1401 Factorial | 提高 | http://bailian.openjudge.cn/practice/1401/ |
| 课件：C1001基础数论_提高组_v2022.pdf[NOIP2009 提高组] Hankson 的趣味题 | 提高 | https://www.luogu.com.cn/problem/P1072 |
| POJ2115, C Looooops | 提高 | http://bailian.openjudge.cn/practice/2115/ |
| P4549 【模板】裴蜀定理(要求严格证明) | 提高- | https://www.luogu.com.cn/problem/P4549 |
| CF1514C Product 1 Modulo N | 提高- | https://codeforces.com/problemset/problem/1514/C |
| CF1225D Power Products | 提高 | https://codeforces.com/problemset/problem/1225/D |
| [NOIP2017 提高组] 小凯的疑惑 | 提高 | https://www.luogu.com.cn/problem/P3951 |
| [NOIP2012 提高组] 同余方程 | 提高- | https://www.luogu.com.cn/problem/P1082 |
| UVA294 Divisors | 提高 | https://www.luogu.com.cn/problem/UVA294 |
| [AHOI2005]约数研究 | 普及- | https://www.luogu.com.cn/problem/P1403 |
相对难题！！：
| Trees in a Wood, UVa10214 | 提高 | https://www.luogu.com.cn/problem/UVA10214 |
|---|---|---|
| GCD Extreme（II）,UVa11426 | 提高+ | https://www.luogu.com.cn/problem/UVA11426 |
| CF1536C Diluc and Kavya | 提高 | https://codeforces.com/problemset/problem/1536/C |
| CF1349A Orac and LCM | 提高+ | https://codeforces.com/problemset/problem/1349/A(要求严格证明，要求空间复杂度O(1)!!) |
| CF1499D The Number of Pairs | 提高+ | https://codeforces.com/problemset/problem/1499/D |
| A Horrible Poem，POI2012 | NOI- | https://www.luogu.com.cn/problem/P3538 |
| [TJOI2009] 猜数字(不允许快速乘法或高精) | 提高 | https://www.luogu.com.cn/problem/P3868 |
| Code Feat, UVa11754 | 提高+ | https://www.luogu.com.cn/problem/UVA11754 |
20220306 栈&滑动窗口
C0601数据结构-栈_提高_v2022.pdf
C0803滑动窗口.pdf
| 单调栈 | CEOI 2011 – Balloons | 提高+ | https://www.luogu.com.cn/problem/P4697 |
|---|---|---|---|
| 单调栈 | CF1412A CEOI 2020 - Fancy Fence | NOI- | https://www.luogu.com.cn/problem/P6801 |
| 括号序列 | USACO 2017 Open S - Modern Art 2 | 提高+ | https://www.luogu.com.cn/problem/P3668 |
| 单调栈 | CF gym101102D Rectangles, ACPC2016 | 提高+ | https://codeforces.com/gym/101102/problem/D |
| 单调栈 | IOI 2004 - Empodia | NOI- | https://www.luogu.com.cn/problem/P5923 |
| 滑动窗口 | USACO 2016 Jan P. Fort Moo | 提高+ | https://www.luogu.com.cn/problem/P3135 |
|---|---|---|---|
| 扫描线 | APIO 2015 - Palembang Bridges | NOI- | https://www.luogu.com.cn/problem/P3644 |
| 扫描线 | USACO 2019 Feb G. Painting the Barn | NOI- | https://www.luogu.com.cn/problem/P6100 |
| 扫描线 | APIO 2009 - Digging for Oil | NOI- | https://www.luogu.com.cn/problem/P3625 |
| 扫描线 | IOI 2005 - Garden | 提高+ | https://www.spoj.com/problems/IOIGARD/en/ |
20220313 背包 DP
| 01 背包转化 | USACO 2015 Dec G. Fruit Feast | 提高- | https://www.luogu.com.cn/problem/P4817 |
|---|---|---|---|
| 01 背包转化 | CF837D Round Subset | 提高- | http://codeforces.com/contest/837/problem/D |
| 01 背包转化 | CEOI2018 Cloud Computing | 提高 | https://www.luogu.com.cn/problem/P6359 |
| 完全背包方案数 | [NOIP2018 提高组] 货币系统 | 提高 | https://www.luogu.com.cn/problem/P5020 |
| 01 背包转化 | USACO 2020 Open G. Exercise | 提高+ | https://www.luogu.com.cn/problem/P6280 |
| 完全背包方案数 | USACO 2019 Jan G. Cow Poetry | 提高+ | https://www.luogu.com.cn/problem/P5196 |
| 01 背包转化 | POI2004 - Maximal Orders of Permutations | NOI- | https://www.luogu.com.cn/problem/P5919 |
| 分数规划 | USACO 2018 Open G. Talent Show | 提高+ | https://www.luogu.com.cn/problem/P4377 |
| 分组背包 | [BJOI2019] 排兵布阵 | 提高+ | https://www.luogu.com.cn/problem/P5322 |
20220320-DFS 序&欧拉序列¶
课件：C11_DFS 序&欧拉序列_v2022.pdf
| 投入时间 | ||||
|---|---|---|---|---|
| < 0.5h | 时间戳 | 祖孙询问(LOJ10135) | 提高 | https://loj.ac/p/10135 |
| < 0.75h | 时间戳 | AtCoder abc202 E Count Descendants | 提高+ | https://atcoder.jp/contests/abc202/tasks/abc202_e |
| <1h | 欧拉序列 | USACO 2019 Feb G. Cow Land | 提高+ | https://www.luogu.com.cn/problem/P6098 |
| <2h | 欧拉序列 | USACO 2019 Dec G. Milk Visits(离线算法) | 提高+ | https://www.luogu.com.cn/problem/P5838 |
| 投入时间 | ||||
|---|---|---|---|---|
| <1h | 欧拉序列 | USACO 2019 Dec G. Milk Visits(禁止离线算法) | NOI- | https://www.luogu.com.cn/problem/P5838 |
| <1h | 时间戳 | [SDOI2015]寻宝游戏 | NOI- | https://www.luogu.com.cn/problem/P3320 |
| <1h | 时间戳 | USACO 2019 Dec P. Bessie's Snow Cow | NOI- | https://www.luogu.com.cn/problem/P5852 |
| <2h | 欧拉序列 | IOI2009 – Regions | NOI | https://www.luogu.com.cn/problem/P5901 |
| <1.5h | 时间戳 | CF838B Diverging Directions | NOI- | https://codeforces.com/contest/838/problem/B |
20220327-线性代数¶
课件：TGC2.7矩阵和线性方程组_v2022.pdf
| 0.5h | 矩阵乘法 | [TJOI2017]可乐 | 图上路径数 | 提高 | https://www.luogu.com.cn/problem/P3758 |
|---|---|---|---|---|---|
| 1h | 矩阵乘法 | Recurrences,UVa10870 | 伴随矩阵 | 提高+ | https://www.luogu.com.cn/problem/UVA10870 |
| 1h | 矩阵乘法 | USACO2007 Nov G. Cow Relay | Floyd 加速 | 提高+ | https://www.luogu.com.cn/problem/P2886 |
| 1h | 矩阵乘法 | [2020-NOI Online #3 提高组] 魔法值 | DP 加速 | 提高+ | https://www.luogu.com.cn/problem/P6569 |
| 0.5h | 矩阵乘法 | CF691E Xor-sequences | DP 加速 | 提高 | https://codeforces.com/contest/691/problem/E |
| 0.5h | 高斯消元 | [JSOI2008]球形空间产生器 | 方程转换 | 提高+ | https://www.luogu.com.cn/problem/P4035 |
| 0.5h | 矩阵乘法 | [TJOI2019]甲苯先生的字符串 | 路径统计 | 提高+ | https://www.luogu.com.cn/problem/P5337 |
|---|---|---|---|---|---|
| 0.75h | 高斯消元 | 乘积是平方数(Square, UVa11542) | 异或方程 | NOI- | https://www.luogu.com.cn/problem/UVA11542 |
| 2h | 矩阵线段树 | CF718C. Sasha and Array | 斐波那契 | NOI- | https://codeforces.com/problemset/problem/718/C |
| 1h | 矩阵乘法 | Balkan OI 2009 - Reading | 分层图 | NOI- | https://www.luogu.com.cn/problem/P6841 |
| 0.25h | 高斯消元 | [JSOI2008]球形空间产生器 | 方程转换 | 提高+ | https://www.luogu.com.cn/problem/P4035 |
| 1h | 高斯消元 | [SDOI2010] 外星千足虫 | 异或方程 | 提高+ | https://www.luogu.com.cn/problem/P2447 |
| 1h | 矩阵乘法 | Recurrences,UVa10870 | 伴随矩阵 | 提高+ | https://www.luogu.com.cn/problem/UVA10870 |
2022-0403-状态压缩 DP-A¶
课件：C09_05-状态压缩 DP-v2022.pdf
| 0.75h | 位集合 | UVa10911 Forming Quiz Teams | 提高 | https://www.luogu.com.cn/problem/UVA10911 |
|---|---|---|---|---|
| 0.5h | 货郎挑担 | UVa10944 Nuts for nuts.. | 提高 | https://www.luogu.com.cn/problem/UVA10944 |
| 0.5h | 货郎挑担 | Codeforces Gym 100648B Hie with the Pie | 提高 | https://codeforces.com/gym/100648 |
| 1.5h | 货郎挑担 | Kattis Cat & Mice | 提高+ | https://open.kattis.com/problems/catandmice |
| 1h | 行压缩 | USACO06 Nov G Corn Fields | 提高+ | https://www.luogu.com.cn/problem/P1879 |
| 2h | 无后效性 | USACO 2021 Jan G. Uddered but not Herd | 提高+ | https://www.luogu.com.cn/problem/P7296 |
| 1.5h | 二进制串 | UVa1633 Dyslexic Gollum | 提高+ | https://www.luogu.com.cn/problem/UVA1633 |
| 1h | 货郎挑担 | Kattis Cat & Mice | 提高+ | https://open.kattis.com/problems/catandmice |
|---|---|---|---|---|
| 1h | 无后效性 | USACO 2021 Jan G. Uddered but not Herd | 提高+ | https://www.luogu.com.cn/problem/P7296 |
| 1h | 二进制串 | UVa1633 Dyslexic Gollum | 提高+ | https://www.luogu.com.cn/problem/UVA1633 |
| 1.5h | DP | CCF NOI Online 2020 #3 优秀子序列 | NOI- | https://www.luogu.com.cn/problem/P6570 |
| 1.5h | 位集合 | USACO 2022 Feb G. Redistributing Gifts | NOI- | https://www.luogu.com.cn/problem/P8189 |
| 1h | 位集合 | USACO 2015 Jan G. Moovie Mooving | NOI- | https://www.luogu.com.cn/problem/P3118 |
2022-0410-BIT&IndexedSet¶
TG_C3_02_BIT&IndexedSet 提高&NOI 级_v2022.pdf
| 0.5h | POJ2352 Stars | 普及 | 点坐标维护 | http://bailian.openjudge.cn/practice/2352?lang=en_US |
|---|---|---|---|---|
| 0.5h | POJ2299 Ultra-QuickSort | 提高 | 逆序对 | http://bailian.openjudge.cn/practice/2299?lang=en_US |
| 0.5h | SEERC 2006 Japan | 提高 | 逆序对 | https://vjudge.net/problem/UVALive-2926 |
| 0.5h | Kattis Mega Inversions | 提高 | 逆序对 | https://vjudge.net/problem/Kattis-megainversions |
| 1h | USACO 2020 Open G. Haircut | 提高+ | 逆序对 | https://www.luogu.com.cn/problem/P6278 |
| 1h | POJ3321 Apple Tree | 提高+ | DFS 序列 | http://poj.org/problem?id=3321 |
| 0.5h | [CQOI2006]简单题 | 提高 | 差分序列 | https://www.luogu.com.cn/problem/P5057 |
| 0.5h | POJ2481 Cows | 提高 | 区间嵌套 | http://bailian.openjudge.cn/practice/2481?lang=en_US |
| 0.5h | [JSOI2009]计数问题 | 提高 | 二维 BIT | https://www.luogu.com.cn/problem/P4054 |
| 0.5h | [SDOI2009]HH 的项链 | 提高+ | 离线算法 | https://www.luogu.com.cn/problem/P1972 |
|---|---|---|---|---|
| 0.5h | [USACO17JAN P]Promotion Counting | 提高+ | DFS 序列 | https://www.luogu.com.cn/problem/P3605 |
| 0.5h | USACO 2017 Feb P1. Why Did the Cow Cross the Road | 提高+ | https://www.luogu.com.cn/problem/P3656 | |
| 1h | USACO 2017 Feb G3. Why Did the Cow Cross the Road III | 提高+ | 区间嵌套 | https://www.luogu.com.cn/problem/P3660 |
| 1h | USACO 2019 Jan G. Sleepy Cow Sorting | NOI- | https://www.luogu.com.cn/problem/P5200 | |
| 1.5h | [POI2015]LOG | NOI- | 贪心 | https://www.luogu.com.cn/problem/P3586 |
2022-0417-倍增 LCA¶
TG_C3_05_LCA_v2022.pdf
注意：所有题目禁止使用树链剖分以及 LCT 等复杂结构。
| 1h | 聚会(AHOI 2008) | 提高 | https://www.luogu.com.cn/problem/P4281 |
|---|---|---|---|
| 1h | Lightning Energy Report, Jakarta2010, UVa1674 | 提高 | https://www.luogu.com.cn/problem/UVA1674 |
| 1h | Network(POJ3417) | 提高+ | http://poj.org/problem?id=3417 |
| 0.5h | USACO 2012 Dec G. Running Away From the Barn | 提高+ | https://www.luogu.com.cn/problem/P3066 |
| 1h | CFGYM102694C Sloth Naptime | 提高+ | https://codeforces.com/blog/entry/81527 |
| 1.5h | CF609E Minimum spanning tree for each edge | 提高+ | https://www.luogu.com.cn/problem/CF609E |
| 1h | [ZJOI2012]灾难 | NOI- | https://www.luogu.com.cn/problem/P2597 | |
|---|---|---|---|---|
| 1h | [NOIP2015 提高组] 运输计划 | NOI- | https://www.luogu.com.cn/problem/P2680 | |
| 2h | Rikka with Intersection of Paths, CF Gym 102012G(要求详细题解) | NOI- | https://codeforces.com/gym/102012/problem/G | |
| 1h | USACO 2018 Feb P. New Barns | NOI- | https://www.luogu.com.cn/problem/P4271 | |
| 1.5h | USACO 2019 Jan P. Exercise Route(要求详细题解) | NOI- | 倍增 | https://www.luogu.com.cn/problem/P5203 |
| 1h | USACO 2018 Open P. Disruption | NOI- | https://www.luogu.com.cn/problem/P4374 |
2022-0430-组合数学¶
C1002组合数学之-递推计数_v2022.pdf
| 0.2h | 组合数 | NOIP2011 提高组 计算系数 | 普及 | https://www.luogu.com.cn/problem/P1313 |
|---|---|---|---|---|
| 0.25h | 组合数 | NOIP2016 提高组 组合数问题 | 提高 | https://www.luogu.com.cn/problem/P2822 |
| 0.25h | 乘法原理 | [HNOI2008]越狱 | 提高 | https://www.luogu.com.cn/problem/P3197 |
| 0.5h | 多重排列 | POJ3421 X-factor Chains | 提高 | http://poj.org/problem?id=3421 |
| 1h | 错位排列 | [SDOI2016]排列计数 | 提高 | https://www.luogu.com.cn/problem/P4071 |
| 0.5h | 重复选择问题 | UVa10910 Marks Distribution | 提高 | https://www.luogu.com.cn/problem/UVA10910 |
| 0.5h | 递推计数 | UVA1510 Neon Sign | 提高 | https://www.luogu.com.cn/problem/UVA1510 |
| 1.5h | 容斥原理 | UVa11806 Cheerleaders | 提高+ | https://www.luogu.com.cn/problem/UVA11806 |
| 0.5h | 递推计数 | UVa11401 Triangle Counting | 提高 | https://www.luogu.com.cn/problem/UVA11401 |
| 1h | 二项式系数 | Irrelevant Elements, NEERC 2004 | 提高 | http://bailian.openjudge.cn/practice/2167?lang=en_US |
| 1h | Binomial coefficients, NWERC2011 | 提高+ | https://www.luogu.com.cn/problem/UVA1649 | |
|---|---|---|---|---|
| 1h | [AHOI2012]树屋阶梯 | 提高+ | https://www.luogu.com.cn/problem/P2532 | |
| 0.5h | [HAOI2008]硬币购物 | 提高+ | https://www.luogu.com.cn/problem/P1450 | |
| 1h | CF1332E Height All the Same | NOI- | https://codeforces.com/problemset/problem/1332/E | |
| 1h | [HNOI2009]有趣的数列 | 排队问题 | NOI- | https://www.luogu.com.cn/problem/P3200 |
| 1h | SWERC-2019 Counting Trees | 树统计 | NOI- | https://codeforces.com/gym/102501/problem/J |
| 0.75h | [GXOI/GZOI2019]逼死强迫症 | NOI- | https://www.luogu.com.cn/problem/P5303 | |
| 1.5h | [JLOI2016]成绩比较(写出详细推导，仅使用基本的计数逻辑) | NOI- | https://www.luogu.com.cn/problem/P3270 |
2022-0504-MST¶
C1102_MST提高&NOI 级_v2022.pdf
| USACO 2015 Feb S. Superbull | 提高 | https://www.luogu.com.cn/problem/P4826 |
|---|---|---|
| Slim Span, ACM/ICPC Japan 2007 | 提高+ | https://www.luogu.com.cn/problem/UVA1395 |
| POJ2349 Arctic Network | 提高 | http://bailian.openjudge.cn/practice/3417/ |
| [JSOI2010]部落划分 | 提高 | https://www.luogu.com.cn/problem/P4047 |
| USACO 2016 Feb G. Fenced In | 提高 | https://www.luogu.com.cn/problem/P6171 |
| USACO 2019 Open G. I Would Walk 500 Miles | 提高 | https://www.luogu.com.cn/problem/P5425 |
| Buy or Build, SWERC 2005, UVa1151 | 提高+ | https://www.luogu.com.cn/problem/UVA1151 |
| CF472D Design Tutorial: Inverse the Problem | 提高+ | https://codeforces.com/contest/472/problem/D |
|---|---|---|
| HDU3367 Pseudoforest | 提高+ | https://acm.hdu.edu.cn/showproblem.php?pid=3367 |
| Qin Shi Huang's National Road System, UVa1494 | 提高+ | https://www.luogu.com.cn/problem/UVA1494 |
| CF1513D GCD and MST | 提高+ | https://codeforces.com/problemset/problem/1513/D |
| USACO 2022 Feb G. Moo Network | NOI- | https://www.luogu.com.cn/problem/P3141 |
| USACO 2016 Feb P. Fenced In | NOI- | https://www.luogu.com.cn/problem/P7528 |
| USACO 2021 Open G. Portals | 提高+ | https://www.luogu.com.cn/problem/P7528 |
| [COCI2016-2017#6] Sirni | NOI- | https://www.luogu.com.cn/problem/P7789 |
| CF888G Xor-MST | NOI- | https://codeforces.com/contest/888/problem/G |
2022-0508-线段树¶
TGC3.2线段树-V2022.pdf
| POJ2828-Buy Tickets | 提高 | http://poj.org/problem?id=2828 |
|---|---|---|
| Ray,Pass me the Dishes, UVa1400 | 提高 | https://www.luogu.com.cn/problem/UVA1400 |
| POJ3468 A Simple Problem with Integers | 提高 | http://poj.org/problem?id=3468 |
| USACO13Jan G, P3. Seating | 提高 | https://www.luogu.com.cn/problem/P3071 |
| 维护序列(AHOI 2009) | 提高 | https://www.luogu.com.cn/problem/P2023 |
| USACO 2013 Dec G. Optimal Milking | 提高+ | https://www.luogu.com.cn/problem/P3097 |
| [NOI Online 2020 #2 提高组] ：子序列问题 | NOI- | https://www.luogu.com.cn/problem/P6477 |
|---|---|---|
| USACO14March G, P1 The Lazy Cow | NOI- | https://www.luogu.com.cn/problem/P4876 |
| IOI 2014 – Wall | NOI- | https://www.luogu.com.cn/problem/P4560 |
| USACO14Dec G, P2 Marathon | NOI- | https://www.luogu.com.cn/problem/P3113 |
| [POI2014]KAR-Cards | NOI- | https://www.luogu.com.cn/problem/P3569 |
| COCI 2020/2021 #5 – Sjeckanje | NOI- | https://www.luogu.com.cn/problem/P7402 |
| CF1179C Serge and Dining Room | NOI- | https://codeforces.com/contest/1179/problem/C |
| Balkan OI 2018 - Election | NOI- | https://www.luogu.com.cn/problem/P4786 |
2022-05-15-状态压缩 DP-B¶
课件：C09_05-状态压缩 DP-v2022.pdf
| 1h | AtCoder DP Contest - Matching | 提高 | https://www.luogu.com.cn/problem/AT4536 |
|---|---|---|---|
| 1.5h | CF1316E Team Building | 提高+ | https://codeforces.com/contest/1316/problem/E |
| 1.5h | USACO 2014 Dec G. Guard Mark | 提高+ | https://www.luogu.com.cn/problem/P3112 |
| 1h | Headmaster's Headache, UVa10817 | 提高+ | https://www.luogu.com.cn/problem/UVA10817 |
| 1h | [USACO13NOV G]No Change | 提高+ | https://www.luogu.com.cn/problem/P3092 | |
|---|---|---|---|---|
| 1h | Hacker's Crackdown, UVa11825 | 提高+ | https://www.luogu.com.cn/problem/UVA11825 | |
| 1.5h | Sharing Chocolate, WF2010, UVa1099 | NOI- | https://www.luogu.com.cn/problem/UVA1099 | |
| 2h | COCI2016 - Burza | NOI- | 博弈 | https://www.luogu.com.cn/problem/P6499 |
| 2h | CF1043F Make It One | NOI- | GCD | https://codeforces.com/problemset/problem/1043/F |
2022-05-22-树形 DP-A¶
C09_03-树形 DP-v2022.pdf
| 0.5h | Anniversary party, POJ2342 | 提高 | http://bailian.openjudge.cn/practice/2342 |
|---|---|---|---|
| 1h | AtCoder Independent Set | 提高 | https://www.luogu.com.cn/problem/AT4537 |
| 1.5h | CF1528A Parsa's Humongous Tree | 提高 | https://codeforces.com/problemset/problem/1528/A |
| 0.5h | Balancing Act, POJ1655 | 提高 | http://bailian.openjudge.cn/practice/1655 |
| 0.5h | Cow Marathon, POJ1985 | 提高 | http://bailian.openjudge.cn/practice/1985 |
| 1.5h | Computer, HDU2196 | 提高+ | http://acm.hdu.edu.cn/showproblem.php?pid=2196 |
|---|---|---|---|
| 2h | Party at Hali-Bula | 提高+ | https://www.luogu.com.cn/problem/UVA1220 |
| 2h | [CSP-S2019] 括号树 | 提高 | https://www.luogu.com.cn/problem/P5658 |
| 1h | [ZJOI2006]三色二叉树 | 提高+ | https://www.luogu.com.cn/problem/P2585 |
| 1h | [USACO12FEB G]Nearby Cows | 提高+ | https://www.luogu.com.cn/problem/P3047 |
| 1h | USACO 2017 Dec, G. Barn Painting | 提高+ | https://www.luogu.com.cn/problem/P4084 |
2022-05-29-笛卡尔树&Treap¶
TGC3_05_BST_Set笛卡尔树_Treap.v2022.pdf
入门组：
| 1hr | multiset | Efficient Solutions, UVa11020 | 提高 | https://www.luogu.com.cn/problem/UVA11020 |
|---|---|---|---|---|
| 2hrs | set | [SDOI2015]寻宝游戏 | 提高+ | https://www.luogu.com.cn/problem/P3320 |
| 1.5hr | 笛卡尔树 | POJ1785 Binary Search Heap Construction | 提高 | http://bailian.openjudge.cn/practice/1785/ |
| 1.5hr | 笛卡尔树 | Largest Rectangle in a Histogram | 提高 | http://bailian.openjudge.cn/practice/2559/ |
| 2hr | Treap | Permutation Transformer, UVa11922 | NOI- | 非旋转 Treap | https://www.luogu.com.cn/problem/UVA11922 |
|---|---|---|---|---|---|
提高组：
| multiset | Efficient Solutions, UVa11020 | 提高 | https://www.luogu.com.cn/problem/UVA11020 |
|---|---|---|---|
| 笛卡尔树 | POJ1785 Binary Search Heap Construction | 提高 | http://bailian.openjudge.cn/practice/1785/ |
| 笛卡尔树 | Largest Rectangle in a Histogram | 提高 | http://bailian.openjudge.cn/practice/2559/ |
| Treap | Graph and Queries, Tianjin 2010 | NOI- | https://www.luogu.com.cn/problem/UVA1479 |
| Treap | Permutation Transformer, UVa11922 | NOI- | https://www.luogu.com.cn/problem/UVA11922 |
| Treap | USACO 2014 Feb G. Airplane Boarding | NOI- | https://www.luogu.com.cn/problem/P3103 |
2022-06-05-Hashing¶
课件： TG_C3_03_HASH_v2022.pdf
入门组
| 0.5h | Seek the Name, Seek the Fame, POJ Monthly--2006 | http://poj.org/problem?id=2752 | 入门 |
|---|---|---|---|
| 1h | Power Strings, Waterloo local 2002.07.01 | http://bailian.openjudge.cn/practice/2406?lang=en_US | 入门 |
| 1.5h | Stammering Aliens, SWERC 2009 | https://codeforces.com/gym/102470/problem/J | 提高 |
| 2h | [USACO17 OPEN G]Bovine Genomics | https://www.luogu.com.cn/problem/P3667 | 提高+ |
提高组
| 2h | [CEOI2017]Palindromic Partitions | https://www.luogu.com.cn/problem/P4656 | 提高+ |
|---|---|---|---|
| 2h | [USACO16 JAN G]Lights Out | https://www.luogu.com.cn/problem/P3134 | 提高+ |
| 2h | [COCI2016-2017#4] Osmosmjerka | https://www.luogu.com.cn/problem/P7538 | NOI- |
| 选做 | [COCI2020-2021#3] Sateliti | https://www.luogu.com.cn/problem/P7170 | NOI |
| 选做 | Baltic OI 2018 – Genetics | https://open.kattis.com/problems/genetics2 | NOI- |
2022-05-22-树形 DP-B¶
C09_03-树形 DP-v2022.pdf
入门组
| 1.5h | [CTSC1997]选课 | https://www.luogu.com.cn/problem/P2014 |
|---|---|---|
| 1.5h | [BOI2003]Gem 气垫车 | https://www.luogu.com.cn/problem/P4395 |
| 2h | [NOIP2003 提高组] 加分二叉树 | https://www.luogu.com.cn/problem/P1040 |
| 1.5h | Another Crisis, UVa12186 | https://www.luogu.com.cn/problem/UVA12186 |
提高组
| 2h | CF161D. Distance in Tree | https://codeforces.com/contest/161/problem/D |
|---|---|---|
| 2h | CF440D - Berland Federalization | https://codeforces.com/problemset/problem/440/D |
| 1.5h | [CQOI2009]叶子的染色 | https://www.luogu.com.cn/problem/P3155 |
| 2h | [ZJOI2008]骑士 | https://www.luogu.com.cn/problem/P2607 |
| 2h | Accumulation Degree(POJ3585) | https://vjudge.net/problem/POJ-3585 |
| 1h | UVA10859 放置街灯 Placing Lampposts | https://www.luogu.com.cn/problem/UVA10859 |
2022-06-12-树形 DP-B¶
C09_03-树形 DP-v2022.pdf
入门组
| 1.5h | [CTSC1997]选课 | 提高 | https://www.luogu.com.cn/problem/P2014 |
|---|---|---|---|
| 1.5h | [BOI2003]Gem 气垫车 | 提高 | https://www.luogu.com.cn/problem/P4395 |
| 2h | [NOIP2003 提高组] 加分二叉树 | 提高 | https://www.luogu.com.cn/problem/P1040 |
| 1.5h | Another Crisis, UVa12186 | 提高+ | https://www.luogu.com.cn/problem/UVA12186 |
提高组
| 2h | CF161D. Distance in Tree | https://codeforces.com/contest/161/problem/D |
|---|---|---|
| 2h | CF440D - Berland Federalization | https://codeforces.com/problemset/problem/440/D |
| 1.5h | [CQOI2009]叶子的染色 | https://www.luogu.com.cn/problem/P3155 |
| 2h | [ZJOI2008]骑士 | https://www.luogu.com.cn/problem/P2607 |
| 2h | Accumulation Degree(POJ3585) | https://vjudge.net/problem/POJ-3585 |
| 1h | UVA10859 放置街灯 Placing Lampposts | https://www.luogu.com.cn/problem/UVA10859 |
2022-06-19-Trie&KMP¶
课件：TG_C3_03_Trie_KMP-v2022.pdf
| HDU4825 Xor Sum(01 Trie) | 提高 | https://acm.hdu.edu.cn/showproblem.php?pid=4825 | |
|---|---|---|---|
| Remember the Word, UVa1401 | 提高+ | https://www.luogu.com.cn/problem/UVA1401 | |
| [TJOI2010]阅读理解 | 提高+ | https://www.luogu.com.cn/problem/P3879 | |
| [USACO08DEC G]Secret Message | 提高+ | https://www.luogu.com.cn/problem/P2922 | |
| [BOI2009]Radio Transmission 无线传输 | 普及 | https://www.luogu.com.cn/problem/P4391 | |
| Period, SEERC 2004, POJ1961 | 普及 | http://bailian.openjudge.cn/practice/1961?lang=en_US |
2022-06-19-Trie&KMP¶
课件：TG_C3_03_Trie_KMP-v2022.pdf
| HDU4825 Xor Sum(01 Trie) | 提高 | https://acm.hdu.edu.cn/showproblem.php?pid=4825 | |
|---|---|---|---|
| Remember the Word, UVa1401 | 提高+ | https://www.luogu.com.cn/problem/UVA1401 | |
| [TJOI2010]阅读理解 | 提高+ | https://www.luogu.com.cn/problem/P3879 | |
| [USACO08DEC G]Secret Message | 提高+ | https://www.luogu.com.cn/problem/P2922 | |
| [BOI2009]Radio Transmission 无线传输 | 普及 | https://www.luogu.com.cn/problem/P4391 | |
| Period, SEERC 2004, POJ1961 | 普及 | http://bailian.openjudge.cn/practice/1961?lang=en_US |