Summary

感觉NOI之前肯定来不及把所有的题都一个个发成题解了。。 把做过的题随便溜一遍吧。。。。 这两天还会更新一大波内容

网络流：

1.和时间有关的问题：按照时间拆点，分层图

BZOJ1189 紧急疏散 SD二轮集训D3T3 第三题 BZOJ1570 Blue Mary的旅行 POJ3686 The Windy’s BZOJ1070 修车 BZOJ2879 美食节

2.添加限流点来满足题目要求

BZOJ1189 紧急疏散 BZOJ4842 Delighting for a Cat

3.基本模型

(1).集合划分模型：一个点要么选S要么选T，选且只能选一个

BZOJ2127 happiness Codeforces311E Biologist SPOJ839 OPTM

(2).路径覆盖模型：拆成二分图

BZOJ1927 星际竞速 BZOJ2150 部落战争

(3).黑白染色：黑点和白点不能同时选择

BZOJ1324 Exca王者之剑 BZOJ3275 Number BZOJ3158 千钧一发

(4).区间选择问题：把所有点连成一串

BZOJ4842 Delighting for a Cat POJ3680 Intervals

(5).最大权闭合子图

BZOJ3438 小M的作物 BZOJ1565 植物大战僵尸 BZOJ1497 最大获利

(6).离散变量的取值

BZOJ3144 切糕

4.最小割

(1).使某两个点不联通的最小代价

BZOJ2521 最小生成树

(2).平面图最小割=对偶图最短路

BZOJ1001 狼抓兔子 BZOJ2007 海拔

(3).最小割唯一性判定

BZOJ1797 最小割

5.有上下界的网络流

(1).有上下界的最大流

BZOJ2406 矩阵 BZOJ2502 清理雪道 POJ3801 Crazy Circuits

(2).有上下界的费用流：优先保证费用最小

BZOJ4108 Catering BZOJ3876 支线剧情

6.费用是流量的函数：拆边

BZOJ2597 剪刀石头布 BZOJ1070 修车 BZOJ2879 美食节

7.对棋盘进行行列拆点

BZOJ1059 矩阵游戏 BZOJ4554 游戏 SD一轮集训D4T1 棋盘 BZOJ3698 XWW的难题

8.消圈定理：费用流中出现负环一定存在更优解

BZOJ3597 方伯伯运椰子

9.混合图欧拉回路：流量平衡原理

BZOJ2095 Bridges

10.用最大流进行模拟

BZOJ1779 奶牛战争 Uva10779 Collector’s Problem

11.实数网络流

BZOJ3993 星际战争 BZOJ3130 费用流

DP：

1.树形DP

(1).树上最长链：dfs和树形DP。dfs不能用于有负边权的情况

BZOJ1912 巡逻 Codeforces592D Super M BZOJ1509 逃学的小孩

(2).每个点的状态较少：f[u][0/1/2…]

BZOJ3257 树的难题 BZOJ1063 道路设计 BZOJ1907 树的路径覆盖

(3).从子树外面自顶向下推过来

BZOJ3566 概率充电器 HDU2196 Computer

(4).树的直径的性质

Codeforces455C Civilization BZOJ2282 消防 BZOIJ3124 直径

(5).树形背包

BZOJ4033 T1 POJ1155 TELE

2.DP的顺序问题

(1).出现后效性的时候换一种顺序

Codeforces31E TV Game

(2).DP之前适当排序

Codeforces459E Pashmak and Graph

(3).不是从前往后而是数字从小到大

SD一轮集训D4T2 塔 BZOJ4321 queue2 Codeforces285E Positions in Permutations

3.记忆化搜索

BZOJ2461 符环 BZOJ1048 分割矩阵 BZOJ3895 取石子

4.带有环的DP：拆环或对端点讨论

BZOJ1737 午睡时间 BZOJ1040 骑士 BZOJ3242 快餐店

5.状压DP：集合内元素非常少

BZOJ1072 排列perm BZOJ2669 局部极小值 BZOJ4197 寿司晚宴 Codeforces71E Nuclear Fusion

6.数位DP：开多维状态来记录，注意前导零的处理

BZOJ3530 数数 BZOJ1799 同类分布 BZOJ3134 numbers

7.优化

(1).bitset

