Beyond the Void

NOI1999的6道题分别是[钉子和小球][棋盘分割][生日蛋糕][最优连通子集][01串][内存分配]。六道题个题难易差别不太大，没有送分题，也没有特别困难的题。

[钉子和小球]是概率递推问题，需要处理分数。[棋盘分割]是一个动态规划问题，但是很容易想成搜索。[生日蛋糕]是经典的搜索+剪枝，强力剪枝需要对题目足够透彻地分析，还需要一定的数学推导。[最优连通子集]是一个树形动态规划问题，题目描述全部以各种定义给出，需要耐心读题，仔细分析。[01串]的解决需要构造差分约束系统，然后利用最短路径算法求解，其数学模型有一定隐蔽性。[内存分配]是一道模拟题，但其细节却十分复杂，容易遗漏各种情况，需要缜密的思维和良好的编程能力。

做1999年的题我花了4天时间，还需继续努力。
Read the rest of this entry »

根据木桶原理，水位的高低取决于最低的边界。我们可以从最低的边界入手，向内灌水，使水面于边界齐平。如果灌到了新的边界，而且不低于最低的边界，则这个点一定是不能被灌水的。

每次取边界最小值向内灌水，于是可以用一个最小堆来维护高度。

算法流程如下：

1. 把所有的边界上的点加入堆，且标记为已使用过。
2. 取出高度最小的点(x,y)，枚举与(x,y)相邻的未使用过的点(x’,y’)，从(x’,y’)开始Floodfill，边界高度h=(x,y)的高度。
3. 重复第二步，直到堆为空。

• Floodfill(x,y)

1. 标记(x,y)为已使用过。
2. 如果(x,y)的高度>=h，则该点不能积水，加入堆并返回。
3. 否则(x,y)的点的积水量为h-(x,y)的高度。
4. 枚举与(x,y)相邻的未使用过的点(x’,y’)，Floodfill(x’,y’)。

Read the rest of this entry »

把特征串看作图中的一条边，建立一个图。我们只需计算，至少增加的边数k，能使图中存在一个欧拉回路，则N+k就是结果。

一个有向图存在欧拉回路的充要条件是图中有且只有一个连通分支且每一点的出度等于入度。假设图中只存在一个连通分支，则至少增加的边数k＝每个点出度入度之差的绝对值之和的二分之一。

如果图中存在多个连通分支，则对于每个连通分支，按一个连通分支的方法求其至少的加边数，再加上本来就存在欧拉回路的连通分支的个数，就是k的值。

求连通分量的方法可以用广搜或者并查集，时间复杂度为O(N)。
Read the rest of this entry »

这是一个动态规划的问题。对于题中给定的A(k)的定义，我们可以很容易发现累积误差最小的情况为取A(k)为这组数的中值（不是严格意义上的中位 数，是数列S[i]..S[j]中的S[(i+j+1)/2] /为整除）。于是我们很容易想到要从小到大排序，然后以长度为阶段动态规划。

状态设定

• F[i,j] 表示前i个地区，然成j种颜色时最小的总误差。
• P[i,j] 表示排序过后的序列中，第i位到第j位的最小误差。

状态转移方程

• F[i,j]=Min{ F[k,j-1] + P[k+1,i] | 0<=k<=i-1 }

边界条件

• F[i,j]=无穷大 (0<=i<=N , 0<=j<=M)
• F[0,0]=0

P[i,j]有定义式为

• P[i,j]=Sum{ Abs( S[k]-Mid(i,j) ) | i<=k<=j } (Mid(i,j)为S[i]..S[j]的中值)

但是如果我们直接这样求，时间复杂度高达O(N^3 + N^2*M)，关键在于求P[i,j]时浪费了太多时间。其实我们可以递推求出P[i,j]。

递推式

• P[i,j]=P[i+1,j] + Mid(i,j) – S[i]

边界

• P[i,i]=0

这样，我们就可以在O(N^2*M)内解决。

Read the rest of this entry »

首先是根据输入的前序遍历建树，然后树形动态规划，递归地建立二叉树。假设绿色为0，红色为1，蓝色为2。要求两遍动态规划。

以最大值为例，动态规划状态设定

• F[i,c] 以节点i为根的子树中，根的颜色为c时，这棵子树上颜色为0的节点的个数。

状态转移方程

如果i为叶节点

• F[i,c]=1 (c为0)
• F[i,c]=0 (c不为0)

如果i只有一个子节点

• F[i,0]=Max { F[i.left,1] , F[i.left,2] } + 1
• F[i,1]=Max { F[i.left,0] , F[i.left,2] }
• F[i,2]=Max { F[i.left,0] , F[i.left,1] }

如果i有两个子节点

• F[i,0]=Max { F[i,left,1]+F[i.right,2] , F[i,left,2]+F[i.right,1] } + 1
• F[i,1]=Max { F[i,left,0]+F[i.right,2] , F[i,left,2]+F[i.right,0] }
• F[i,2]=Max { F[i,left,0]+F[i.right,1] , F[i,left,1]+F[i.right,0] }

目标状态

• Max{ F[root,0] , F[root,1] , F[root,2] } (root为根)

以上为求最大值，求最小值方法一样，把Max全部改成Min即可。
Read the rest of this entry »