tricks 笔记

gzw2005 · 2022-03-14 11:41:13 · 个人记录

• 感觉编排有点乱，过几天收拾一下。（pigeon）

• 请务必在 AC 后将题目加入此处。

trick 一般在思考的第一步时出现。也就是说如果没有发现这个 trick 就做不出来力

如果想到了，后面的思考就顺理成章了

注意不能局限于对 trick 的搜集，保持思维活跃是很重要的

持续更新。

思维

• - AT2292 [AGC009C] Division into Two - P7468 [NOI Online 2021 提高组] 愤怒的小 N(缩小题目范围)(数位dp)(+拉插)
• - AT2266 [AGC008D] K-th K（构造） - P4229 某位歌姬的故事 / NH20221006D piano(等价转化+DP) - NH20221024B sequence(+堆) - P9755 [CSP-S 2023] 种树(+二分)
• 去除无效操作：AT2005 [AGC003E] Sequential operations on Sequence(+轻量势能分析)
• - AT2703 [AGC019D] Shift and Flip - AT2171 [AGC007D] Shik and Game - AT4520 [AGC032E] Modulo Pairing(+二分) - P7984 [USACO21DEC] Tickets P / NH20221025D 旅游(+最短路+线段树优化建图) - NH20221024D 雨即实刑(+贪心+DP)(+拆分贡献)
• - AT2688 [ARC080C] Young Maids - P7054 [NWRRC2015]Graph - AT5162 [AGC037E] Reversing and Concatenating(让最小字符前缀最大) - AT3974 [AGC026E] Synchronized Subsequence(划分成若干独立子问题) - P5022 [NOIP2018 提高组] 旅行 / P5049 [NOIP2018 提高组] 旅行 加强版(基环树+贪心) - NH20221014B 字典序(+前缀相同元素形成区间)(+区间DP模拟) - ZRNOIPSIM#14D 香蕉公司(只考虑最靠前的元素)(+排列转置换环)(+势能分析)(+平衡树/线段树)
• - AT2149 [ARC063D] Snuke's Coloring 2 - CF1188C Array Beauty(+差分) - P3641 [APIO2016]最大差分(交互) - ZRNOIPSIM#3D 等差数列(+带权中位数)(+对顶堆) - ZRNOIPSIM#20A 薰衣草(+DP)
• - AT2164 [AGC006C] Rabbit Exercise - CF587E Duff as a Queen(+线性基+线段树) - CF573E Bear and Bowling(观察到毒瘤性质)(+平衡树优化dp) - P4365 [九省联考 2018] 秘密袭击 coat(+交换维度整体dp+生成函数+线段树合并+慢速插值) - CF1700C Helping the Nature - P7962 [NOIP2021] 方差 - AT5147 [AGC036D] Negative Cycle(+差分约束+dp) - AT2689 [ARC080D] Prime Flip(+差分)(+欧拉路径与奇度点关系)(+二分图匹配)
• - CF377E Cookie Clicker(+dp+决策单调) - CF372C Watching Fireworks is Fun(+dp+单调栈) - P6105 [Ynoi2010] y-fast trie(+分讨+set) - CF1285F Classical?(+栈+轻量莫反) - P6072 『MdOI R1』Path(直径) - T215858 B. M-IV-Y【省选计划 · 模拟赛 #1】(+转偏序问题)(+CDQ分治+BIT) - ZRNOIPSIMEx#1A 串(分段处理)(+SA/hash+二分)(+扫描线+set/线段树)
• - ZRNOIPSIM#4B 简单题(区间DP)(+斜率优化 / +凸包+扫描线)
• - AT4437 [AGC028C] Min Cost Cycle(算元素的贡献) - AT4438 [AGC028D] Chords(算连通块的贡献)(+只考虑内部信息)(+区间dp) - AT4513 [AGC030D] Inversion Sum / CF258D Little Elephant and Broken Sorting(期望的线性性+概率dp) - AT3956 [AGC023E] Inversions(+线段树/树状数组) - P6276 [USACO20OPEN]Exercise P(+求补集) - P5666 [CSP-S2019] 树的重心(+转偏序问题)(+dfs序+树上倍增+树状数组) - ZRNOIPSIM#11D Tree(+状压DP)(+中量推式)
• - AT4167 [ARC100B] Equal Cut / NH20221002B 组队比赛 - CF660F Bear and Bowling 4(+决策单调) - CF627E Orchestra(+链表+时光倒流) - CF526F Pudding Monsters(+线段树维护等差数列个数) - CF364E Empty Rectangles(+二维分块) - CF220B Little Elephant and Array(+树状数组) - CF997E Good Subsegments(+线段树+历史版本贡献和) - CF538H Summer Dichotomy - CF1606F Tree Queries(对删除时间扫描) - P1712 [NOI2016] 区间(交换维度)(+线段树) - CF915G Coprime Arrays(+莫反) - AT4927 [AGC033D] Complexity(dp优化) - CF704E Iron Man(+树剖+set) - NH20221011C 极差(随机化算法)(找到若干定点)(+扫描线+ST) - ZRNOIPSIM#20D 郁金香(+找到最优策略)
• - CF715E Complete the Permutations(排列转简单环)(+dp) - AT4694 [AGC031D] A Sequence of Permutations(置换的运算)(找规律)(+轻量矩乘) - AT5203 [AGC038F] Two Permutations(排列转简单环)(考虑合法方案条件)(+最小割) - CF1656G Cycle Palindrome / NH20221005D permutation(构造)(置换环的拼接) - ZRNOIPSIM#14D 香蕉公司(环的拼接与分拆)(+字典序从前到后考虑)(+势能分析)(+平衡树/线段树)
• 加法与乘法的转化：
  • CF521D Shop(加法变乘法+堆)
  • P7077 [CSP-S2020] 函数调用(+拓扑排序)