Codeforces781D Axel and Marston in Bitland BZOJ3687 简单题

(2).用最长上升子序列来代替最长公共子序列

BZOJ1264 基因匹配

(3).斜率优化

BZOJ3675 序列分割 BZOJ1492 货币兑换Cash BZOj2726 任务安排

(4).矩阵乘法

Codeforces621E Wet Shark and Blocks POJ3744 Scout YYF （分段） BZOJ1898 沼泽鳄鱼 BZOJ4417 超级跳马

(5).决策单调性

POJ1160 Post Office HDU2829 Lawrence HDU3480 Division HDU3516 Tree Construction

(6).适当更改状态表示

BZOJNOIP十连测第二场B Market

(7).数据结构

BZOJ1835 基站选址

8.分组更新

BZOJ2423 最长公共子序列 BZOJ4197 寿司晚宴 BZOJNOIP十连测第八场B 降雷皇

9.斯坦纳树：分成子集的合并和移动两种方法转移

BZOJ4774 修路 BZOJ2595 游览计划 BZOJ3205 机器人 BZOJ4006 管道连接

贪心：

1.判断最优解中的必需元素

BZOJ2811 Guard BZOJ3168 钙铁锌硒维生素 BZOJ3624 免费道路 BZOJ1178 会议中心

2.两边和中间合并，链表+堆

SD二轮集训D1T2 第二题 BZOJ1150 数据备份Backup BZOJ2151 种树

3.用替换的思路来证明正确性

Codeforces798D Mike and distribution BZOJ1658 滑水（同一条链上尽量不交叉）

4.调整为某种极端情况

BZOJ2007 海拔 BZOJ1049 数字序列 BZOJ1385 Division expression BZOJ3130 费用流

5.用优先队列维护前k优解

BZOJ1598 牛跑步 BZOJ4520 K远点对 BZOJ2006 超级钢琴 BZOJ3784 树上的路径

分块&&莫队

1.块内维护排过序的数组

BZOJ3337 ORZJRY I （块状链表） SD三轮集训D4T3 Right BZOJ4028 公约数数列 Codeforces551E GukiZ and GukiZiana

2.利用权值分块来缩小修改复杂度

BZOJ4129 Haruna’s Breakfast BZOJ3236 作业 BZOJ3809 Gty的二逼妹子序列

3.用隔段时间重构的方法来代替块状链表

Codeforces455D Serega and Fun

4.用一个较大的数组记录每个块的信息

BZOJ2741 L

5.分成在同一块内/跨多个块等情况讨论

BZOJ3509 COUNTARI

6.删除操作不好进行的莫队：特殊的转移方法

BZOJ4358 permu

7.树上莫队

BZOJ3757 苹果树 SPOJ10707 COT2

8.利用分块平衡修改和询问的复杂度

BZOJ2388 旅行规划 Codeforces13E Holes

9.带修莫队

BZOJ2120 数颜色 BZOJ3052 糖果公园

均摊分析

1.每个位置只会被操作一次（合并，删除等）

BZOJ3333 排队计划 BZOJ4569 萌萌哒 BZOJ2959 长跑 BZOJ3252 攻略 BZOJ3319 黑白树

2.变化的情况是单调的

BZOJ4127 Abs（增量一定是正数） Codeforces444C DZY loves colors

数据结构

1.可并堆

(1).支持合并两个集合，动态维护最值

BZOJ2809 dispatching SD三轮集训D1T2 Fiend

(2).求全局最值：对每个堆顶维护一个堆

BZOJ2333 棘手的操作

2.主席树

(1).求区间第k大

BZOJ3524 Courier BZOJ3123 森林 SD三轮集训D1T1 Fable

(2).带有两重限制，其中一种满足前缀和性质

BZOJ3772 精神污染 SD二轮集训D1T1 第一题 BZOJ4556 字符串 BZOJ4408 神秘数 BZOJ3653 谈笑风生

(3).可持久化字典树

BZOJ4212 神牛的养成计划 BZOJ3261 最大异或和

3.线段树

(1).加法标记和乘法标记

BZOJ2962 序列操作

(2).比较复杂的update

BZOJ2957 楼房重建 POJ1151 Atlantis（矩形面积并） POJ1389 Area of Simple Polygons（矩形面积并） Codeforces811E Vladik and Entertaining Flags（在线段树内维护并查集）

