文档介绍：平衡规划
——浅析一类平衡思想的应用
引言
状态
平衡
状态
状态
稳定
构建平衡
引言
例题一:任意图匹配修改主算法平衡思维与实现复杂度
例题二:高精度计算
修改程序实现细节
平衡程序各部分之间的复杂度
效果优秀的非完美算法
例题三:NOI2007 day2 Catch
非完美算法取得优秀效果的实例
平衡所花时间与所取得的成果
复杂问题的简单化构造
例题四:数列维护
模型简化
平衡时空复杂度与实现复杂度
例题五:树的维护
特例与一般的转化
平衡特例与一般的关系
经典算法的非典型实现
√
经典算法的非典型实现
经典算法:
经典≠简单
有效解决一类问题
障碍
平衡规划
经典算法的非典型实现
Jackpot (PKU 2103)
题目描述:
等概率选择任意整数,求选到的数能被给定的p1,p2,p3...pn中至少一个数整除的概率(用最简分数表示,n≤16)。
实现不同
性能不同
经典算法
实现方法
实现方法
实现方法
实现方法
经典算法的非典型实现
10^k压位的高精度实现
for i  1 to a[0] + 1 do
begin
p  a[i] * b + ;
a[i] ;
end;
2^k压位的高精度实现
for i  1 to a[0] + 1 do
begin
p  a[i] * b + p shr k;
a[i]  p and (2^k-1);
end;
p div 10^k
p mod 10^k
实现不同
性能不同
常见优化:压位
有效减少数组长度
输出速度
运算速度
经典算法的非典型实现
难思维
难实现

简单
实用
经典算法
有效解决一类问题。
经典≠简单
经典算法的非典型实现
警卫安排问题(ural 1099)
题目描述:
给定若干警卫间搭档关系,要求成对给警卫安排保卫工作,求能够安排警卫的最大值。(警卫人数不超过222)
模型:任意图的最大匹配!
经典算法:带花匈牙利树
经典算法:交错增广树
联想:二分图最大匹配
经典算法的非典型实现
反例
3
4
5
2
1
6
7
8
3
4
5
2
1
6
7
3
2
1
6
7
8
经典算法的非典型实现
3
4
5
2
1
6
7
8
另一个反例
3
4
5
2
1
6
7
3
4
5
2
1
6
7
8