嗯，200分压线金牌。第二题输出没排序，就把本来的28分骗分送人了。不过貌似所有200分的第二题都是0，所以也没什么遗憾了。
zouxun考的很囧，第一题用了一种比我麻烦的代码搞了200多行结果WA不少，只得了65分，最后获得银牌，不免有些郁闷。
不过最终大家玩得还是很开心的。
这几天还是抽空写写总结。先把那个 A* 的小结写完，再把答应的某模拟赛题目出出来，最后再写个 APIO'09 总结。嗯，过两天回家再把 APIO'09 的题目加到 RQNOJ 上吧，第二题还是很不错的。第一题和第三题对基本功的考察也还是很不错的。
就写这么多。
2009年5月14日星期四
2009年5月12日星期二
A*算法浅谈(60% finished)
嗯，答应的事情的确有太多没有做好，现在就一点一点去补偿吧。
A*可以看成BFS的加强版，或者说BFS就是A*的特殊情况。这里我们在BFS的基础上来逐步介绍A*。我们只考虑路经寻找问题，即寻找从初始状态到目标状态的一条最短路径。我们定义 D[u] 为初始状态到状态 u 的最短路径长度，w[u, v] 为状态 u 到状态 v 的路径长度。
首先我们回顾BFS的过程，我们需要一个队列 queue 保存待扩展节点，一个 hash 表保存待扩展和已经扩展的节点，BFS 过程可以表示如下：
不难发现，这个过程与 SPFA 很像。
但是这个算法的效率是很低的，特别对于很多状态空间是无限的问题，BFS可能会迟迟找不到解。究其原因，我们发现，BFS过程完全是按照入队列的顺序扩展状态的，也就是说，如果把状态空间看作一个层次图，BFS 每次只遍历这个层次图的一层，然而每个层次中的大部分状态都是没有用的，可不可以不要去碰这些状态呢？另一方面，对于一些特定的问题，从某个状态出发，往往很容易看出一些后继状态是明显没有“前途”的，那么能不能尽量把这些状态延迟取出，以便加速求解（目标状态可能在这些状态开始扩展之前就到达了，这样就省去了扩展这些节点的操作）？
综合以上两种思路，我们考虑为每个状态 u 设计一个函数 h[u]（通常叫做这个算法的启发函数），表示我们估计从 u 状态到目标状态的最短路径还有多长，设 h*[u] 表示 u 到目标状态的实际最短路径常数。如果我们能直接计算出任意的 h[u]=h*[u]，那么 h[初始状态]=h*[初始状态] 就是答案。但这在大部分的问题中都很难做到。于是我们考虑改进 BFS，每次扩展 h 值最小的状态。但是思考之后可以发现这显然是错的，因为大体上来说一个对于任意一个状态 u 的后继状态 v，一般有 h[u] > h[v]，这样算法就很可能朝着一条路径一直搜索下去，即使找到了目标状态也还是不能保证解的最优性。所以我们考虑“经过状态 u 的最短路径的估计函数”f[u]（同上设最短路径长度的实际值为 f*[u]）。设 g[u]=g*[u] 表示从初始状态到状态 u 的最短路径长度，这可以准确得出，则有：f[u] = g[u] + h[u]。于是算法改为：每次扩展 f 值最小的状态。
但是我们又发现，这样仍然不能保证获得最优解，由于对 h* 估计的不确定性，仍然不能保证第一次找到目标状态时的路径就是最短路径（因为最短路径上的某个状态 u 可能由于错误估计的较大 f[u](h[u]) 值而迟迟得不到扩展），于是我们需要对 h 函数加一些限制，使它能更客观真实地反映一个状态的优劣程度。我们要求对任意状态 u，h[u] 必须满足 h[u] <= h*[u]，即 h[u] 是最短路径的下界。
乍一看找不到反例了，但是这种算法的确能保证第一次遇到的解是最优解吗？答案是肯定的，这种算法正是大名鼎鼎的 A* 算法。首先我们将整个算法流程重新描述如下：
算法正确性的证明分为两步（我的数学很烂，不很会严格证明，大家如果想看严格证明可以自己尝试或者参考《人工智能导论》中的相关章节）：
定理 1. 如果存在一条从初始状态到目标状态的路径，A* 算法一定可以找到这条路径。
说明：容易看出，A* 算法退化到极致之后就是朴素的 BFS，所以只要 BFS 可以找到解，A* 就一定可以找到解（当然，这种证明对于状态空间是无限的问题来说还是有些牵强，不过勉强还能说得过去吧）。
定理 2. 设最优解为 F*。A* 算法未完成时，队列 queue 中一定存在 F[u] <= F* 的状态 u。
说明：在一条最短路径（s、v1、v2、……、vk、t）上的状态 u 显然满足：
即 u 的估计价值 f[u] 不超过 F*。所以若 A* 算法未完成，则最短路径上的状态就没有全部被扩展，所以一定在这样的状态 u。
定理 3. A* 算法找到的解一定是最优解。
说明：首先根据定理 1，A* 算法一定可以找到解。又根据定理 2，只要 A* 算法未完成，总有 f[u] <= F* 的状态 u，所以 A* 算法每次扩展的状态 u 总有 f[u] <= F*，因而扩展到目标状态时，仍然有 f[t] <= F*，而 F* 为最优解，既有 f[t] = F*，定理得证。
A*可以看成BFS的加强版，或者说BFS就是A*的特殊情况。这里我们在BFS的基础上来逐步介绍A*。我们只考虑路经寻找问题，即寻找从初始状态到目标状态的一条最短路径。我们定义 D[u] 为初始状态到状态 u 的最短路径长度，w[u, v] 为状态 u 到状态 v 的路径长度。
首先我们回顾BFS的过程，我们需要一个队列 queue 保存待扩展节点，一个 hash 表保存待扩展和已经扩展的节点，BFS 过程可以表示如下：
1. 将初始状态加入 queue 和 hash 中
2. while (queue 非空)
3. 取出 queue 尾状态 u
4. 若 u 是目标状态，则 D[u] 为答案，结束算法
5. 枚举每个从状态 u 出发可以到达的状态 v
6. 若从 D[u] + w[u, v] < D[v] 则
7. 更新 D[v] = D[u] + w[u, v]
8. 若 v 不再 hash 中
9. v 入队并加入 hash
10. 不存在所需的路径
不难发现，这个过程与 SPFA 很像。
但是这个算法的效率是很低的，特别对于很多状态空间是无限的问题，BFS可能会迟迟找不到解。究其原因，我们发现，BFS过程完全是按照入队列的顺序扩展状态的，也就是说，如果把状态空间看作一个层次图，BFS 每次只遍历这个层次图的一层，然而每个层次中的大部分状态都是没有用的，可不可以不要去碰这些状态呢？另一方面，对于一些特定的问题，从某个状态出发，往往很容易看出一些后继状态是明显没有“前途”的，那么能不能尽量把这些状态延迟取出，以便加速求解（目标状态可能在这些状态开始扩展之前就到达了，这样就省去了扩展这些节点的操作）？
综合以上两种思路，我们考虑为每个状态 u 设计一个函数 h[u]（通常叫做这个算法的启发函数），表示我们估计从 u 状态到目标状态的最短路径还有多长，设 h*[u] 表示 u 到目标状态的实际最短路径常数。如果我们能直接计算出任意的 h[u]=h*[u]，那么 h[初始状态]=h*[初始状态] 就是答案。但这在大部分的问题中都很难做到。于是我们考虑改进 BFS，每次扩展 h 值最小的状态。但是思考之后可以发现这显然是错的，因为大体上来说一个对于任意一个状态 u 的后继状态 v，一般有 h[u] > h[v]，这样算法就很可能朝着一条路径一直搜索下去，即使找到了目标状态也还是不能保证解的最优性。所以我们考虑“经过状态 u 的最短路径的估计函数”f[u]（同上设最短路径长度的实际值为 f*[u]）。设 g[u]=g*[u] 表示从初始状态到状态 u 的最短路径长度，这可以准确得出，则有：f[u] = g[u] + h[u]。于是算法改为：每次扩展 f 值最小的状态。
但是我们又发现，这样仍然不能保证获得最优解，由于对 h* 估计的不确定性，仍然不能保证第一次找到目标状态时的路径就是最短路径（因为最短路径上的某个状态 u 可能由于错误估计的较大 f[u](h[u]) 值而迟迟得不到扩展），于是我们需要对 h 函数加一些限制，使它能更客观真实地反映一个状态的优劣程度。我们要求对任意状态 u，h[u] 必须满足 h[u] <= h*[u]，即 h[u] 是最短路径的下界。
乍一看找不到反例了，但是这种算法的确能保证第一次遇到的解是最优解吗？答案是肯定的，这种算法正是大名鼎鼎的 A* 算法。首先我们将整个算法流程重新描述如下：
算法正确性的证明分为两步（我的数学很烂，不很会严格证明，大家如果想看严格证明可以自己尝试或者参考《人工智能导论》中的相关章节）：
定理 1. 如果存在一条从初始状态到目标状态的路径，A* 算法一定可以找到这条路径。
说明：容易看出，A* 算法退化到极致之后就是朴素的 BFS，所以只要 BFS 可以找到解，A* 就一定可以找到解（当然，这种证明对于状态空间是无限的问题来说还是有些牵强，不过勉强还能说得过去吧）。
定理 2. 设最优解为 F*。A* 算法未完成时，队列 queue 中一定存在 F[u] <= F* 的状态 u。
说明：在一条最短路径（s、v1、v2、……、vk、t）上的状态 u 显然满足：
f[u] = g[u] + h[u] <= g*[u] + h*[u] = f*[u] = F*
即 u 的估计价值 f[u] 不超过 F*。所以若 A* 算法未完成，则最短路径上的状态就没有全部被扩展，所以一定在这样的状态 u。
定理 3. A* 算法找到的解一定是最优解。
说明：首先根据定理 1，A* 算法一定可以找到解。又根据定理 2，只要 A* 算法未完成，总有 f[u] <= F* 的状态 u，所以 A* 算法每次扩展的状态 u 总有 f[u] <= F*，因而扩展到目标状态时，仍然有 f[t] <= F*，而 F* 为最优解，既有 f[t] = F*，定理得证。
2009年5月6日星期三
8数码 A*
终于初步学会了A*，也把这个一直留着的8数码AC掉了。
A*的速度的确很快很强大。。。写得这么丑的代码都那么快。。。
PS：我用的启发函数是每个数字当前位置到目标位置的曼哈顿距离之和。
过两天有空写个 A* 的详细解释，也算对这几天研究的一个总结。
A*的速度的确很快很强大。。。写得这么丑的代码都那么快。。。
PS：我用的启发函数是每个数字当前位置到目标位置的曼哈顿距离之和。
过两天有空写个 A* 的详细解释，也算对这几天研究的一个总结。
program number8;
const
maxState = 100000;
Mask: array [0..9] of Longint = (1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1);
Ori: array [1..8, 1..2] of Longint = ((1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1));
type
TOpenState = record
P, F, G: Longint
end;
TClosedState = record
State, P: Longint
end;
var
State: array [1..3, 1..3] of Longint;
i, j: Longint;
a, b: Longint;
OpenCount, CloseCount: Longint;
Open: array [1..maxState] of TOpenState;
Closed: array [1..maxState] of TClosedState;
Current, CurrentG: Longint;
procedure Swap(a, b: Longint);
var
T: TOpenState;
begin
T := Open[a];
Open[a] := Open[b];
Open[b] := T;
Closed[Open[a].P].P := a;
Closed[Open[b].P].P := b
end;
procedure Decrease_Key(t, dstF, dstG: Longint);
var
u: Longint;
begin
u := t;
Open[u].F := dstF;
Open[u].G := dstG;
while (u > 1) and (Open[u div 2].F > Open[u].F) do
begin
Swap(u, u div 2);
u := u div 2
end
end;
function Extract_Min: Longint;
var
u: Longint;
begin
Closed[Open[1].P].P := 0;
Current := Closed[Open[1].P].State;
Extract_Min := Open[1].G;
Open[1] := Open[OpenCount];
dec(OpenCount);
u := 1;
while True do
if (u * 2 <= OpenCount) and (Open[u * 2].F < Open[u].F) then
begin
Swap(u, u * 2);
u := u * 2
end
else if (u * 2 + 1 <= OpenCount) and (Open[u * 2 + 1].F < Open[u].F) then
begin
Swap(u, u * 2 + 1);
u := u * 2 + 1
end
else
break
end;
function CalculateH: Longint;
var
i, j: Longint;
begin
CalculateH := 0;
for i := 1 to 3 do
for j := 1 to 3 do
if State[i, j] <> 0 then
inc(CalculateH, abs(i - Ori[State[i, j], 1]) + abs(j - Ori[State[i, j], 2]))
end;
procedure Expand(a, b, da, db: Longint);
var
i, j: Longint;
NowF, NowState: Longint;
Flag: Boolean;
begin
State[a, b] := State[da, db];
State[da, db] := 0;
Flag := False;
NowState := 0;
for i := 1 to 3 do
for j := 1 to 3 do
inc(NowState, State[i, j] * Mask[(i - 1) * 3 + j]);
NowF := CurrentG + 1 + CalculateH;
for i := 1 to CloseCount do
if Closed[i].State = NowState then
begin
Flag := True;
if (Closed[i].P <> 0) and (NowF <= Open[Closed[i].P].F) then
Decrease_Key(Closed[i].P, NowF, CurrentG + 1)
end;
if not Flag then
begin
inc(CloseCount);
inc(OpenCount);
Closed[CloseCount].State := NowState;
Closed[CloseCount].P := OpenCount;
Open[OpenCount].P := CloseCount;
Open[OpenCount].F := MaxLongint;
Decrease_Key(OpenCount, NowF, CurrentG + 1)
end;
State[da, db] := State[a, b];
State[a, b] := 0
end;
begin
fillchar(Open, sizeof(Open), 0);
fillchar(Closed, sizeof(Closed), 0);
OpenCount := 1;
CloseCount := 1;
readln(Closed[1].State);
Closed[1].P := 1;
Open[1].G := 0;
Open[1].P := 1;
while OpenCount > 0 do
begin
CurrentG := Extract_Min;
if Current = 123804765 then
begin
writeln(CurrentG);
halt
end;
for i := 1 to 3 do
for j := 1 to 3 do
begin
State[i, j] := Current mod Mask[(i - 1) * 3 + j - 1] div Mask[(i - 1) * 3 + j];
if State[i, j] = 0 then
begin
a := i;
b := j
end
end;
if a > 1 then
Expand(a, b, a - 1, b);
if a < 3 then
Expand(a, b, a + 1, b);
if b > 1 then
Expand(a, b, a, b - 1);
if b < 3 then
Expand(a, b, a, b + 1)
end
end.
2009年5月3日星期日
省选归来,一切正常,期待APIO'09
省选归来已经是一个星期之前的事情了，考的分数还是很让人郁闷的：不过半的280分。有的时候别人问我靠怎么样，我还可以炫耀一下：与第一名只差20分。殊不知，我与第三名只差10分。- -||
今年是我OI生涯最后一年了（如果拿不到金牌的话……）。所谓成也OI，败也OI。期望越大，失望越大。不过正常发挥就可以了吧。
这两天貌似很多事情都变了很多。QQ 好友数目呈指数爆炸式增长，五一的 RQNOJ 群变得异常火热。终于认识了传说中带狗牛，看到了 RQ 照片，大家还在 IPSC'09 组了队 ~^_^~（话说register添年龄的时候发现我们三的年龄恰成等差数列）。这样给了今年的 APIO 不少期待。虽然估计这次要考差，但见识到这么多传说中的牛人，也不虚此行吧。
怎么说着说着废话又连篇了。- -|| 就到这里吧，期待 APIO'09，大家共同加油！
今年是我OI生涯最后一年了（如果拿不到金牌的话……）。所谓成也OI，败也OI。期望越大，失望越大。不过正常发挥就可以了吧。
这两天貌似很多事情都变了很多。QQ 好友数目呈指数爆炸式增长，五一的 RQNOJ 群变得异常火热。终于认识了传说中带狗牛，看到了 RQ 照片，大家还在 IPSC'09 组了队 ~^_^~（话说register添年龄的时候发现我们三的年龄恰成等差数列）。这样给了今年的 APIO 不少期待。虽然估计这次要考差，但见识到这么多传说中的牛人，也不虚此行吧。
怎么说着说着废话又连篇了。- -|| 就到这里吧，期待 APIO'09，大家共同加油！
2009年4月16日星期四
2009年4月8日星期三
继续暴力搜索，SGU 125
题目大意：有两个 NxN (N<=3) 的矩阵 A、B。1 <= A[i, j] <= 9，B[i, j] 表示 A 中与 A[i, j] 相邻的<=4个格子内比 A[i, j] 大的格子数。给出 B，求 A。
为什么叫作继续呢。。。。。我也不好多说了。。。。。结果是 23ms 的 AC，能排上第一页了，不错不错。。。
为什么叫作继续呢。。。。。我也不好多说了。。。。。结果是 23ms 的 AC，能排上第一页了，不错不错。。。
program sgu_125;
{$APPTYPE CONSOLE}
const
NS = 'NO SOLUTION';
var
N: Integer;
i, j: Integer;
a11, a12, a13, a21, a22, a23, a31, a32, a33: Integer;
b11, b12, b13, b21, b22, b23, b31, b32, b33: Integer;
begin
readln(N);
if N = 1 then
begin
readln(a11);
if a11 <> 0 then
writeln(NS)
else
writeln(1)
end
else if N = 2 then
begin
readln(b11, b12);
readln(b21, b22);
for a11 := 1 to 9 do
for a12 := 1 to 9 do
for a21 := 1 to 9 do
if ord(a21 > a11) + ord(a12 > a11) = b11 then
for a22 := 1 to 9 do
if ord(a11 > a12) + ord(a22 > a12) = b12 then
if ord(a11 > a21) + ord(a22 > a21) = b21 then
if ord(a12 > a22) + ord(a21 > a22) = b22 then
begin
writeln(a11, ' ', a12);
writeln(a21, ' ', a22);
readln;
halt
end;
writeln(NS)
end
else
begin
readln(b11, b12, b13);
readln(b21, b22, b23);
readln(b31, b32, b33);
for a11 := 1 to 9 do
for a12 := 1 to 9 do
for a21 := 1 to 9 do
if ord(a12 > a11) + ord(a21 > a11) = b11 then
for a22 := 1 to 9 do
if ord(a12 > a22) + ord(a21 > a22) <= b22 then
for a13 := 1 to 9 do
if ord(a11 > a12) + ord(a13 > a12) + ord(a22 > a12) = b12 then
for a31 := 1 to 9 do
if ord(a11 > a21) + ord(a31 > a21) + ord(a22 > a21) = b21 then
for a23 := 1 to 9 do
if (ord(a12 > a13) + ord(a23 > a13) = b13) and
(ord(a12 > a22) + ord(a21 > a22) + ord(a23 > a22) <= b22) then
for a33 := 1 to 9 do
if ord(a13 > a23) + ord(a22 > a23) + ord(a33 > a23) = b23 then
for a32 := 1 to 9 do
if (ord(a22 > a32) + ord(a33 > a32) + ord(a31 > a32) = b32) and
(ord(a12 > a22) + ord(a21 > a22) + ord(a23 > a22) + ord(a32 > a22) = b22) and
(ord(a32 > a31) + ord(a21 > a31) = b31) and
(ord(a32 > a33) + ord(a23 > a33) = b33) then
begin
writeln(a11, ' ', a12, ' ', a13);
writeln(a21, ' ', a22, ' ', a23);
writeln(a31, ' ', a32, ' ', a33);
halt
end;
writeln(NS)
end
end.
2009年4月1日星期三
URAL 1127
小岛叫我做下，说不好做，可惜10分钟就ac了。。。时间空间复杂度都极小。。。至于其中缘由，见下程序。。。。。。。。。
题目大致意思是给你一些相同大小的正方体，每个正方体六个面上涂有不同颜色，选一些正方体堆成一个 1x1xK 的塔，要求前后左右四个面必须分别是一种颜色，问 K 最大为多少。
既然有人问了，就说明下，Q[a, b, c, d] 表示四个面颜色为 a、b、c、d （顺时针或逆时针）时的 K 的最大值。
题目大致意思是给你一些相同大小的正方体，每个正方体六个面上涂有不同颜色，选一些正方体堆成一个 1x1xK 的塔，要求前后左右四个面必须分别是一种颜色，问 K 最大为多少。
既然有人问了，就说明下，Q[a, b, c, d] 表示四个面颜色为 a、b、c、d （顺时针或逆时针）时的 K 的最大值。
program ural_1127;
const
Front = 1;
Right = 2;
Left = 3;
Rear = 4;
Top = 5;
Bottom = 6;
var
Ans, N: Longint;
i, j, k, l: Longint;
Q: array [1..10, 1..10, 1..10, 1..10] of Longint;
D: array [1..6] of Longint;
C: Char;
begin
fillchar(Q, sizeof(Q), 0);
readln(N);
for i := 1 to N do
begin
for j := 1 to 6 do
begin
read(C);
case C of
'A': D[j] := 1;
'B': D[j] := 2;
'C': D[j] := 3;
'G': D[j] := 4;
'O': D[j] := 5;
'R': D[j] := 6;
'S': D[j] := 7;
'V': D[j] := 8;
'W': D[j] := 9;
'Y': D[j] := 10
end
end;
readln;
// Front - Right - Rear - Left
inc(Q[D[Front], D[Right], D[Rear], D[Left]]);
inc(Q[D[Right], D[Rear], D[Left], D[Front]]);
inc(Q[D[Left], D[Front], D[Right], D[Rear]]);
inc(Q[D[Rear], D[Left], D[Front], D[Right]]);
inc(Q[D[Left], D[Rear], D[Right], D[Front]]);
inc(Q[D[Rear], D[Right], D[Front], D[Left]]);
inc(Q[D[Right], D[Front], D[Left], D[Rear]]);
inc(Q[D[Front], D[Left], D[Rear], D[Right]]);
// Front - Top - Rear - Bottom
inc(Q[D[Front], D[Top], D[Rear], D[Bottom]]);
inc(Q[D[Top], D[Rear], D[Bottom], D[Front]]);
inc(Q[D[Bottom], D[Front], D[Top], D[Rear]]);
inc(Q[D[Rear], D[Bottom], D[Front], D[Top]]);
inc(Q[D[Bottom], D[Rear], D[Top], D[Front]]);
inc(Q[D[Rear], D[Top], D[Front], D[Bottom]]);
inc(Q[D[Top], D[Front], D[Bottom], D[Rear]]);
inc(Q[D[Front], D[Bottom], D[Rear], D[Top]]);
// Left - Top - Right - Bottom
inc(Q[D[Left], D[Top], D[Right], D[Bottom]]);
inc(Q[D[Top], D[Right], D[Bottom], D[Left]]);
inc(Q[D[Bottom], D[Left], D[Top], D[Right]]);
inc(Q[D[Right], D[Bottom], D[Left], D[Top]]);
inc(Q[D[Bottom], D[Right], D[Top], D[Left]]);
inc(Q[D[Right], D[Top], D[Left], D[Bottom]]);
inc(Q[D[Top], D[Left], D[Bottom], D[Right]]);
inc(Q[D[Left], D[Bottom], D[Right], D[Top]])
end;
Ans := 0;
for i := 1 to 10 do
for j := 1 to 10 do
for k := 1 to 10 do
for l := 1 to 10 do
if Q[i, j, k, l] > Ans then
Ans := Q[i, j, k, l];
writeln(Ans)
end.
2009年3月30日星期一
市赛
可能我们这边比较怪吧，联赛之后还需要搞个市赛选出市队
昨天就在现在这个机房比完了，题目很水，没有原创题，打字也浪费时间，就不贴了。本来感觉不是很理想，有一道很简单的 dp 题没想出来，只交了个贪心。
但是现在出来的是我是满分，于是乎我便不再担心自己
但是很多同学的命途多舛啊
squll，本来说是 310 的，还是很有希望，今天再对了下是 240，唉。。。其实他靠这样差，我也有点过失，考试前我还让他看看 hlpp，但最大流这种东西市赛是根本不可能涉及的。然后考试的时候忘记提醒他细心了，结果第三题他少考虑了一些情况，于是就悲剧了。
作为学长的确考试之前我应该提醒高一同学仔细读题的，结果我却没有做到这样的责任。今天各人看了下程序，有两个人高精度写错，一个人犯把 i 打成 j 的低级错误，一个人没有按照要求少输出了解数……
无语
离开这个自己喜欢的“事业”，是很难受的一件事吧？
既然如此，还是努力奋斗吧
真的希望所有人都能早点将大学定掉，学得轻松点，玩得开心点
但是，唉。。。
也许高二之后就我跟小岛两个人了吧。。。。。。。
Bless everyone
昨天就在现在这个机房比完了，题目很水，没有原创题，打字也浪费时间，就不贴了。本来感觉不是很理想，有一道很简单的 dp 题没想出来，只交了个贪心。
但是现在出来的是我是满分，于是乎我便不再担心自己
但是很多同学的命途多舛啊
squll，本来说是 310 的，还是很有希望，今天再对了下是 240，唉。。。其实他靠这样差，我也有点过失，考试前我还让他看看 hlpp，但最大流这种东西市赛是根本不可能涉及的。然后考试的时候忘记提醒他细心了，结果第三题他少考虑了一些情况，于是就悲剧了。
作为学长的确考试之前我应该提醒高一同学仔细读题的，结果我却没有做到这样的责任。今天各人看了下程序，有两个人高精度写错，一个人犯把 i 打成 j 的低级错误，一个人没有按照要求少输出了解数……
无语
离开这个自己喜欢的“事业”，是很难受的一件事吧？
既然如此，还是努力奋斗吧
真的希望所有人都能早点将大学定掉，学得轻松点，玩得开心点
但是，唉。。。
也许高二之后就我跟小岛两个人了吧。。。。。。。
Bless everyone
2009年3月24日星期二
2009年3月22日星期日
又上rq，发了篇题解
无聊中看到某人的恐怖分子的题解
居然是硬枚举 s、t，o(N^5) 啊。。。。。。
于是就又写个了 Stoer-Wagner 算法介绍。。。。。。
这里原文照抄下吧。。。
题目：
居然是硬枚举 s、t，o(N^5) 啊。。。。。。
于是就又写个了 Stoer-Wagner 算法介绍。。。。。。
这里原文照抄下吧。。。
其实话说我一开始也是最大流做滴。。。最大流即使是用hlpp也要 o(n^4) 的复杂度，要像某个题解说的枚举 s、t 就到 o(n^5) 了。。而且hlpp也不是随随便便就能写出来滴。。。
不过看清本质之后，这一题本质就是求无向图的全局最小割，这其实是有专门算法的，叫 Stoer-Wagner 算法，复杂度不超过 o(N^3)，而且代码行数很短。。真的很短
下面概略说明下算法，正确性证明略去：
首先我们定义对于不存在的边 (u,v)，w[u, v] = 0。
之后介绍经典的 Contract(a, b) 操作：
加入新点 u，对于 a、b 之外的每个点 v，加入无向边 (u, v) 并令 w[u, v] = w[a, v] + w[b, v]
完成之后删除 a、b 两点及相关联的所有边
不难看出，每做一次 Contract 操作，图的节点数减少1
Stoer-Wagner 算法的正确性基于如下定理：
一个无向图的全局最小割，等于这个图的 s-t 最小割，或对这个图进行 Contract(s, t) 得到的图的全局最小割。
定理是显然的，下面我们说明如何求无向图的 s-t 最小割：
首先定义对于点集 A 和点 u，w[A, u] 表示 A 中所有点与 u 连边的权值之和。再次说明，不存在的边视为0处理。
1. 初始化点集 A={}
2. 任意取一点 a 加入 A 中
3. 每次取 w[A, u] 最大的点 u，将其加入 A，直到 A=V
4. 可取3中倒数第二次加入的点为 s，倒数第一次加入的点为 t（无向图顺序无关紧要），则对应的 s-t 最小割为 w[U-{t}, t]
证明可以用数学归纳法，大家自己试试吧^_^
不难看出，上述 s-t 最小割算法的朴素实现是 O(N^2) 的（第三步显然还可以用最大堆优化，达到更好的时间界），而对于一个图，Contract 操作最多进行 n-1 次（此时图中只剩1个点了）。所以算法的复杂度不超过 O(N^3)
而代码行数，可想而知有多短了。。。
而且即使写错了什么，调试起来也比调试hlpp轻松多了
题目：
一个国家由n个城市组成，任意两个城市间都有一条双向的道路。如今，恐怖分子想要炸掉其中的一些道路，使得这n个城市变得不再连通，也就是说，存在至少两个城市，它们之间不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到它们的目的，所需要的最小总代价是多少。
2009年3月20日星期五
还是写写东西吧...
发觉这个blog有很长时间没有写过东西了，现在决定还是好好利用起来吧
blog不必要像所谓空间那样，弄得花里胡哨，简洁就好
下周1、2段一，基本可以确定要挂蛋
下周日在本校市赛，估计问题不会很大。这两天打算不钻难题了，去vijos做点水题找找自信，同时晚上睡早些，补补最近一直不怎么样的精神状态。
准备今天晚上做个图论的小总结，把我了解的一些图论结构及算法都总结一下，尽量总结全一些，临考复习也方便些。
大概就这样吧。。。。这里还是真的要利用起来，不能浪费了 google 的服务啊……
blog不必要像所谓空间那样，弄得花里胡哨，简洁就好
下周1、2段一，基本可以确定要挂蛋
下周日在本校市赛，估计问题不会很大。这两天打算不钻难题了，去vijos做点水题找找自信，同时晚上睡早些，补补最近一直不怎么样的精神状态。
准备今天晚上做个图论的小总结，把我了解的一些图论结构及算法都总结一下，尽量总结全一些，临考复习也方便些。
大概就这样吧。。。。这里还是真的要利用起来，不能浪费了 google 的服务啊……
订阅：
博文 (Atom)