(3).最靠左，最靠右，总的

POJ3667 Hotel BZOJ1756 小白逛公园

(4).维护连通性

BZOJ1018 堵塞的交通

(5).维护直线或线段：标记永久化

BZOJ4515 游戏 BZOJ1568 Blue Mary开公司

(6).统计子树信息：线段树合并

Codeforces666E Forensic Examination BZOJ3317 雨天的尾巴 BZOJ4756 Promotion Counting BZOJ4530 大融合

(7).区间标记是一个数列

BZOJ3221 树上询问（等差数列标记可以直接相加） Codeforces446C DZY loves Fibonacci numbers（类Fibonacci数列标记可以直接相加）

(8).历史最大值

BZOJ3064 CPU监控

(9).在线段树内维护矩阵

HDU6013 Lotus and Thermodynamics

(10).二维线段树

POJ2155 Matrix BZOJ1513 Tet-Tetris 3D

4.平衡树

(1).适当放宽维护信息的限制，比如允许出现空串等

BZOJ1500 维修数列

(2).维护dfs序：欧拉序列，括号序列等

BZOJ3729 Gty的游戏

5.并查集

(1).带有传递性质的信息维护问题

BZOJ1202 狡猾的商人 BZOJ4602 齿轮 BZOJ4195 程序自动分析

(2).维护无向连通关系

BZOJ4569 萌萌哒 BZOJ2303 方格染色 BZOJ3319 黑白树 BZOJ3076 反色刷

6.树链剖分

(1).单点询问与区间询问的转化

BZOJ3626 LCA BZOJ1103 大都市meg

(2).针对轻儿子的标记

BZOJ3862 Little Devil I

7.K-D tree

(1).带有多重限制的区间询问

BZOJ3489 A simple rmq problem BZOJ4154 Generating Synergy BZOJ4066 简单题

(2).平面上的部分求和问题以及点对

BZOJ2850 巧克力王国 BZOJ4520 K远点对（用优先队列）

8.LCT

(1).维护以删除时间为权值的最大生成树

BZOJ4025 二分图 BZOJ1453 双面棋盘

(2).动态的最小生成树

BZOJ2594 水管局长数据加强版

离线询问

1.倒序处理询问，删除变成添加

BZOJ1969 航线规划 BZOJ3319 黑白树

2.对询问排序然后动态维护

BZOJ3626 LCA BZOJ3529 数表 BZOJ2186 沙拉公主的困惑

3.预先做一遍询问来处理信息

BZOJ2333 棘手的操作（把同一个连通块内的点编号成连续区间） BZOJ4530 大融合 BZOJ3545 Peaks

图论

1.生成树

(1).将图转化为生成树进行维护

BZOJ1969 航线规划

(2).一定在生成树上的边：小于等于它的边无法连通它的两个端点

BZOJ2521 最小生成树

(3).建立最小生成树的模型

BZOJ1601 灌水

(4).Kruskal重构树

BZOJ3551 Peaks加强版

(5).生成树上的边小于等于环上的最大边

BZOJ1937 最小生成树 BZOJ3118 Orz the MST

2.二分图匹配

(1).匈牙利算法

BZOJ1854游戏 BZOJ3168 钙铁锌硒维生素（求字典序最小的解：贪心） BZOJ1191 超级英雄

(2).带权匹配：二分图或KM

BZOJ2539 丘比特的烦恼 POJ3686 The Windy’s POJ3565 Ants BZOJ1937 最小生成树（利用KM顶标的性质） HDU2853 Assignment（注意没有完备匹配的情况）

3.最短路

(1).最短路图是一个DAG

BZOJ1880 Elaxia的路线

(2).坐标系上的建图

BZOJ2541 冰原探险 BZOJ2304 寻路

4.Tarjan

(1).双连通分量：无向图中每一对点之间有两条不重复经过边或点的路

BZOJ2959 长跑

(2).缩点之后形成树结构或者DAG

Codeforces487E Tourists（新建代表连通分量的点来维护每个连通分量的信息） BZOJ1123 BLO BZOJ3887 Grass Cownoisseur

5.2-SAT：一个变量的状态对另外的变量造成限制

