。。。没法直接发代码

原来blogspot会把
'<' 和 '>'编译掉..
'<'要写成'<' '>'要写成'>'...
不知道哪一天才能提供[code][/code]功能 :(

单调队列

扫盲贴:

单调队列是这样一种东西:

队列里面存放"决策"
队列需要维护一个连续时间范围内的最优决策
"过时"的决策将被弹出
队列元素的"时间戳"单调递增(即加入队列从队列尾部进行）
可知队列元素的"优性"(比如大小等..)递减
（简单证明：若队列元素a 在 b的左边 a没有b优。。那么在a没有出队列的时候b也肯定没有出队列
这样a 永无出头之日。。不可能成为后面某个时刻的最优决策了）

凸单调的1D/1D Dp:
f[i] = max/min { f[j] + w(i, j) } w(i, j)是凸的

g(a, b) 表示min{i | i > b > a 决策a没有决策b优，即决策b “追上了”决策a }
决策队列满足
g(i1, i2) < g(i2, i3) < ... (gik, gi(k+1) )
(一个决策一旦被另一个决策追上就永远不会优了..证明略 ^_^有兴趣的可以去翻书)
每到达一个时刻( 即i++ )
从队头开始把被追上的决策清理出去
然后队首的元素既是求f[i]的最优决策
同时将f[i]加入决策队列的队尾

伪代码:

qh = qt = 0
f[qh] = 0

for (int i=1;i<=n;i++) {
while (qh < qt && catch[qh+1] <= i) qh ++;
f[i] = F(i, q[qh]);
while (qh < qt && findcatchup(q[qt], i) <= catch[qt])
qt --;
catch[qt+1] = findcatchup(q[qt], i);
q[++qt] = i;
}

最后的十天在模拟套题的同时啃这些东西：

1.各种Dp题型

2.图的连通性、K度生成树

3.几何杂碎若干..(离散化处理、随机增量 等）

4.Nim游戏

熟练：树状数据结构(Interval Tree / Heap / Treap)

           network flow(dinic / spfa cost flow)

            KM

            DFA

Extra： nlogn SA / Lcp

               有上下界的网络流

               2-SAT

最小割模型

一个关系E,

Ei = { x, y, cost } 表示条件Ax 和 By 同时不满足时的代价为cost

CAx 表示条件Ax 满足时的代价

CBx 表示条件Bx满足时的代价

则要使总代价最小，即可构造网络

S - > Ai    容量为CAi

当Ai和Bj的关系属于E时， Ai -> Bj    容量为Ai和Bj关系的cost

Bj -> T   容量为CBj

则求这个网络的最小割即是最小代价

如NOI 06 profit:

条件Ai表示放弃某项工作Ai S->Ai的容量即为放弃时丢失的获利

条件Bj表示需要零件Bj  Bj->T的容量即为零件Bj的花费

Ai->Bj的容量为      不满足 Ai且 不满足Bj的损失

在本题中，不满足Ai 且 不满足Bj   即 选定了某项工作但是没有它必须的某个零件

根据题意这种情况非法，所以我们可以设定容量为 inf

图论代码的几个注意事项

1.构图的时候注意权值。。（费用流一正一副）

2.注意初始化

memset(info,-1,sizeof(info)); p = 0;

memset(vis, 0, sizeof(vis));

memset(fp, -1, sizeof(fp));

fillall(dis, inf); dis[S] = 0;

3.注意return true/false

MFCL3 第一阶段总结

今天把“初期”大致做完了，

剩下两个东西：KM和旋转卡壳

旋转卡壳据Zealot同学说他也没写过，我就忽略了( 我是个不求上进的孩子 =.= )

想起来判点在多边形内外还没写..

Zz from hi.baidu

2008-07-05 18:54

为在SCOI中XX的同志默哀三分钟...

Zz from hi.baidu

2008-07-02 23:01

bincode : 经典的构造题 O(N)

mobile : 2D indexed tree
ioiwari : MINMAX
twofive : usaco的经典题，状态压缩的dp，通过dp的结果决定答案
depot: 类似于Young Table的东西，
  搜索它们的加入次序
  一个显而易见的结论： 同一行的数在后面的数肯定比前面的数要 先 加入序列 （否则就会被挤下去）
  另一个结论：Tot(i+1)<=Tot(i) Tot表示一行的数个数 （被挤下来的数肯定有新的一个在原来一行占据位置）


今天效率还可以..

double crypt: 很奇妙的题。。没看懂
score: 还是博弈题，没做

Zz from hi.baidu

2008-06-23 20:23CEOI 2000:
XPLANET: 高斯消元。。当年需要压位才能不超时...
* Roads : 没做
CP : 贪心 佳佳书上的 归纳法证明
Fall: 无聊dp
* Sticks: 博弈 没有写code
Light: 还是佳佳树上的

CEOI 2001:
circuit: 并查集
trip : 无向图网络流两次增广
错了2次:(1).augment_path的时候每次只能+1 
  (2).打印路径的时候没有判断findpath(i)是否能到达T

Zz from hi.baidu

2008-06-23 20:23CEOI 2000:
XPLANET: 高斯消元。。当年需要压位才能不超时...
* Roads : 没做
CP : 贪心 佳佳书上的 归纳法证明
Fall: 无聊dp
* Sticks: 博弈 没有写code
Light: 还是佳佳树上的

CEOI 2001:
circuit: 并查集
trip : 无向图网络流两次增广
错了2次:(1).augment_path的时候每次只能+1 
  (2).打印路径的时候没有判断findpath(i)是否能到达T