• - CF505E Mr. Kitayuta vs. Bamboos(+二分答案+堆) - CF1416D Graph and Queries(+转为树论+树状数组) - P5163 WD与地图(+整体二分+线段树分治+可撤销并查集) - AT4144 [ARC098D] Donation(Kruskal重构树)(+树上dp) - CF441E Valera and Number(+数位dp) - AT4363 [ARC102D] Revenge of BBuBBBlesort!(+找充要条件) - ZRNOIPSIM#2C Hotel(+线段树+set)(+势能分析) - P7963 [NOIP2021] 棋局(+线段树合并+并查集)
• 先考虑最终情况：
  • AT3955 [AGC023D] Go Home(考虑无论如何的最终情况)
  • AT5141 [AGC035D] Add and Remove(将系数放入状态转移)(区间dp)
  • P7315 [COCI2018-2019#3] Sajam / NH20221007C bit(+bitset优化)
• 设未知数：CF538G Berserk Robot(构造)(+快速高消)
• 构造能算局部最优的黑箱：
  • CF1428E Carrots for Rabbits(对长度分割作黑箱)(+贪心+堆)
  • P2048 [NOI2010] 超级钢琴
  • P6646 [CCO2020] Shopping Plans(+堆)
• - CF1446D2 Frequency Problem - P4062 [Code+#1]Yazid 的新生舞会(分治) - P8496 [NOI2022] 众数(摩尔投票法)(+链表+线段树合并) - ABC272G Yet Another mod M(随机选元素为绝对众数概率1/2)(+枚举)
• 等价转化：CF516E Drazil and His Happy Friends (转化为同一类元素)(+轻量级数学+环上最短路)
• - CF566E Restoring Map(构造) - AT2294 [AGC009E] Eternal Average(+dp) - AT4363 [ARC102D] Revenge of BBuBBBlesort!(+时光倒流)
• 二分改倍增：
  • P2305 [NOI2014] 购票(+决策单调)
  • P6619 [省选联考 2020 A/B 卷] 冰火战士(树状数组上二分)
• 分数规划：P3705 [SDOI2017]新生舞会(+费用流)
• 分成若干独立子问题：
  • P3226 [HNOI2012]集合选数(+轻量插头dp)
  • CF1237F Balanced Domino Placements(+组合数学)
• 猫树分治(链上树分治)：
  • P6240 好吃的题目(+背包)
• - CF848C Goodbye Souvenir(cdq分治+树状数组) - P8253 [NOI Online 2022 提高组] 如何正确地排序(cdq分治+树状数组) - CF575I Robots protection(树状数组) - P5445 [APIO2019] 路灯(cdq分治+树状数组) - AT4353 [ARC101D] Robots and Exits(转成网格行走问题+平移折线)(dp+树状数组) - P3688 [ZJOI2017] 树状数组(树套树)(+微量矩乘) - P5666 [CSP-S2019] 树的重心(dfs序+树状数组)(+拆分贡献+树上倍增) - P7470 [NOI Online 2021 提高组] 岛屿探险(cdq分治)(+01trie解异或不等式) - ZRNOIPSIM#1C 旅行(+按余数分组)(+BIT) - T215858 B. M-IV-Y【省选计划 · 模拟赛 #1】(CDQ分治+BIT)(+去除无用元素)
• - CF1188B Count Pairs - P4437 [HNOI/AHOI2018]排列 - CF639E Bear and Paradox(+二分)
• - CF1017G The Tree(将元素视作$\pm 1$)(树剖+线段树) - AT4379 [AGC027E] ABBreviate(给元素视作$1/2$)(+dp) - ABC107D] Median of Medians(中位数记 $\pm 1$)(+二分)
• 边权与点权的转化 / 将边(点)的信息或贡献放到点(边)上：
  • P4643 [国家集训队]阿狸和桃子的游戏(+排序)
  • CF434E Furukawa Nagisa's Tree(+点分+分离变量)
  • NH20221007 tree(+点分治)
• 进位次数是均摊线性的：
  • AT4502 [AGC029C] Lexicographic constraints(+二分答案)
  • P3822 [NOI2017] 整数(压位高精)(+set)
• - P5653 基础最优化练习题(贪心) - P2501 [HAOI2006]数字序列(用于证明充分性)(+dp) - ZRNOIPSIM#1A 匹配(排序) - ZRNOIPSIM#6B 最小最大(+找到答案上界)(+堆)
• 操作可逆：CF627F Island Puzzle(+基环树分析)

不好分类：

• AT5799 [AGC043B] 123 Triangle(吞并思想)
• CF126D Fibonacci Sums(斐波那契唯一分解)

计算方案数

经常会结合组合数学 / DP。

• - AT3878 [ARC089D] ColoringBalls - AT2070 [ARC061D] Card Game for Three - AT2000 [AGC002F] Leftmost Ball(存放式dp) - CF506E Mr. Kitayuta's Gift(+dp套自动机+矩阵乘法)(+压缩自动机状态) - P3647 [APIO2014] 连珠线(+换根dp) - AT5142 [AGC035E] Develop(转化为图+dp) - P3899 [湖南集训]更为厉害 - P6811 「MCOI-02」Build Battle 建筑大师(+前缀和优化+考虑组合意义) - AT3962 [AGC024E] Sequence Growing Hard(+笛卡尔树上dp) - P3750 [六省联考 2017] 分手是祝愿(方案是唯一的)(概率dp+链上高斯消元) - P7515 [省选联考 2021 A 卷] 矩阵游戏(先构造特解再调整)(+差分约束) - AT4379 [AGC027E] ABBreviate(给元素视作数字)(构造最简便的方案)(+dp) - AT5203 [AGC038F] Two Permutations(排列转简单环)(+网络流) - AT3871 [AGC021E] Ball Eat Chameleons(找等价转化)(+转网格行走问题)(类似Catalan的推导) - AT3872 [AGC021F] Trinity(+中量推导+dp)(+导出卷积) - AT5143 [AGC035F] Two Histograms(考虑不合法的充要条件)(+二项式反演) - ZRNOIPSIM#8C 树(+Caylay定理)
• 转化为图上无向边定向问题：AT3537 [ARC083D] Collecting Balls
• 将题目限制化为转移条件：AT2567 [ARC074C] RGB Sequence
• 记录外部信息：CF1107E Vasya and Binary String(区间DP)
• 只考虑内部信息：AT4438 [AGC028D] Chords(+拆分贡献)(+区间dp)
• - CF1111E Tree(+轻量组合意义)(+树状数组) - CF559E Gerald and Path(+钦定法) - AT3860 [AGC020F] Arcs on a Circle(对小数部分离散化)(+状压dp) - P3953 [NOIP2017 提高组] 逛公园(使用拓扑序取消后效性)(DAG上dp)(+最短路径图) - ARC148E ≥ K - T225483 C. 定向【省选计划 · 模拟赛 #2】(将图分层逐步转移)(+子集容斥)(+半在线子集卷积)
• - AT2062 [AGC005D] ~K Perm Counting - CF997C Sky Full of Stars(轻量数学题) - CF840C On the Bench - AT4352 [ARC101C] Ribbons on Tree / NH20221014D 树(+树上背包) - P6478 [NOI Online #2 提高组] 游戏(二项式反演)(+树上背包) - AT3981 [ARC093D] Dark Horse(子集反演)(+状压dp) - AT4119 [ARC096C] Everything on It(+dp) - AT5149 [AGC036F] Square Constraints(合理的顺序转移)(+dp) - AT5143 [AGC035F] Two Histograms(二项式反演)(考虑不合法的充要条件) - NH20220926T4 排列(二项式反演+dp) - CF1605F PalindORme(合法序列和非法序列建立映射)(+dp+二项式反演) - T225483 C. 定向【省选计划 · 模拟赛 #2】(子集容斥)(+将图分层逐步转移)(+半在线子集卷积) - **V - E 容斥**： - P5291 [十二省联考 2019] 希望(+DP) - NH20221007D tree(+点分治)
• - AT1999 [AGC002E] Candy Piles(+博弈论) - AT2705 [AGC019F] Yes or No(考虑组合意义) - AT1983 [AGC001E] BBQ Hard(考虑组合意义) - CF536D Tavas in Kansas(+博弈论+最短路) - AT4353 [ARC101D] Robots and Exits(平移折线)(转成偏序问题)(dp+树状数组) - AT3871 [AGC021E] Ball Eat Chameleons(类似Catalan的翻转折线)(+找等价转化) - T231037 C. 数学作业【省选计划 · 模拟赛 #11】(考虑组合意义)(+复杂推导)
• - CF351E Jeff and Permutation(+笛卡尔树式分治) - AT4515 [AGC030F] Permutation and Minimum(从大到小考虑)(+dp) - P6163 [Cnoi2020]领域极限 / [ARC147C](https://atcoder.jp/contests/arc147/tasks/arc147_c) Min Diff Sum - AT5149 [AGC036F] Square Constraints(右端点单增地考虑)(+容斥+dp) - ARC148E ≥ K
• - **笛卡尔树上 DP**： - CF1580B Mathematics Curriculum - CF1580D Subsequence - AT3962 [AGC024E] Sequence Growing Hard(考虑合法方案的满足条件) - **水淹笛卡尔树计数：** - [ARC117E](https://atcoder.jp/contests/arc117/tasks/arc117_e) Zero-Sum Ranges 2(+dp) - CF704B Ant Man - CF1515E Phoenix and Computers
• 本质不同的元素分别记录：CF979E Kuro and Topological Parity

DP 优化 / 特殊 DP

• - P1973 [NOI2011] NOI 嘉年华 - CF708E Student's Camp - CF559E Gerald and Path(+钦定法) - P6669 [清华集训2016] 组合数问题(+Lucas定理+数位dp)(高位往低位考虑) - P6811 「MCOI-02」Build Battle 建筑大师(+前缀和优化+考虑组合意义) - P3830 [SHOI2012]随机树(期望/概率dp) - NH20220925T2 掷骰子(优化二元卷积) - AT5619 [AGC039E] Pairing Points(精细化考虑独立变量)(区间dp)
• - CF868F Yet Another Minimization Problem - CF321E Ciel and Gondolas - P1912 [NOI2009] 诗人小G - P2305 [NOI2014] 购票(可撤销二分单调栈)(+二分改倍增) - P4655 [CEOI2017] Building Bridges(+cdq分治/李超线段树) - P5468 [NOI2019] 回家路线 - P5665 [CSP-S2019] 划分(结合题目性质) - AT4927 [AGC033D] Complexity(+扫描线) - CF1179D Fedor Runs for President(维护凸包)(树上dp+单调栈) - ZRNOIPSIM#13B 最大子矩阵(可撤销二分单调栈)
• - P4597 序列 sequence / CF13C Sequence / CF713C Sonya and Problem Wihtout a Legend / P2893 [USACO08FEB] Making the Grade G(分段一次函数斜率递增)(维护凸包)(+堆) - NH20221016D 序列(分治+凸包合并)(闵可夫斯基和) - ZRNOIPSIM#4B 简单题(区间DP)(+斜率优化 / +凸包+扫描线)(+保留不合法但不优方案)
• - CF1557D Ezzat and Grid(+线段树) - CF568E Longest Increasing Subsequence(+树状数组) - CF573E Bear and Bowling(观察到毒瘤性质)(+差分+平衡树) - P4365 [九省联考 2018] 秘密袭击 coat(线段树合并)(+生成函数+慢速插值) - CF671D Roads in Yusland(线段树合并 / 平衡树启发式合并) - P4655 [CEOI2017] Building Bridges(+李超线段树/cdq分治) - P5290 [十二省联考 2019] 春节十二响(贪心)(平衡树启发式合并)【不是dp但是我想放在这里】 - P5298 [PKUWC2018]Minimax(线段树合并) - P6847 [CEOI2019] Magic Tree / NH20221026D magic tree(树上DP+差分+线段树合并模拟DP过程) - ZRNOIPSIM#7C (树上DP+差分+凸函数)(+平衡树启发式合并)(+找到最优策略)
• 李超线段树：CF932F Escape Through Leaf(李超线段树合并+树形DP)
• DDP：
  • CF811E Vladik and Entertaining Flags(静态)
  • CF750E New Year and Old Subsequence(+轻量自动机)
• 考虑等价类减小状态数：
  • AT3621 [ARC084B] Small Multiple(mod意义相等视作等价类)(+有后效性最优性dp转最短路)
  • AT3951 [AGC022F] Checkers(各数字贡献系数等价)
• - CF809D Hitchhiking in the Baltic States(+平衡树) - P3643 [APIO2016]划艇 - P8290 [省选联考 2022] 填树(换根dp)(+插值)
• - P4587 [FJOI2016]神秘数(物品能表示的区间)(倍增+线段树)【不是dp】 - AT4120 [ARC096D] Sweet Alchemy(物品间的替换)(去除较劣方案)(dp+枚举+贪心) - NH20220912D 的最⼤的伤害(物品间的替换)(等价转化)(dp+枚举)
• DP 套自动机：
  • CF808G Anthem of Berland(+kmp自动机)
  • CF585F Digits of Number Pi(数位DP)(+AC自动机)
  • AT3963 [AGC024F] Simple Subsequence Problem(状压dp)(+轻量子序列自动机)
• 分治背包：
  • CF601E A Museum Robbery(+线段树分治)
  • CF1442D Sum
  • P6240 好吃的题目(+猫树分治)
• - **不同转移对应不同矩阵** - CF576D Flights for Regular Customers(图上行走问题) - CF575A Fibonotci(线性递推) - AT2371 [AGC013E] Placing Squares(增量法,不要往整块想)(值域很大交换维度) - **状态信息能记就记**：CF385E Bear in the Field(模拟) - P3746 [六省联考 2017] 组合数问题(+考虑组合意义) - P4365 [九省联考 2018] 秘密袭击 coat(dp转移化为矩乘满足交换律)(+生成函数+线段树合并优化矩乘+慢速插值) - P4007 小 Y 和恐怖的奴隶主(概率dp) - P5772 [JSOI2016]位运算(数位dp)(高位往低位考虑) - P6630 [ZJOI2020] 传统艺能 - P6772 [NOI2020] 美食家(预处理转移矩阵幂次) - ARC151D Binary Representations and Queries(操作满足交换律) - P8820 [CSP-S 2022] 数据传输(+倍增)
• - P4707 重返现世(+kthminmax) - P4827 [国家集训队] Crash 的文明世界(+Stirling降幂) - AT4352 [ARC101C] Ribbons on Tree / NH20221014D 树(-1次幂随转移拆开)(树上背包) - P6944 [ICPC2018 WF]Gem Island / NH20221003D 宝石 - AT5141 [AGC035D] Add and Remove(先考虑最终情况)(区间dp)
• 整体 DP(转移数很少且可以用 DS 模拟)：
  • CF671D Roads in Yusland(线段树合并 / 平衡树启发式合并)
  • P4365 [九省联考 2018] 秘密袭击 coat(线段树合并优化矩乘)(+生成函数+慢速插值)
• - AT4927 [AGC033D] Complexity(+决策单调+扫描线) - NH20221014D 摩斯电码(+二分)
• - AT3621 [ARC084B] Small Multiple(+mod意义相等视作等价类) - CF375C Circling Round Treasures(状压dp+网格走路+全1最短路bfs)(+注意看题目备注)(+光线投射判多边形内)
• 仙人掌上DP：
  • ZRNOIPSIM#13D 波波牛的星系(考虑树上DP与环上DP)
  • ZRNOIPSIM#18C Cactus(期望DP)(+线性高消)
• 找到状态数上界：
  • P3724 [AHOI2017/HNOI2017]大佬 / NH20221015C 打怪(+枚举)
  • ZRNOIPSIM#14C 猪尾巴(状压DP)(+hash)
• 设置过渡状态交叉转移：
  • ZRNOIPSIM#10B 哈夫曼树(区间DP)(+倍增)
  • ZRNOIPSIM#16C 工厂(子集DP)
  • P8859 冒泡排序(+笛卡尔树式DP)

构造

• 最短路与网络流的建图相通：AT3877 [ARC089C] GraphXY
• 倍增地构造：
  • AT4432 [ARC103B] Robot Arms
  • AT4361 [ARC102B] All Your Paths are Different Lengths
• 数论的构造（很考瞪眼法）：
  • AT4378 [AGC027D] Modulo Matrix
  • AT3947 [AGC022B] GCD Sequence
• 奇怪的构造：
  • AT2043 [AGC004C] AND Grid
  • CF1530E Minimax(字符串)(找到答案上界+分讨)
  • CF1583F Defender of Childhood Dreams
  • AT4512 [AGC030C] Coloring Torus(对角线)
  • P7115 [NOIP2020] 移球游戏(类似快速排序的分治)
• 匹配思想：
  • ZRNOIPSIM#7D (复制链表示匹配信息)(+可持久化线段树)
  • ZRNOIPSIM#17D 飞毯(自动机的构造)(+哈密顿回路+环的拼接)

图论

路径 / 最短路

• P7520 [省选联考 2021 A 卷] 支配(朴素支配树+翻译条件)
• P7516 [省选联考 2021 A/B 卷] 图函数(借用Floyd思想)
• 同余最短路：
  • CF241E Flights
  • P2371 [国家集训队]墨墨的等式(优化背包)
• P3350 [ZJOI2016]旅行者(分治+最短路)
• P5471 [NOI2019] 弹跳(kdtree优化建图)

强连通分量 / 环 / 度数

• (非)必经边的分析：AT3945 [ARC092D] Two Faced Edges
• - CF835F Roads in the Kingdom - P5022 [NOIP2018 提高组] 旅行 / P5049 [NOIP2018 提高组] 旅行 加强版(字典序最小 从前往后考虑)(+贪心) - CF627F Island Puzzle(+操作可逆)
• 全为奇数度点 \Leftrightarrow 全为偶数点连通块：CF603E Pastoral Oddities
• 两点不相交路径形成环：
  • CF521E Cycling City
  • CF639F Bear and Chemistry(+虚树+树上差分)
• 环上点度数必 \ge 2：CF512D Fox And Travelling
• 奇环相交：CF19E Fairy
• 环与匹配的关系：P1407 [国家集训队]稳定婚姻
• 同余系与环的关系：P5330 [SNOI2019]数论
• 割点的分析：P3225 [HNOI2012]矿场搭建
• 竞赛图的分析：T232309 A. 基础图论练习题 【省选计划 · 模拟赛 #13】(转成序列上问题)(+线段树)

二分图 / 奇环 / 染色

• (转化为)在二分图上构造：
  • AT3967 [AGC025D] Choosing Points
  • CF538H Summer Dichotomy
• 染色：AT2167 [AGC006F] Blackout
• - AT4505 [AGC029F] Construction of a tree(+二分图匹配)(构造) - AT5161 [AGC037D] Sorting a Grid(k-正则二分图满足Hall定理)(+二分图匹配)

欧拉回路 / 欧拉路径 / 偶度点

• - CF547D Mike and Fish - CF527E Data Center Drama - CF429E Points and Segments - AT3968 [AGC025E] Walking on a Tree - P6628 [省选联考 2020 B 卷] 丁香之路(+简易Kruskal)
• CF1698F Equal Reversal
• AT4518 [AGC032C] Three Circuits(欧拉回路的拆分)(分讨)
• AT2689 [ARC080D] Prime Flip(欧拉路径条数与奇度点的关系)(+差分+二分图匹配)

传递关系

• 并查集：
  • P7323 [WC2021] 括号路径(关系双向且可传递)(+线段树合并)
  • 种类并查集：
    • P2024 [NOI2001] 食物链
    • CF1444C Team-Building(+可撤销并查集)
  • 链上并查集：
    • CF319E Ping-Pong(+set)
    • NH20220930 赚钱(贪心)
• 2-SAT：P3825 [NOI2017] 游戏(+枚举)
• 拓扑排序：
  • AT4380 [AGC027F] Grafting(+枚举)
  • CF698D Limak and Shooting Points(枚举拓扑序列)(+搜索)
  • P3953 [NOIP2017 提高组] 逛公园(判环)(+最短路径图)(+DAG上dp)
• NH20221007B qwq(调整法)(+队列)

DS

• 可持久化：
  • 修改很少的版本：
    • CF757G Can Bash Save the Day?(交换元素)
    • CF464E The Classic Problem(松弛操作)(+Dijkstra+线段树二分)
  • 维护复制粘贴：
    • CF803G Periodic RMQ Problem(静态)
    • T215859 C. 博福斯 TRV【省选计划 · 模拟赛 #1】(+底层分块+定期重构)
• - CF765F Souvenirs(+偏序) - P3747 [六省联考 2017] 相逢是问候(+欧拉定理) - P7476 「C.E.L.U-02」苦涩(线段树+堆) - **操作使值域减半 / 操作数或段数不太多**： - CF702F T-Shirts(+平衡树) - CF438D The Child and Sequence(找有效操作)(+线段树) - CF920F SUM and REPLACE - P3987 我永远喜欢珂朵莉~(树状数组+链表) - P7603 [THUPC2021] 鬼街(堆) - NH20220907 旅人1970(段数上界为根号)(+线段树) - CF1523G Try Booking(段数上界为调和级数)(+树套树) - ZRNOIPSIM#2C Hotel(+线段树+set)(+时光倒流) - ZRNOIPSIM#14D 香蕉公司(+排列、置换与简单环的转化+字典序从前到后考虑)(+平衡树/线段树) - **势能增加只决定于特定的操作数 / 操作使连续段增加常数个**： - CF453E Little Pony and Lord Tirek(+主席树+set维护连续段) - CF444C DZY Loves Colors(线段树) - P3823 [NOI2017] 蚯蚓排队(+hash+链表) - **吉司机线段树：** CF793F Julia the snail
• 线段树分治：
  • CF1140F Extending Set of Points(+数点转有向边)
  • 半在线线段树分治：
    • CF576E Painting Edges(到达叶子才处理)
    • P3309 [SDOI2014]向量集(线段树节点完整才处理)
• 楼房重建线段树：
  • P4198 楼房重建
  • CF1340F Nastya and CBS
• 对操作的操作：CF571D Campus(对操作建树+主席树)
• 历史版本贡献和：CF997E Good Subsegments(+扫描线)
• 转为树上问题：
  • CF1416D Graph and Queries(对集合合并建树)(+树状数组)
  • CF571D Campus(对操作建树)(+主席树)
• logn 分块：
  • CF1515I Phoenix and Diamonds(线段树)
  • P7447 [Ynoi2007] rgxsxrs(线段树)
• - CF1614E Divan and a Cottage - P1712 [NOI2016] 区间(扫描线+线段树) - P3348 [ZJOI2016]大森林(扫描线+LCT) - P4365 [九省联考 2018] 秘密袭击 coat(整体dp)(dp+生成函数+线段树合并优化矩乘+慢速插值) - ZRNOIPSIM#C 栀子花(+SegmentTreeBeats)
• 整体二分：
  • P1527 [国家集训队]矩阵乘法(+二维树状数组)
  • P5163 WD与地图 / NH20220928D 连通(预处理加边时间)(+Tarjan重标记 / 可撤销并查集+线段树合并)

根号

• 序列分块：
  • 只考虑块内信息：CF13E Holes
  • 分块凸包：CF436F Banners
  • 分块NTT：T224318 C. T95/FV4201【省选计划 · 模拟赛 #1】 / P8527 [Ynoi2003] 樋口円香
• - CF587F Duff is Mad(+AC自动机+序列分块) - P5386 [Cnoi2019]数字游戏(回滚莫队+序列分块) - P6578 [Ynoi2019] 魔法少女网站(操作分块+序列分块)
• 根号分治：
  • CF1039D You Are Given a Tree(数论根号)(+二分+自底而上)
  • P5307 [COCI2018-2019#6] Mobitel(数论根号)(+dp)
  • P3591 [POI2015] ODW
  • P5901 [IOI2009] regions
• 对操作分块：CF1588F Jumping Through the Array
• 无向图三元环计数：CF985G Team Players(补集)
• 折半处理：
  • CF1006F Xor-Paths(折半搜索)
  • CF1569E Playoff Restoration(折半搜索)
  • P6622 [省选联考 2020 A/B 卷] 信号传递(折半处理)

树论

• - **自底而顶地考虑**： - AT2304 [AGC010C] Cleaning - CF1039D You Are Given a Tree(+数论根号+二分) - P7246 手势密码 - AT4995 [AGC034E] Complete Compress(+枚举) - P3748 [六省联考 2017] 摧毁“树状图”(路径拼接+分讨)(树上dp) - **自顶而底地考虑**：P8293 [省选联考 2022] 序列变换(贪心)
• 图转生成树：P2542 [AHOI2005] 航线规划(+树剖+线段树)
• 最小生成树：
  • 点分治划分成若干子图再合并：
    • AT3611 Tree MST
    • P6199 [EER1]河童重工(+虚树+树形dp)
  • (特殊方式的 Kruskal)快速找到下一条边：CF888G Xor-MST
  • - P1967 [NOIP2013 提高组] 货车运输 - P4768 [NOI2018] 归程(+可持久化并查集) - AT4144 [ARC098D] Donation(时光倒流)(+树上dp)
  • - P2387 [NOI2014] 魔法森林(+LCT) - AT3980 [ARC093C] Bichrome Spanning Tree(替换边的分析)
  • 次小生成树：P4180 [BJWC2010] 严格次小生成树
  • P3665 [USACO17OPEN]Switch Grass P(最优决策为最小生成树)(兄弟节点一起维护)(+set)
• 树上距离分析：AT4434 [ARC103D] Distance Sums
• - CF741D tree&paths(+dp) - CF1499F Diameter Cuts(+dp) - P3565 [POI2014]HOT-Hotels / P5904 [POI2014]HOT-Hotels 加强版(+dp) - T226216 C. 缘分【省选计划 · 模拟赛 #3】(+轻量卷积)
• - CF600E Lomsat gelral - CF570D Tree Requests - CF375D Tree and Queries - CF1009F Dominant Indices - P6072 『MdOI R1』Path(+dp) - P5439 【XR-2】永恒(用dsu降维成在线问题)(+01Trie) - ZRNOIPSIM#16D 火柴(+容斥)
• - CF526G Spiders Evil Plan(+重链剖分) - CF1442E Black, White and Grey Tree(树形dp算直径) - CF835F Roads in the Kingdom / P1399 [NOI2013] 快餐店(基环树的直径)(树形dp算直径) - CF516D Drazil and Morning Exercise(+栈+二分) - CF566C Logistical Questions(最长距离以重心往外单增)(+求导) - P4383 [八省联考 2018] 林克卡特树(dp算直径)(+wqs二分) - AT4133 [ARC097D] Monochrome Cat(路径拼接转路径补集)(树形dp算带权直径) - AT4114 [ARC095D] Permutation Tree(构造)(考虑合法方案满足条件) - ZRNOIPSIM#5C 树(贪心)(+换根DP)(+扫描线) - T215857 A. 卡利班【省选计划 · 模拟赛 #1】(直径合并)(+并查集+倍增)
• - CF150E Freezing with Style(+二分答案+单调队列) - P7206 [COCI2019-2020#3] Lampice(+二分答案+hash) - P3920 [WC2014]紫荆花之恋(动态点分树+定期重构)(+平衡树) - P6072 『MdOI R1』Path(去除较劣方案) - P5311 [Ynoi2011] 成都七中(树上连通块必以分治重心为根)(+扫描线) - P4565 [CTSC2018]暴力写挂 / ZRNOIPSIM#2D Tree(两棵树问题)(改写式子)(边分治+虚树上dp) - T226303 C【省选计划 · 模拟赛 #4】(点分树+BIT)(+轻量矩阵) - T228288 C. 树上背包 【省选计划 · 模拟赛 #7】(+单调队列)
• DFS树：CF938G Shortest Path Queries(利用异或性质)(+线段树分治+可撤销并查集)
• 重链剖分：CF960H Santa's Gift(+提取贡献+动态开点线段树)
• - CF1528C Trees of Tranquillity - P3248 [HNOI2016]树(大树套小树) - AT2063 [AGC005E] Sugigma: The Showdown - P4565 [CTSC2018]暴力写挂 / ZRNOIPSIM#2D Tree(改写式子)(边分治+虚树上dp) - CF997D Cycles in product(两棵树本质相互独立)(换根dp) - T233315 b(+中量推导)
• 重构树：P4899 [IOI2018] werewolf 狼人(+主席树)
• P7518 [省选联考 2021 A/B 卷] 宝石(树上倍增+二分)
• 考虑每条边出现时间：
  • P7897 [Ynoi2006] spxmcq / CF1606F Tree Queries(+堆+树状数组+并查集)
  • P5163 WD与地图 / NH20220828 连通(加边时间预处理)(+Tarjan重标记 / 可撤销并查集+线段树合并)

数学

• 线性递推：
  • 二阶线性递推：P1397 [NOI2013] 矩阵游戏(or 矩乘)
  • 同线性递推数列相加仍满足递推：CF446C DZY Loves Fibonacci Numbers(+矩阵乘法)
• - P3723 [AH2017/HNOI2017]礼物 - P3338 [ZJOI2014]力 - P3175 [HAOI2015]按位或(dp+min-max容斥+FWT) - P4221 [WC2018]州区划分(FWT) - P4491 [HAOI2018]染色(二项反演) - P4921 [MtOI2018]情侣？给我烧了！ - P5644 [PKUWC2018]猎人杀(容斥)(+分治NTT) - P6846 [CEOI2019] Amusement Park(容斥)(FWT求逆) - P8292 [省选联考 2022] 卡牌(根号分治+状压dp+FWT) - AT2022 [ARC059D] バイナリハック / Unhappy Hacking(dp+朴素多项式快速幂) - AT3872 [AGC021F] Trinity(考虑合法方案满足条件+dp) - CF582E Boolean Function(状压dp+FWT) - T221672 C 还是树【省选计划 · 模拟赛 #7】(+点分治) - T227758 C. 连击路径【省选计划 · 模拟赛 #8】(+拆分贡献) - ZRNOIPSIM#18D Melody(容斥)(+分治NTT) - ZRNOIPSIMEx#1B 树(+快速求值)(+复杂推导)
• 生成函数：
  • 导出恒等式解方程：CF438E The Child and Binary Tree
  • 结合矩阵树定理：
    • CF917D Stranger Trees(+拉插)
    • P5296 [北京省选集训2019]生成树计数(+高斯消元)
  • P3784 [SDOI2017] 遗忘的集合(exp组合意义+exp与ln互逆)
  • 构造新型生成函数：CF1698G Long Binary String(基于二进制异或运算)(求离散对数+多项式慢速取模)
  • P4463 [集训队互测 2012] calc
  • P6570 [NOI Online #3 提高组] 优秀子序列(占位多项式慢速exp)
  • P6060 [加油武汉]传染病研究(+线性筛)
• - CF917D Stranger Trees(+矩阵树定理) - P4365 [九省联考 2018] 秘密袭击 coat(慢速插值)(+交换维度+整体dp+生成函数+线段树合并) - ZRNOIPSIM#15D 狮子(伯努利数)(+类欧)
• 快速高消(依赖题目性质)：
  • CF538G Berserk Robot(构造)(+设未知数)
  • T227756 A. 无双割草小游戏【省选计划 · 模拟赛 #8】(带状高斯消元)
• 求导：
  • CF566C Logistical Questions(+重心性质)
  • P3706 [SDOI2017]硬币游戏(PGF)(+高斯消元)
  • P5401 [CTS2019] 珍珠(复杂推导)
  • CF566C Logistical Questions(最长距离以重心往外单增)
• - AT5202 [AGC038E] Gachapon(概率+min-max容斥+提取贡献) - CF961G Partitions(提取贡献+干掉Stirling) - P4091 [HEOI2016/TJOI2016]求和(干掉Stirling) - P2791 幼儿园篮球题 - P5401 [CTS2019] 珍珠 - P6108 [Ynoi2009] rprsvq(冷门恒等式)(+线段树) - P6031 CF1278F Cards 加强版 - P6620 [省选联考 2020 A 卷] 组合数问题 - ZRNOIPSIM#4C 数数题(中量推式)(+期望线性性) - T231037 C. 数学作业【省选计划 · 模拟赛 #11】(考虑组合意义)(+转网格行走问题) - ZRNOIPSIM#19C 带我上(EGF)(组合数裂项求递推式) - ZRNOIPSIMEx#1B 树(导出卷积)(+快速求值)
• - **分块凸包**：CF436F Banners - **线段树维护凸包**：P3309 [SDOI2014]向量集 - **分治凸包**：NH20221016D 序列(分治+凸包合并)(闵可夫斯基和)(+差分)
• 曼哈顿与切比雪夫间的转化：
  • CF685C Optimal Point(高维曼哈顿与切比雪夫距离转化)(+二分)
  • CF538G Berserk Robot(转化操作)(构造)(+设未知数+快速高消)

数论

• 先干掉平方数/立方数：
  • AT2004 [AGC003D] Anticube
  • CF980D Perfect Groups
  • P4448 [AHOI2018初中组]球球的排列
  • P5438 【XR-2】记忆(+轻量莫反+整除分块)
  • CF1325E Ehab's REAL Number Theory Problem(+对质因数根号分治)(+bfs求最小环)
  • T227162 A. WG你还我秃子酋长【省选计划 · 模拟赛 #5】(+map)
• gcd 是可合并的：CF359D Pair of Numbers(+RMQ+二分)
• - AT5200 [AGC038C] LCMs - CF1139D Steps to One(+期望dp) - P4619 [SDOI2018]旧试题(约数函数内积)(+无向图三元环计数) - P6624 [省选联考 2020 A 卷] 作业题(+矩阵树定理)
• - CF585E Present for Vitalik the Philatelist(+轻量级莫反) - CF1614D2 Divan and Kostomuksha (hard version)(类似的dp转移) - P6222 「P6156 简单题」加强版(加速一般Dirichlet卷积)(+莫反)
• 裴蜀定理：CF1515G Phoenix and Odometers(类线性基)
• - P2150 [NOI2015] 寿司晚宴(+状压) - P8292 [省选联考 2022] 卡牌(+FWT) - CF1325E Ehab's REAL Number Theory Problem(+干掉平方数)(+bfs求最小环)
• 质数作为维度分开考虑：CF571E Geometric Progressions(手搓方程组)(+exCRT)
• - P3773 [CTSC2017]吉夫特(+子集枚举dp) - P6669 [清华集训2016] 组合数问题(+数位dp)(高位往低位考虑) - NH20221014C 高维整点(+数位DP)(高位往低位考虑)
• 中国剩余定理：P4774 [NOI2018] 屠龙勇士

位运算

• 加法与位运算的转化：
  • AT2272 [ARC066B] Xor Sum
  • T232314 B. 序列上的树 【省选计划 · 模拟赛 #13】(+FMT)
• - AT4835 [ABC141F] Xor Sum 3 - CF242E XOR on Segment(+线段树) - P7207 [COCI2019-2020#3] Sob(构造) - P4067 [SDOI2016]储能表(数位DP) - P5354 [Ynoi2017] 由乃的 OJ(+树剖+线段树+微型矩阵乘法) - Zeros and Ones(观察题目元素)(数位dp)(+从低位到高位考虑也能比大小) - P7468 [NOI Online 2021 提高组] 愤怒的小 N(数位dp)(找到更紧的限制)(+拉插) - NH20220926T3 异或(+从高位到低位考虑)(+轻量dp) - T228277 B. 星命定轨 【省选计划 · 模拟赛 #7】(+bitset)(+根号分治) - ZRNOIPSIM#6D 脉冲星(从高位到低位贪心)
• 高维前缀和：
  • AT4168 [ARC100C] Or Plus Max
  • CF1208F Bits And Pieces
• FWT：CF662C Binary Table
• - **构造方案再添加基本元素**： - NH20220928 图异或 - P4151 [WC2011]最大XOR和路径(转DFS树上加环) - CF938G Shortest Path Queries(转DFS树上加环)(+线段树分治+可撤销并查集) - **向量组等价 $\Leftrightarrow$ 大小相同且能互作线性表示**： - CF587E Duff as a Queen(+差分+线段树) - P5607 [Ynoi2013] 无力回天 NOI2017(+差分+线段树) - T227325 时空传送器(求秩的大小)(非典型线性基)(+矩阵+高斯消元) - CF1100F Ivan and Burgers(+扫描线+贪心)
• 子集优化建图(?)：CF986C AND Graph
• - CF1515H Phoenix and Bits(trie树合并) - P6018 [Ynoi2010] Fusion tree(低位至高位建trie) - P6623 [省选联考 2020 A 卷] 树(低位至高位建trie) - P7470 [NOI Online 2021 提高组] 岛屿探险(01trie解异或不等式)(+转偏序问题)(+cdq分治)

概率和期望

• CF698C LRU（无限步数 多一步仍为原状）
• 含决策的概率/期望题：
  • CF605E Intergalaxy Trips(+最短路)
  • CF553E Kyoya and Train(+卷积优化dp)
• PGF：
  • P4548 [CTSC2006]歌唱王国(+KMP)
  • P3706 [SDOI2017]硬币游戏(+高斯消元)
  • P6125 [JSOI2009] 有趣的游戏(+AC自动机+高斯消元)
• P1850 [NOIP2016 提高组] 换教室(基础dp)
• P3600 随机数生成器(期望)(dp)
• P5516 [MtOI2019]小铃的烦恼(拆分贡献+条件概率)
• - AT4513 [AGC030D] Inversion Sum / CF258D Little Elephant and Broken Sorting(+概率dp) - CF1187F Expected Square Beauty(轻量推式) - CF1172C2 Nauuo and Pictures (hard version)(拆分成本质相同元素的期望) - NH20221011B 数列期望(只观察某些元素)(+裂项法求递推式) - ARC150D Removing Gacha(只观察某些元素) - ZRNOIPSIM#4C 数数题(+中量推式) - ZRNOIPSIMEx#4B 我想大声告诉你(本质相同元素合并考虑)(+DP)
• - P4284 [SHOI2014] 概率充电器(树上高斯消元) - P3750 [六省联考 2017] 分手是祝愿(方案唯一表示)(概率dp+链上高斯消元) - P4457 [BJOI2018]治疗之雨(概率dp+链上高斯消元) - ZRNOIPSIM#15B 对赌(+设未知数+二分答案)(概率DP) - ZRNOIPSIM#18C Cactus(期望DP)
• 所有可能总和转期望：P5280 [ZJOI2019]线段树(+线段树上dp)

网络流

• 平面图最小割转最短路：
  • P4001 [ICPC-Beijing 2006] 狼抓兔子
  • P7916 [CSP-S 2021] 交通规划
• (最小割)必经边与可行边的分析：P4126 [AHOI2009]最小割
• 模拟费用流(反悔贪心)：
  • CF802O April Fools' Problem (hard)(+线段树)
  • CF280D k-Maximum Subsequence Sum(+线段树)
  • P1484 种树(+链表)
  • P4694 [PA2013] Raper(+线段树)
• - CF739E Gosha is hunting(费用流+概率) - P4298 [CTSC2008]祭祀(Dilworth定理+构造反链方案)(可行点判断) - CF590E Birthday(Dilworth定理+构造反链方案)(+AC自动机) - CF1054F Electric Scheme(构造二分图最大独立集方案) - AT2689 [ARC080D] Prime Flip(二分图匹配)(+差分+欧拉路径与奇度点关系)
• Dilwork 定理 / 其对偶定理：
  • P4298 [CTSC2008]祭祀(Dilworth定理+构造反链方案)(可行点判断)
  • CF590E Birthday(Dilworth定理+构造反链方案)(+AC自动机)
  • T226215 B. 阅读【省选计划 · 模拟赛 #3】(+AC自动机)
• 解方程组/不等式组：
  • CF611H New Year and Forgotten Tree(求解方程组)(+枚举)
  • P3980 [NOI2008] 志愿者招募(求解不等式组)

字符串

• - CF1056E Check Transcription - P4036 [JSOI2008]火星人(+平衡树) - AT4163 [ARC099D] Eating Symbols Hard(双hash)(+map) - P3823 [NOI2017] 蚯蚓排队(手写hash表以卡常)(+链表) - CF213E Two Permutations / NH20221011D 股票图(找到答案上界)(+线段树模拟) - P8819 [CSP-S 2022] 星战(+势能分析)
• KMP：CF954I Yet Another String Matching Problem(+brute)
• SA：
  • CF1073G Yet Another LCP Problem(+二分)
  • P2178 [NOI2015] 品酒大会(对height分组)
• - CF802I Fake News (hard) - CF1063F String Journey(+dp+线段树) - P3346 [ZJOI2015]诸神眷顾的幻想乡(广义SAM) - CF666E Forensic Examination(广义SAM)(+线段树合并) - P7046 「MCOI-03」诗韵(+线段树二分)
• - CF547E Mike and Friends（AC自动机+树状数组） - CF587F Duff is Mad（AC自动机+分块+根号平衡） - CF1483F Exam
• 匹配的势能分析：
  • P1117 [NOI2016] 优秀的拆分(+SA)
• PAM：
  • ZRNOIPSIM#17C 冰块(周期与回文border的关系)

\blacktriangle 随机算法

• UOJ#245 【UER #7】天路 / NH20221011C 极差(找到若干定点)(+扫描线+ST表)
• ABC272G Yet Another mod M(错误概率对次数以指数级缩小)
• ZRNOIPSIM#12C 时空限制(估计答案的范围)

碎碎念

• 递归复杂度不能用主定理算的，一般都能用等比数列求和算。
  • T(n)=2T(n/2)+O(n\sqrt n\log n)=O(n\sqrt n\log n)
• STL 迭代器：1.前驱函数 \text{prev(it)}；2.后继函数 \text{next(it)}。
• 图的计数有时候可以考虑转化成生成树计数，再往里面加非树边。

• 请你模块化编程

• 遇到很奇怪的 DS，用 \log 型数据结构很难维护时，一定不要忘记往根号算法想。