BZOJ1823 满汉全席 BZOJ1997 Planar（结论：当边数大于点数*3的时候一定不是平面图）

6.优化建图

(1).用差值转移的思想

BZOJ4289 Tax BZOJ1283 序列

(2).向一段区间内的点连边：线段树

BZOJ4383 Pustynia BZOJ3218 A+B Problem BZOJ3073 Journeys

7.0-1分数规划

POJ2976 Dropping Tests BZOJ3597 方伯伯运椰子（最优比率环） POJ2728 Desert King（最优比率生成树） POJ3155 Hard Life（最大密度子图）

8.差分约束：最大化->最短路，最小化->最长路，注意隐藏限制

POJ3169 Layout HDU3440 House Man HDU3666 Matrix Problem POJ1752 Advertisement BZOJ3436 小K的农场 BZOJ1077 天平（对常数部分也进行限制） BZOJ2788 Festival

9.拓扑排序

BZOJ2584 memory BZOJ2707 走迷宫 BZOJ1565 植物大战僵尸

10.邻接矩阵相关

BZOJNOIP十连测第一场B Tourist Attractions BZOJ1875 HH去散步 BZOJ1297 迷路

11.最长反链=最小链覆盖

BZOJ1143 祭祀

字符串

1.KMP

(1).KMP树

BZOJ3670 动物园 BZOJ3620 似乎在梦中见过的样子

(2).字符串匹配

Codeforces631D Messenger BZOJ3942 Censorting

2.AC自动机

(1).Fail树：所有包含x的串在x的结尾节点的子树中

BZOJ2754 喵星球上的点名 BZOJ3530 数数 BZOJ3881 Divljak

(2).前缀相同的串在Trie树上的同一个子树中

BZOJ4212 神牛的养成计划

3.后缀自动机

(1).Parent树：LCA代表最长公共后缀，出现过该串的节点在子树里

BZOJ3238 差异 BZOJ2555 Substring Codeforces666E Forensic Examination BZOJ4545 DQS的Trie FJWC2017D3 recollection BZOJ4556 字符串

(2).不同路径数=不同子串数目

BZOJ3998 弦论 SD一轮集训D5T1 字符串

(3).Right集合：当前子串的出现次数

Codeforces452E Three Strings Codeforces427D Match&Catch

(4).当前节点的合法长度：[step[fa]+1,step[now]]

Codeforces235C Cyclical Request BZOJ4516 生成魔咒

(5).广义后缀自动机

BZOJ3926 诸神眷顾的幻想乡

4.后缀数组

(1).单调栈维护height数组：计算每个数字作为LCP的区间

BZOJ3238 差异 BZOJ4199 品酒大会

(2).每个后缀贡献的不同子串：后缀长度-height[i]，按照字典序排列

BZOJ3230 相似子串 BZOJ4310 跳蚤 BZOJ4516 生成魔咒

(3).对字符串进行分段，一定经过某几个关键点

BZOJ2534 L-gap字符串 BZOJ2119 股市的预测 POJ3693 Maximum repetition substring

(4).对每个点二分LCP为x的区间

BZOJ3277 串 BZOJ4556 字符串

(5).用height给后缀分组

POJ1743 Musical Theme POJ3294 Life Forms

5.manacher

BZOJ2565 最长双回文串（以这个点结尾的最长回文串=覆盖这个点的最远回文中心） BZOJ3160 万径人踪灭

6.hash：快速判断子串相等

BZOJ4373 算数天才⑨与等差数列 BZOJ3574 抄卡组 BZOJ3555 企鹅QQ

数论

1.莫比乌斯反演

(1).没啥可说的画柿子吧

BZOJ2154 Crush的数字表格 BZOJ2301 Problem b

(2).用枚举因数代替枚举倍数，构造可以线筛的函数

BZOJ2820 YY的GCD BZOJ4407 于神之怒加强版 BZOJ2693 jzptab

(3).不能筛的函数观察性质，考虑不同种类质因子的影响

BZOJ3309 DZY Loves Math

(4).杜教筛：构造容易求前缀和的函数

BZOJ3930 选数 BZOJ3944 Sum 51nod 1227 平均最小公倍数 BZOJ4176 Lucas的数论

(5).利用反演构造更容易求解的函数

