noip算法总结材料2016.docx

实用文档
算法总结
一、 动态规划和递推
dp 一般的解题步骤 ：
分析问题， 弄清题意——从原问题中抽象出模型——根据模型设计状态， 要求状态满足
最优子结构和无后效性ir[j];
end;
j:=next[j];
end;
end;
上面的代码中正边和反边的编号是相邻的，关注 inc(ans[0]) 的位置，是在递归调用的
后面
哈密尔顿回路
含义：经过所有点的一个回路
这是个 NPC问题，只有近似算法（暴搜就不提了）
比较好用的是 模拟退火 ，以环上相邻两点有边相连的个数 作为估价值，随机化调整
二分图匹配 ：
最大匹配：匈牙利算法，理论 O(nm)，实际复杂度好很多
最佳匹配： KM算法，理论 O(n^2m)，实际复杂度同匈牙利一样相当不错
——重要性质：最小可行定标和 = 最优匹配
KM 算法中构造了一个非常不错的不等式 lx[i] + ly[j] >= w[i,j] ，有的题目可以利
文案大全
实用文档
用这个不等式套 KM求出最小可行定标和，如
20101112 ti
糟糕的传染
网络流
非常神奇的一个东西，
数学味有余而图论味不足，
通常用来解决限制条件太强，
以至于
无论如何都表示不了状态的题，很多经典例题见《网络流
24 题》
通常使用的最大流算法是
dinic ，代码要背熟，一般能
10
分钟之内敲出来
最大流最小割定理
经典模型：最小割模型，最大权闭合图，平面图网络流转最小割
——参考神文 胡伯涛论文
费用流
相当于网络流的一个强化，能多处理一维信息。具体来讲就是给边多加一个“费用”
，
每次增广的费用就是这条增广路的费用之和
* 流量。
费用流有最小费用最大流和最大费用最大流，用
spfa 每次找条最短（长）路增广即可
最小费用最大流还可以用
zkw 算法加速，差不多比裸
spfa+ 增广快 10 倍的样子（在二
分图网络流上尤为明显） ，我和盾盾研究了一种更
nb 的费用流， 我命名为 “ 距离标号连
续增广路费用流算法
”，能够秒杀几千个点的稠密随机图，二分图就更不在话下了，速
度几乎达到了 dinic
的三分之一的样子，而且实现非常简单！
经典例题参考《网络流
24 题》
三、 贪心
贪心的关键是找结论，同时给出证明，然后就可以利用这个结论来做题了
当然，考场上对你猜出的结论给出证明通常是很难的， 所以用贪心法解题需要丰富的经验，正确的“题感” ，胆大心细才能搞出来
由于经常要取最优值，所以常常与堆、平衡树等数据结构结合起来
贪心 +其他算法：
由于贪心往往能大幅化简状态，利用问题的某些“单调性” ，加上贪心的思想，往往能
是问题大幅简化，从而结合其他算法解决问题
经典例题：田忌赛马，利用贪心来确定状态
四、 分治
分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用二分查找
思想很简单，功能很强大，边界要注意， 负数要特判 （ NOI2010 PIANO）
在非负数范围内的二分一般写法
如果是 l := mid - 1 或 + 1 则 mid := (l + r) div 2
而如果是 r := mid - 1 或 +1 则 mid := (l + r + 1) div 2
快速幂
a^b = (a^(b div 2))^2 + ord(odd(b))*a
取模也适用
文案大全
实用文档
—— 展：求 (1 + a + a^2 + a^3 + ⋯ + a^n) mod p 的
O(logn) 算法：分治
1 + a + a^2 + a^3 + ⋯ + a^n
= (1 + a + a^2 + a^3 + ⋯ + a^(n div 2))*a^(n div 2) + ord(odd(n))*a^n
两个快速 可以合到一起写
快速排序， 并排序
任何一本算法 上都会 的， 里就略 了， 得一提的是快排 得加上 随机化
k := a[random(r - l + 1) + l]
二分答案（