三 06
先放出NOI2008 Day1，欢迎批评指正
三 06
这道题难在对图的深入分析。如果一个人能够看见两个不同的人，那么这两个人所戴的面具种类一定相同，同样，如果一个人能被两个人看见，这两个人所戴 的面具种类也一定相同。把每个人当作图中的一个顶点，a能看见b，则连接(a,b)一条有向边。我们把能够推断出的带相同面具的人成为一个类。
显然图中可能会有多个连通分量，对于某个连通分量，如果把边的方向去掉，该连通分量中存在一个无向环，则称该连通分量为环结构，否则成为 树结构。可以发现，一个环结构的连通分量，逐步把一个类的所有顶点收缩为一个顶点，最终一定会剩下一个有向环，而一个树结构的连通分量也会变成一个单向的 有向树。一个环结构的连通分量，最终有向环上顶点个数，就是该连通分量的最大类数，而且，最大类数的所有约数也都可以满足该连通分量的类数。而树结构连通 分量，有向树中的最长路径，就是该连通分量的最大类数。
显然环结构是关键的，如果同时存在树结构和环结构的连通分量，树结构可以忽略。如果存在两个（或多个）环结构连通分量，它们类数的最大公约数可以就是满足这两个连通分量的最大类数，它们类数的最大公约数的大于等于3的最小公约数就是满足这两个连通分量的最小类数。
关键问题就是求一个环结构连通分量的等价环的长度。收缩等位顶点的方法不便于编写，我们可以用一遍DFS的方法。对于一个连通分量，从一个 顶点开始DFS，有向边可以双向走，第一个顶点标号1。遇到正向的边，标号加1，遇到反向的边，标号减1。遇到已经访问过的点，则说明找到了一个等价环， 长度为该点应该被标的标号减去已有的标号的差的绝对值，标号不改变然后返回继续DFS。这样以O(N+M)的时间求出所有等价环长度，算出最大和最小公约 数即可。
三 06
这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。
例如一共需要4天，四天需要的人数依次是4,2,5,3。有5类志愿者，如下表所示：
| 种类 | 1 | 2 | 3 | 4 | 5 |
| 时间 | 1-2 | 1-1 | 2-3 | 3-3 | 3-4 |
| 费用 | 3 | 4 | 3 | 5 | 6 |
设雇佣第i类志愿者的人数为X[i]，每个志愿者的费用为V[i]，第j天雇佣的人数为P[j]，则每天的雇佣人数应满足一个不等式，如上表所述，可以列出
P[1] = X[1] + X[2] >= 4
P[2] = X[1] + X[3] >= 2
P[3] = X[3] + X[4] +X[5] >= 5
P[4] = X[5] >= 3
对于第i个不等式，添加辅助变量Y[i] (Y[i]>=0) ，可以使其变为等式
P[1] = X[1] + X[2] – Y[1] = 4
P[2] = X[1] + X[3] – Y[2] = 2
P[3] = X[3] + X[4] +X[5] – Y[3] = 5
P[4] = X[5] – Y[4] = 3
在上述四个等式上下添加P[0]=0,P[5]=0，每次用下边的式子减去上边的式子，得出
① P[1] – P[0] = X[1] + X[2] – Y[1] = 4
② P[2] – P[1] = X[3] – X[2] -Y[2] +Y[1] = -2
③ P[3] – P[2] = X[4] + X[5] – X[1] – Y[3] + Y[2] =3
④ P[4] – P[3] = – X[3] – X[4] + Y[3] – Y[4] = -2
⑤ P[5] – P[4] = – X[5] + Y[4] = -3
观察发现，每个变量都在两个式子中出现了，而且一次为正，一次为负。所有等式右边和为0。接下来，根据上面五个等式构图。
- 每个等式为图中一个顶点，添加源点S和汇点T。
- 如果一个等式右边为非负整数c，从源点S向该等式对应的顶点连接一条容量为c，权值为0的有向边；如果一个等式右边为负整数c，从该等式对应的顶点向汇点T连接一条容量为c，权值为0的有向边。
- 如果一个变量X[i]在第j个等式中出现为X[i]，在第k个等式中出现为-X[i]，从顶点j向顶点k连接一条容量为∞，权值为V[i]的有向边。
- 如果一个变量Y[i]在第j个等式中出现为Y[i]，在第k个等式中出现为-Y[i]，从顶点j向顶点k连接一条容量为∞，权值为0的有向边。
构图以后，求从源点S到汇点T的最小费用最大流，费用值就是结果。
根据上面的例子可以构造出如下网络，红色的边为每个变量X代表的边，蓝色的边为每个变量Y代表的边，边的容量和权值标已经标出(蓝色没有标记，因为都是容量∞，权值0)。
在这个图中求最小费用最大流，流量网络如下图，每个红色边的流量就是对应的变量X的值。
所以，答案为4*3+2*3+3*6=36。
上面的方法很神奇得求出了结果，思考为什么这样构图。我们将最后的五个等式进一步变形，得出以下结果
① – X[1] – X[2] + Y[1] + 4 = 0
② – X[3] + X[2] + Y[2] – Y[1] – 2 = 0
③ – X[4] – X[5] + X[1] + Y[3] – Y[2] + 3 = 0
④ X[3] + X[4] – Y[3] + Y[4] – 2 = 0
⑤ X[5] – Y[4] – 3 = 0
可以发现，每个等式左边都是几个变量和一个常数相加减，右边都为0，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求
最小，所以要在X变量相对应的边上加上权值，然后求最小费用最大流。
我写的是朴素的SPFA算法求增广路的最小费用流算法，可以在题目时限内通过所有测试点。
在NOI的现场上，该题得分的平均分12.56，只有高逸涵大牛拿到了满分。不能不说这是一道难题，难就难在抽象出问题的数学模型，设计有效的算法。而信息学竞赛正朝着这个方向发展，数学建模将是解决问题的共同关键步骤。
三 05
基本方法
首先，注意一个重要的条件“每个城市最多只和一个位于它东边的城市相连”，通过这个条件，必须能够明白这个国家的公路网其实是树（或森林）。为什么 是树？我们知道，树中除了根其余节点都有且只有一个父节点，假设每个城市东边的城市就是它的父节点，恰好满足是树的条件。把城市1当作根节点，如果每个节 点都有到达根节点1的路径，那么肯定只有一棵树，如果图中有多个连通分量，那么是无解的，输出两个-1。另外对于这道题，由于数据可以保证不存在环，只需 判断M是否为N-1即可。
明白这是一棵树以后，问题就清晰多了。问题可以被描述为：给定一个根节点为1的数要求在树中找到一些不相交的链，使得每个节点的不便利值的最大值最小，并求出满足条件的方案个数。一个节点的不便利值就是从该节点到根的路径上经过的非链边的条数。
先考虑第一问，求最小不便利值。在纸上随意画几棵树，算出最小不便利值，可以发现很难使最小不便利值很大。当根节点至少有三个子节点时，才 能使不便利值为1，而第二层的节点再都至少有三个子节点，才能使不便利值为2。可以发现，只有节点个数至少为一个高度为k+1的满三叉树，才能使不便利值 达到k，反证法很容易证明。对于最大的数据N<=100000，也不过最多可能有10层满三叉树，最大达到的不便利值为9。发现第一问的可能值很 少，可以考虑和第二问共同解决。可以知道，使得方案数大于0的最小不便利值B，一定为结果。于是可以从0开始枚举第一问的答案，计算方案数，直到方案数大 于0。
解决第二问，需要用到树形动态规划。考虑每个子树根节点向下连边构造不相交链，它向下连边有3种可能，不连边，只连一条边，只连两条边。不可能连更多，否则就会出现相交的链，连两条边还必须满足它的父节点没有向它连边。据此定义：
- F[i,b]为以i为根的子树中，每个节点相对于子树的根最大不便利值不超过b，且子树根节点向下连两条边的方案个数。
- G[i,b]为以i为根的子树中，每个节点相对于子树的根最大不便利值不超过b，且子树根节点向下连一条边或不连边的方案个数。
- 对于F[i,b] (b>0)
- 当i有1个或0个子节点
- F[i,b]=0
- 当i有至少2个子节点
- F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l为i的不同的子节点)
- 当i有1个或0个子节点
- 对于G[i,b] (b>0)
- 当i有0个子节点
- G[i,b]=1
- 当i有至少1个子节点
- G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l为i的不同的子节点)
- 当i有0个子节点
特殊地，当b为0时
- 对于F[i,b]
- 当i有且只有2个子节点
- F[i,b]=G[j,b]*G[k,b] (j和k为i的不同的子节点)
- 当i有多于或少于2个子节点
- F[i,b]=0
- 当i有且只有2个子节点
- 对于G[i,b]
- 当i没有子节点
- G[i,b]=1
- 当i有且只有1个子节点
- G[i,b]=G[j,b] (j为i的子节点)
- 当i有多余1个子节点
- G[i,b]=0
- 当i没有子节点
时间复杂度为O(N^3*logN)。根据上述所有的方程，直接进行树形动态规划，可以拿到40~50分。观察N的范围(N<=100000)，要想全部通过，必须优化到O(N*logN)，向着这个目标，开始着手优化。
状态转移优化
- F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l为i的不同的子节点)
- G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l为i的不同的子节点)
再次观察上述两个方程，发现大部分时间浪费在这里，尤其是Π(F[l,b-1]+G[l,b-1])，重复计算了很多次。是否可以把它先计算出呢？ 我的第一想法就是设置一个变量记录，令W=Π(F[l,b-1]+G[l,b-1]) (l为i的所以子节点)。在计算G[i,b]的Σ内部时，由于每次Π(F[l,b-1]+G[l,b-1])都少乘一个(F[j,b-1]+G[j,b- 1])，而多乘一个G[j,b]，结果是W/(F[j,b-1]+G[j,b-1])*G[j,b]。但这种想法是错误的，首先(F[j,b- 1]+G[j,b-1])可能为0，除法不可用，就算不为0，由于结果要求一个mod Q以后的值，除法会破坏同余的性质。由于式子庞大而繁杂，不利于思考，我把它变换形式后思考。
对于给定的i,b，设节点i有V个子节点，定义
- A[i]=F[j,b-1]+G[j,b-1] (j为节点i的子节点 A[i]为一个连续的数组 (1<=i<=V) )
- B[i]=G[j,b] (j,k为节点i的两个不同子节点 B[i]为一个连续的数组 (1<=i<=V) )
- R0=Π(A[i]) (1<=i<=V)
- R1=Σ(B[i]*Π(A[j])) (1<=i,j<=V ,i!=j)
- R2=Σ(B[i]*B[j]*Π(A[k])) (1<=i,j,k<=V ,i!=j ,i!=k ,j!=k)
则F[i,b]=R2，G[i,b]=R0+R1
我们的目的是要在线性的时间内求出R0,R1,R2，需要定义辅助的线性表。
- 设sf[i]为A[i]的从第i项开始的后缀之积，则有
- sf[V]=A[V]
- sf[i]=sf[i+1]*A[i] (1<=i<=V-1)
- 设pf[i]为A[i]的以第i项为尾的前缀之积，则有
- pf[0]=1
- pf[i]=pf[i-1]*A[i] (1<=i<=V)
显然，R0=pf[V]。求R1线性时间的方法不难想到，R1就是表A中去除第i个元素换成B[i]的所有的和，对于一个给定的i，只需加上 pf[i-1]*B[i]*sf[i+1]，就可以实现线性时间的求和。而求R2看似与求R1类似，却要取出两个元素替换，不易想出线性时间的方法。由于 要取两个元素，考虑固定第一个位置，第二个元素位置变化的和就与求R1类似了。
- 定义C[i]为以第i项为开头的所有替换的后缀积之和。
定义式为 C[i]=Σ(B[j]*Π(A[k])) (1<=i,j,k<=C ,i<=j,i<=k,j!=k)
为了快速求出所有C[i]，发现C[i]与C[i+1]之间有递推关系
- C[V]=B[V]
- C[i]=C[i+1]*A[i] + B[i]*sf[i+1]
于是可以在线性时间内求出了C。同时很方便，R1=C[1]。
- R2=Σ(pf[i-1]*B[i]*C[i+1]) (1<=i<=N-1)，也可以在线性时间内求出了。
经过上述优化，每次状态转移就成了O(V)，而每个节点被访问一次，所以总的时间复杂度为O(N*logN)，理论上可以拿到满分了。但是还有一下 细节不容忽视，如果方案数不为0，而Mod Q以后恰为0了，此时枚举应该中止了，但却没有，怎么办。我的方法是增设了两个数组，记录F[i,b]和G[i,b]的每项是否为“真正的0”(区别于 mod以后的0)，在状态转移的处理中较为麻烦，但是可以判断了。
这是NOI2008相对较简单的一道题了，NOI上有6位大牛拿到了满分，而且平均分高达21.122。但是对于包括我在内的大多数人来说，做出这道题依然很不容易。
Read the rest of this entry »
Recent Comments