51nod1355 斐波那契的最小公倍数 HDU5212 Code

(6).不一定要把式子全部化开

BZOJ3739 DZY Loves Math III BZOJ2694 Lcm Codeforces235E Number Challenge

2.因子相关

(1). d(ij)=∑p|i∑q|j[(p,q)==1]

BZOJ3994 约数个数和 BZOJ4176 Lucas的数论 Codeforces235E Number Challenge

(2).不同的质因子个数非常少

BZOJ3643 Phi的反函数 BZOJ4197 寿司晚宴

(3).前缀gcd最多变化log次

Codeforces457D CGCDSSQ BZOJ4028 公约数数列

(4).大数质因子分解：pollard rho

POJ1811 Prime Test

(5).当直接做数字规模很大的时候考虑分解质因数

BZOJ1005 明明的烦恼 BZOJ1211 树的计数 Codeforces2B The least round way BZOJ3907 网格

(6).约数的幂次和：讨论加入一个质因子的影响

BZOJ1968约数研究 BZOJ2813 奇妙的Fibonacci BZOJ1845 Sumdiv（约数和计算公式： ∏(1+pi+p2i+...+pkii) ）

(7).裴蜀定理：若 gcd(a,b)=d ，则 ax+by 是d的倍数

BZOJ1441 Min

(8).线段(0,0)-(x,y)上的整点数目是gcd(x,y)

BZOJ3505 数三角形 BZOJ2190 仪仗队 BZOJ2005 能量采集

3.同余

(1).同余方程 Ax≡B(modC) 解的个数是 gcd(A,C)

BZOJ2219 数论之神（注意在变化式子过程中引起的值域变化）

4.欧拉定理： aφ(p)≡1(modp,(a,p)=1)

BZOJ3884 上帝与集合的正确用法

5.数论函数

(1). ∑i=1n[(i,n)==1]i=n+φ(n)+[n==1]2

51nod1227 平均最小公倍数 BZOJ2226 LCMSum

(2). ∑i=1n∑j=1n[(i,j)==1]=2∗φ(n)−1

HDU5780 gcd

(3). φ(n)=∏(pi−1)pai−1i

BZOJ1408 Robot BZOJ3813 奇数国

6.中国剩余定理

Codeforces710D Two Arithmetic Progressions

7.原根：乘除化加减

BZOJ2219 数论之神 BZOJ3992 序列统计

组合数学

1.错排公式 f(i)=(i−1)∗(f(i−1)+f(i−2))

BZOJ4517排列计数

2.斯特林数：n个不同的小球放到m个相同的盒子里

BZOJ4555 求和（通项公式 S(n,m)=1m!∑k=1m(−1)kC(m,k)(m−k)n ）

3.卡特兰数

COGS2287 疯狂的机器人（任意一个时刻前缀和不能为负） BZOJ2688 Green Hackenbush（二叉树的不同数目） BZOJ3907 网格

4.插板法：n个相同的小球放到m个不同的盒子里

BZOJ4402 Claris的剑 BZOJ2729 排队 BZOJ1272 Gate of Babylon Codeforces768F Barrels and boxes BZOJ4710 分特产 BZOJ4403 序列统计

5.Lucas定理：p进制分解，然后把结果相乘

(1).用Lucas定理算组合数

BZOJ1272 Gate of Babylon BZOJ4403 序列统计

(2).用Lucas定理的原理进行p进制数位DP

SD三轮集训D6T1 A BZOJ4591 超能粒子炮·改 BZOJ2629 binomial

6.组合数的连续合并

BZOJ1271 Gate of Babylon BZOJ3027 Sweet

FFT

1.把式子里面的组合数拆开

COGS2287 疯狂的机器人

2.生成函数：可以使用整数运算律

BZOJ3771 Triple BZOJ3625 小朋友和二叉树（解生成函数方程） COGS2259 异化多肽（无穷等比数列求和公式）

3.多项式求逆与多项式开根：分治

51nod1514 美妙的序列 BZOJ3625 小朋友和二叉树

4.三模数NTT：最后合并的技巧

51nod1348 乘积之和 BZOJ2294 释迦

5.FFT常数很大，尽量减少次数

BZOJ3509 COUNTARI BZOJ4827 礼物

6.用FFT进行字符串匹配

BZOJ4503 两个串 Codeforces528D Fuzzy Search BZOJ4259 残缺的字符串

概率与期望

1.求概率转化为求当前情况数/总方案数

BZOJ3772 精神污染 BZOJ2752 高速公路

2.设未知数，转化为对系数的递推

HDU4035 Maze ZOJ3329 One Person Game

3.条件概率，全概率公式

HDU4254 A Famous Game POJ3071 Football

4.设未知数列方程

BZOJ2337 XOR和路径 BZOJ2707 走迷宫 Codeforces113D Museum BZOJ3143 游走 HDU3076 ssworld VS DDD

5.平方的期望不等于期望的平方

BZOJ4318 OSU！

6.正推和倒推的区别

BZOJ2707 走迷宫 Codeforces540D Bad Luck Island HDU4336 Card Collector BZOJ1076 奖励关

高斯消元

1.求矩阵的逆：消成单位矩阵

BZOJ3168 钙铁锌硒维生素 SD一轮集训D6T1 字符串（用矩阵表示递推关系）

2.求行列式：缩成上三角矩阵，维护符号

BZOJ4301 小Z的房间（用辗转相除法避免取模）

3.线性基

(1).线性变化得出的数字个数或最大值等

BZOJ2844 albus就是要第一个出场 SD一轮集训D2T2 set（线性基更新时的顺序） BZOJ4269 再见Xor BZOJ2322 梦想封印

(2).最大权值线性无关组

BZOJ2460 元素 BZOJ3105 新Nim游戏

4.利用矩阵的性质优化时间复杂度

SD三轮集训D1T2 Fiend

5.解方程组

BZOJ2337 XOR和路径 BZOJ2707 走迷宫 POJ2947 Widget Factory（无解判定）

6.对自由元的处理

BZOJ1770 灯 BZOJ2466 树

博弈

1.每次操作将游戏分成多个独立部分：求sg函数时要异或起来

POJ2311 Cutting Game

2.阶梯博弈：找到奇数层和偶数层

BZOJ2739 Gty的游戏 HDU5996 dingyeye loves stone POJ1704 Georgia and Bob HDU3389 Game

3.利用对称性

POJ2484 A Funny Game POJ1740 A New Stone Game

单调性

1.单调栈

(1).求以某个数为最值的最长区间

BZOJ1657 奶牛的歌声

(2).寻找左边和右边第一个比它大的元素

BZOJ1345 序列问题 BZOJ3956 Count

(3).求凸壳或凸包

BZOJ1007 水平可见直线

2.指针的单调移动，维护信息

BZOJ3670 动物园 BZOJ2937 建造酿酒厂 BZOJ4653 区间 BZOJ1132 Tro BZOJ2238 数矩形

3.二分答案

(1).利用答案的单调性

BZOJ2406 矩阵 BZOJ2084 Antisymmetry BZOJ3958 Mummy Madness

(2).利用答案变化的连续性

SD二轮集训D2T1 第一题

4.如果一个点现在不可能是答案，以后也不可能

BZOJ3011 Running Away From the Barn

计算几何

1.半平面交

(1).直观的模型

BZOJ1018 瞭望塔 HDU1632 Polygons

(2).解不等式

BZOJ2732 射箭 BZOJ4445 小凸想跑步 POJ2540 Hotter Colder

2.辛普森积分：利用线段覆盖求函数值

BZOJ1502 月下柠檬树 BZOJ2178 圆的面积并

3.旋转卡壳：凸包上的单调性

BZOJ1185 最小矩形覆盖 HDU2202 最大三角形 BZOJ1069 最大土地面积

4.按照极角或斜率排序

BZOJ1132 Tro BZOJ2338 数矩形

5.最小圆覆盖：随机增量法

BZOJ1336 最小圆覆盖

6.根据条件列出直线方程转化为几何问题

BZOJ2388 旅行规划

7.Pick公式S=a+b/2-1：多边形内整点个数

POJ1265 Area POJ2954 Triangle

容斥原理

1.全部-至少一个+至少两个-…=一个也没有的

BZOJ2393 Cirno的完美算数教室 BZOJ2669 局部极小值 BZOJ4455 小星星 BZOJ4487 染色问题 BZOJ3294 放棋子 BZOJ3129 方程 BZOJ4710 分特产 BZOJ4596 黑暗前的幻想乡

2.所有的-一个也没有的=至少有一个的

BZOJ1089 严格n元树 POJ2151 Check the difficulty of problems

3.至少有k个的-C(k+1,k)* 至少有k+1个的+C(k+2,k) *至少有k+2个的…=恰好有k个的

BZOJ3622 已经没有什么好害怕的了 BZOJ2839 集合计数 Codeforces285E Positions in Permutations BZOJ2024 舞会 BZOJ3198 Spring

4.将“强制一部分满足要求，一部分不满足”转化为只强制一部分满足要求，然后容斥

BZOJ3622 已经没有什么好害怕的了 SD二轮集训D3T2 第二题 SD一轮集训D5T2 苹果树

5.补集转化

SD二轮集训D7T3 领主 BZOJ3513 idiots BZOJ4430 赌骆驼

6.Min-Max容斥

51nod1355 斐波那契的最小公倍数

7.与质因子相关的容斥用 μ 做容斥系数

BZOJ2986 Non-Squarefree Numbers Codeforces585E Present for Vitalik the Philatelist Codeforces547C Mike and Foam

分治

1.树分治

(1).在子树中减去不合法的部分

BZOJ3697 采药人的路径 SD二轮集训D7T2 国王 BZOJ4598 模式字符串 BZOJ2599 Race

(2).直接构造答案

BZOJ3784 树上的路径

2.CDQ分治&&整体二分

(1).整体二分时把初始条件也拆成操作一起二分

BZOJ4538 网络 BZOJ2674 Attack

(2).用CDQ分治优化DP

BZOJ2726 任务安排 BZOJ1492 货币兑换Cash BZOJ2244 拦截导弹

位运算

1.各位之间的独立性，分开计算

BZOJ2281 黑白棋 BZOJ2337 XOR和路径 BZOJ3668 起床困难综合征

2.bitset代替数组加速计算

BZOJ4810 由乃的玉米田 BZOJ3890 Meeting Time BZOJ4811 由乃的OJ BZOJNOIP十连测第一场B Tourist Attractions

带有多个条件

1.其中一个满足前缀和性质：主席树

BZOJ3489 A simple rmq problem BZOJ3772 精神污染

2.都是区间查询：K-D tree

BZOJ3489 A simple rmq problem BZOJ4154 Generating Synergy

3.带有偏序关系：CDQ分治

BZOJ2244 拦截导弹 SD二轮集训D7T3 领主 BZOJ3295 动态逆序对 BZOJ2253 纸箱堆叠 BZOJ4237 稻草人 BZOJ4553 序列 BZOJ4430 赌骆驼

4.将条件转化为平面上的问题

BZOJ4059 Non-boring sequences SD二轮集训D1T1 第一题

搜索

1.打表发现合法状态非常少

BZOJ2393 Cirno的完美算数教室 Codeforces768E Game of Stones

2.01边权单源最短路：特殊的Bfs

BZOJ3073 Journeys BZOJ NOIP十连测第一场C Walk

3.K短路：A*搜索

POJ2449 Remmarguts’ Date BZOJ1598 牛跑步 BZOJ1975 魔法猪学院

4.虽然复杂度不科学但是实测非常快

BZOJ3033 太鼓达人

5.设置必经点来限制路径形态

POJ3182 The Grove

6.floodfill

BZOJ2936 降水

Trick

1.模意义下除以一个数x：把模数扩大x倍

BZOJ2962序列操作（中间更换模数一般是不资瓷的） BZOJ3027 Sweet

2.注意“超过一半”这个条件

BZOJ3524 Courier BZOJ2456 mode

3.树上差分：路径统计变成子树统计

BZOJ3317 雨天的尾巴

4.先考虑最坏情况然后优化答案

BZOJ2064 分裂

5.将带有前缀和性质的询问拆分

BZOJ3626 LCA BZOJ2301 Problem b SD一轮集训D6T1 子序列

6.缩点：带有大量重复结构的东西

BZOJ4539 树 Codeforces631D Messenger

7.分成较大规模和较小规模两种情况讨论，设计两种时间复杂度不同的算法

Codeforces348C Subset Sums UOJ#246 套路

8.转化成前缀和或后缀和

BZOJ4866 由乃的商场之旅 Codeforces671E Xor and Favorite Numbers BZOJ4542 大数 BZOJ3261 最大异或和 BZOJNOIP十连测第三场A 平均数

9.用优先队列代替set维护动态最值

BZOJ4538 网络

10.假设已经求出了1..n-1的结果，设计递推式

51nod1514 美妙的序列 BZOJ3456 城市规划 BZOJ3625 小朋友和二叉树

11.适当的枚举规模较小的部分

BZOJ4827 礼物 BZOJ1799 同类分布 BZOJ1077 天平 BZOJ1132 Tro BZOJ1088 扫雷 Codeforces486D Valid Sets SD一轮集训D1T1 sum

12.列方程，寻找定量关系

BZOJ1045 糖果传递 POJ3565 Ants BZOJ2721 樱花

13.把第一关键字乘以一个常数然后加入第二关键字

HDU2853 Assignment POJ2987 Firing SPOJ839 OPTM

14.对序列差分

BZOJ2119 股市的预测 BZOJ4698 Sandy的卡片

15.高精度数的p进制分解

BZOJ2629 binomial

16.利用“趋近于无穷”的条件

Codeforces698C LRU

17.利用“1”和“-1”

BZOJ2209 括号序列 BZOJ2653 middle BZOJ1303 中位数图

Others

1.极大子矩形：极大化枚举思想和悬线法

Vijos1055 奶牛浴场 BZOJ1057 棋盘制作

2.树链的并：按照dfs序排序，减去相邻点的lca

BZOJ2754 喵星球上的点名 SD二轮集训D2T3 第三题 BZOJ3881 Divljak

3.求区间颜色数：离线询问+树状数组

BZOJ2754 喵星球上的点名 BZOJ2743 采花

4.模拟退火：当不确定性较大的时候可以贪心

BZOJ2428 均分数据

5.扫描线：考虑每个操作的影响或相邻操作之间的不变性

(1).矩形面积并

POJ1151 Atlantis POJ1389 Area of Simple Polygons BZOJ3958 Mummy Madness BZOJ4059 Non-boring sequences

(2).分段统计答案

BZOJ4422 Cow Confinement BZOJ1818 内部白点 BZOJ2161 布娃娃 BZOJ1845 三角形面积并 BZOJ4548 小奇的糖果

(3).相邻扫描线之间的有序性

BZOJ2584 memory BZOJ4561 圆的异或并

6.Burnside引理：求不动点的个数

HDU2481 Toy BZOJ1488 图的同构 HDU2865 Birthday Toy

7.prufer序列：给定度数要求的生成树数目

BZOJ1005 明明的烦恼 BZOJ1211 树的计数

8.基尔霍夫矩阵：图的生成树数目

BZOJ4031 小Z的房间 BZOJ1430 小猴打架 SD一轮集训D5T2 苹果树 BZOJ4596 黑暗前的幻想乡

9.倍增

(1).用倍增划分区间来减少操作次数

BZOJ1178 会议中心 BZOJ4569 萌萌哒

(2).每次操作相同的时候用倍增加速

SD一轮集训D1T1 sum BZOJ3992 序列统计 BZOJ1706 奶牛接力跑

10.逆序对：

(1).每个位置定义贡献：后面小于它的或者前面大于它的

BZOJ3333 排队计划 BZOJ2141 排队 BZOJ3295 动态逆序对 BZOJ2212 Tree Rotations

(2).冒泡排序的交换次数

Tsinsen1043 完美的代价 BZOJ2789 Letters

11.线性规划

BZOJ3118 Orz the MST BZOJ3265 志愿者招募加强版

12.dsu on tree

(1).子树统计问题

Codeforces246E Blood Cousins Return Codeforces357D Tree and Queries

(2).路径统计问题

Codeforces741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths（题目名字好长）

13.三分

(1).单峰函数

BZOJ2388 旅行规划 POJ3301 Texas Trip

(2).三分套三分

BZOJ1857 传送带

14.中位数相关

BZOJ1112 BLO

15.启发式合并

BZOJ3123 森林 BZOJ1483 梦幻布丁 BZOJ2733 永无乡