vol2.htm

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

  <li>need[n,1]：表示以n为根的子树中的全部结点都被了望到，但n结点上没有士兵时所需的最少士兵数；
  <li>need[n,2]：表示以n为根的子树中的全部结点都被了望到，且n结点上有士兵时所需的最少士兵数。</ul>
　　每个结点三个need值的计算，还要分叶子结点与非叶子结点来讨论。
  <ul><li>对叶子结点i：显然，need[i,0]=0，need[i,1]=maxint（maxint表示不可能），need[i,2]=1。
  <li>对非叶子结点i（用j表示它的任一个儿子）：
    <ul><li>need[i,0]的计算：因为结点i本身不可以被了望到，所以它的任何一个儿子结点上都不可以放士兵，即need[i,0]应该等于所有need[j,1]之和。若有某个need[j,1]为maxint，那么need[i,0]亦为maxint。
    <li>need[i,1]的计算：因为结点i本身没有士兵，所以它的每个儿子都必须被i的子树中的结点上的士兵了望到，而且至少一个儿子结点上有士兵。也就是说，need[i,1]应等于所有min{need[j,1],need[j,2]}之和，只是在所有儿子都满足need[j,1]&ltneed[j,2]时，需要往need[i,1]上加上最小的一个need[j,2]-need[j,1]。
    <li>need[i,2]的计算：因为结点i本身就有士兵了，所以它的儿子结点怎样都可以，即need[i,2]等于所有min{need[j,0],need[j,1],need[j,2]}之和加1。</ul></ul>
　　设根结点为root，则min{need[root,1],need[root,2]}就是答案。
<script>detail 1148,"救护伤员"</script>
　　虽然数据范围小得搜索都能过，但我还是要讲一下求X、Y顶点数相等的二分图<font color=blue><b>最大权匹配</b></font>（也叫<font color=blue><b>最佳匹配</b></font>）的<font color=blue><b>KM算法</b></font>。<p>
　　KM算法是通过给每个顶点一个标号（叫做<b>顶标</b>）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点X<sub>i</sub>的顶标为A[i]，顶点Y<sub>i</sub>的顶标为B[i]，顶点X<sub>i</sub>与Y<sub>j</sub>之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。KM算法的正确性基于以下定理：<br>
　　<b>若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做<b>相等子图</b>）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。</b><br>
　　这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。<br>
　　初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点X<sub>i</sub>关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。<br>
　　我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
  <ul><li>两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
  <li>两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
  <li>X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
  <li>X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。</ul>
　　现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|X<sub>i</sub>在交错树中，Y<sub>i</sub>不在交错树中}。<p>
　　以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n<sup>4</sup>)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n<sup>2</sup>)。实际上KM算法的复杂度是可以做到O(n<sup>3</sup>)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。
<script>detail 1151,"拼凑春联"</script>
　　按每相邻两个字母是否相同可以把长度为7的春联分为2<sup>7-1</sup>=64类，设第i类有count[i]句，则答案为所有的C(count[i],2)之和。
<script>detail 1155,"拯救Angel行动"</script>
　　这个题是典型的分层图BFS。在最坏情况下，因为钥匙有10种，故可以用0至1023这1024个数对应已取得的钥匙的1024种状态，把图分成1024层。这个图并不大，只有15*15*1024=230400个结点。因为从一个结点出发只有4种走法，所以完全不必担心TLE。
<script>detail 1156,"传球问题"</script>
　　不要受“高二数学改编”误导而想排列组合，这个题要用DP。用a[i]表示传了i次后球又回到甲手里的传法总数，b[i]表示传了i次后球到了乙手里的传法总数，当然，b[i]也表示传了i次后球到了丙、丁等人手里的传法总数，因为乙、丙、丁等人的地位是一样的。很容易写出状态转移方程：
  <blockquote>
    a[i]=(p-1)*b[i-1]（倒数第二次只能传给乙、丙等p-1个人）<br>
    b[i]=a[i-1]+(p-2)*b[i-1]（倒数第二次或者传给甲，或者传给丙、丁等p-2个人）<br>
    显然a[1]=0，b[1]=1。
  </blockquote>
　　但是，用这种方法递推太慢了，n取最大值2<sup>31</sup>-1时显然要超时。换一种思路：假设要传i+j次，考虑传了i次以后的情况，列出如下方程：
  <blockquote>
    a[i+j]=a[i]*a[j]+(p-1)*b[i]*b[j]（传了i次后，球可以又回到甲手里，也可以在其他p-1个人手里）<br>
    b[i+j]=a[i]*b[j]+b[i]*a[j]+(p-2)*b[i]*b[j]（传了i次后，球可以在甲手里，也可以在乙手里，也可以在其他p-2个人手里）<br>
    同样，a[1]=0，b[1]=1。
  </blockquote>
　　用这组方程可以很容易设计出O(logn)的算法。
<script>detail 1157,"愚蠢的教官"</script>
　　在以下的叙述中，sum(a,b)表示从a加到b的和（a<=b，且a,b为整数）。<br>
　　我们把小于等于(n+1) div 2的号叫做<b>小号</b>，其余的号叫做<b>大号</b>。显然，小号都排在奇数位上，大号都排在偶数位上。那么，在绝对值和的计算过程中，不在端点的大号都做了两次被减数，不在端点的小号都做了两次减数，而在端点大号或小号的则只做了一次被减数或减数。而随n的奇偶性不同，最后一个数是大号还是小号也不同，也就是说最后一个数的“功能”（被减数还是减数）不同。于是我们对n的奇偶性分情况讨论。<br>
　　当n是奇数时，队首的1少做了一次减数，队尾的n div 2+1也少做了一次减数，于是绝对值和=2(sum(n div 2+2,n)-sum(1,n div 2+1))+1+n div 2+1。这个式子最终可以化简到n*(n-1) div 2。<br>
　　用last(n)表示n个人的队列中队尾的编号。当n是偶数时，队首的1少做了一次减数，队尾的last(n)少做了一次被减数，于是绝对值和=2(sum(n div 2+1,n)-sum(1,n div 2))+1-last(n)。剩下的工作就是求last(n)了。当n为奇数时，显然last(n)=n div 2+1。当n为偶数时，把所有的小号全部去掉，大号全部减去n div 2，发现现在的队列变成了n div 2个人时的队列，即last(n)=n div 2+last(n div 2)。这样一直递归下去，直到n变成奇数为止。<br>
　　算法复杂度仅为O(logn)。
<script>detail 1159,"半数集"</script>
　　本题我采用的是DFS算法。判重的问题我是这样解决的：对每一个数串，按某种规则将它划分成若干个数。如果这些数恰好是搜索到这一个数串时栈中的数，那么就把答案加1，否则就不加。这样就可以保证相同的数串只算一个。这个规则就是：从后往前划分，使每个数都尽可能大。当然，每个数的开头都不能是0。<br>
　　举个例子：假设输入的数是99，那么按照规则，数串123499的划分应该是12 34 99。搜到这个数串时，如果栈中的数恰好就是12和34，那么答案加1；如果栈中的数是1 2 34或者1 2 3 4，则不加1。
<script>detail 1163,"炼金术"</script>
　　<b>题目叙述有一点毛病：可以不把金子炼成别的金属而直接送出境。</b><br>
　　算法嘛，就是用Dijkstra求点1到其它各点的最短路，再用Dijkstra求其它各点到点1的最短路，答案便是每个点的两个最短路长度与单价的一半的和的最小值。不说“即可”了，因为这个Dijkstra要用堆来优化，这个编程挺费事。另外，两个Dijkstra可以一起做，这样当某个点的两个最短路长度都已经求出来时，可以立即更新答案。如果某个Dijkstra中堆顶元素的最短路长度已经超过了答案，这个Dijkstra就可以停止了。
<script>detail 1164,"猴子分桃"</script>
　　用a<sub>k</sub>表示第k个猴子走后剩余的桃子数。我们要求的就是a<sub>0</sub>和a<sub>n</sub>的最小值。由题意可列出递推式：<center>a<sub>k+1</sub>=(a<sub>k</sub>-1)*(n-1)/n……①</center>
　　这个递推式的形式类似等比数列的递推式，但多一个-1。为了将它整理成标准的等比数列的形式，我们设<center>b<sub>k</sub>=a<sub>k</sub>+x……②</center>让{b<sub>k</sub>}成等比数列：<center>b<sub>k+1</sub>=b<sub>k</sub>*(n-1)/n……③</center>而x是未知数。下面想办法求x：<br>
　　把②式代入③式，得<center>a<sub>k+1</sub>+x=(a<sub>k</sub>+x)*(n-1)/n</center>即<center>a<sub>k+1</sub>*n=a<sub>k</sub>*(n-1)-x……④</center>
　　同时把①式整理成如下形式：<center>a<sub>k+1</sub>*n=a<sub>k</sub>*(n-1)-(n-1)……⑤</center>
　　比较④⑤两式，得<center>x=n-1</center>
　　回过头来我们再关注数列{b<sub>k</sub>}。显然<center>b<sub>n</sub>=b<sub>0</sub>*[(n-1)/n]<sup>n</sup></center>因此<center>b<sub>0 min</sub>=n<sup>n</sup>，b<sub>n min</sub>=(n-1)<sup>n</sup></center>代入②式即求得答案：<center>a<sub>0 min</sub>=n<sup>n</sup>-(n-1)，b<sub>n min</sub>=(n-1)<sup>n</sup>-(n-1)</center>
<script>detail 1165,"切蛋糕"</script>
    <img align=right src=img_vol2/1165_1.gif><img align=left src=img_vol2/1165_2.gif>
　　先讨论比较简单的直线的情况。若直线没有切着蛋糕，则答案显然。下面只讨论直线切着蛋糕的情况。观察一下右面这个图，图中直线的上方有2块蛋糕，而下方有3块。每一块的外边（这个“边”不念轻声）都有一个特征：左转，比如下方较大的那一块，它的外边是A-4-5-F，是左转的。每一条内边也有一个共同特征：右转。还以下方较大的那一块为例，它的内边是E-12-13-B，是右转的。恰好，每一块蛋糕都有且仅有一个外边，所以我们只需统计一下在直线上下方各有多少段左转的边界，第一问就已经解决了。<br>
　　这一结论也适用于圆外蛋糕数目的统计，但对于圆内就不适用了，因为圆内的每块蛋糕没有“外边”、“内边”的概念，它的边数不固定，每条边的旋转方向也不固定。比如左面那个图，圆内较大的一块竟有3条边，且左边不转，下边和右边都是右转。然而很不幸，题目问的恰恰就是圆内的块数。我们必须另辟蹊径。<br>
　　刚才讨论直线的情况时，我们没有充分利用内边的信息。其实，内边的条数与蛋糕被切成的块数也是有直接关系的。如果一块蛋糕有n个内边，那么它的切口就有n+1个，如下方较大的一块有1个内边，它的两个切口是AB和EF。而与这两个切口相连的上方的块一定不同！这暗示我们，直线一边的内边的数目，与<b>另一边</b>的蛋糕块数有某种联系！我们从原始的情况来想。首先想象一块蛋糕被直线一分为二。然后，蛋糕的上方收缩，整个蛋糕成为“凹”字形，直线恰好经过它的两条“腿”。这时，直线下方多了一条内边，上边多了一块蛋糕。于是我们发现了，直线上方的蛋糕块数等于下方内边数加1，下方的蛋糕块数等于上方内边数加1。这个算法也适用于求圆内的蛋糕块数，因为圆外蛋糕的内边同样具有“右转”的特征。还是看一下左边的图，由于圆外上方的那一块有一条内边（点8附近），故圆内的蛋糕块数为2。<br>
　　剩下的问题就是判断线段是否与直线相交、线段是否进入圆或从圆中出来的几何问题了。相信这些你都会的:)
<script>detail 1166,"背包问题"</script>
　　把能取得的若干连续重量用区间存储，比如重量3,4,5可用区间[3,6)表示。阅读下文，你将体会到用半开半闭区间与用闭区间相比的优越性。<br>
　　开始时解集中只有一个区间[0,1)。然后处理每一个物体。设当前处理的物体重量为w，那么把原来解集A中的每个区间都向右平移w得到一个集合B，合并A和B得到新的解集。合并时选用归并排序，这样可使原解集与新解集都保持有序性。当即将加入新解集的区间[c,d)与新解集最后一个区间[a,b)重叠或恰好相连（其充要条件为c<=b）时，将两区间合并为一个区间。这里体现了半开半闭区间的优越性之一：若用闭区间，则条件为c<=b+1，浪费一次加法运算。当所有物体都处理完毕后，累加每个区间中整数的数目。这里体现了半开半闭区间的另一点优越性：半开半闭区间[a,b)中的整数个数为b-a，而闭区间[a,b]中的整数个数为b-a+1，相比之下，半开半闭区间又节省了一次加法运算。因总重量不能为0，故答案为累加和减1。<br>
　　思路已经有了，在具体实现时又遇到这样一个问题：在某一时刻区间最多会有多少呢？理论上讲，若物体数为n，则总重量数为2<sup>n</sup>（包括0），在最坏情况下，这些重量都不连续，就需要2<sup>n</sup>个区间。但在最大规模随机数据的情况下，实验得知区间数一般不超过200000个，因此题目所给的内存是足够的。<br>
　　以上算法还有一点值得优化。这道题不能使用<a href=vol1.htm#1017>1017</a>题那样的朴素算法，原因就在于重量数太多，而区间恰恰解决了这一矛盾。为了让区间的优势发挥得更充分，我们在执行上述算法之前先对所有物体的重量进行一次排序，然后从小到大依次处理。这样，在计算过程中，重量就会最大程度地向轻的方向聚集，区间也会最大程度地合并，时间、空间需求都大大降低：未经优化的算法用时6.9s，而优化后的算法仅用2.3s；实验发现，在输入最大规模的随机数据时，优化后的算法在运行过程中区间的最大数目仅为几十至几百个，远远小于优化前的十万个左右。但是，当物体个数比较少而重量又很分散的情况下，区间数接近物体数的指数函数，如物体数为18，最大重量为100000的情况下，最大区间数仍可超过100000，因此建议仍把最大区间数定在200000左右。
<script>detail 1167,"城墙防御"</script>
　　这道题的算法是O(n*m)的DP。显然可以用列数作阶段。状态需要好好设计：用2*m表示最后一列属于第m个凹口（第0个凹口定义为最左边的空白），用2*m+1表示最后一列左边已经有了m个凹口，而这一列本身是凸出的。用f[n,m]表示阶段n状态m时的最大适用度和，则显然有
  <blockquote>
    f[n,m]=min{f[n-1,m-1],f[n-1,m]}+a[i]+b[i],当m为奇数<br>
    f[n,m]=min{f[n-1,m-1],f[n-1,m]}+b[i],当m为偶数<br>
  </blockquote>
　　其中，a[i]表示第1行第i列土地的适用度，b[i]表示第2行第i列土地的适用度。若某个f[n,m]对应不可能情况，则其值为负无穷大。f[n-1,m-1]表示最后一列与倒数第二列高度不同的情况，f[n-1,m]表示这两列高度相同的情况。<br>
　　算法不难，但编程上需要在细节上下功夫，尽可能地优化常数系数。下面我将对照程序，说明怎样尽可能缩短运行时间：
    <img align=right src=img_vol2/1167_1.gif>
  <ol><li>a[i]、b[i]这两个值需要经常用到，因此需对其进行预处理。注意到在状态转移方程中，是加a[i]+b[i]还是加b[i]与m的奇偶有关，于是用a[true,i]表示原来的a[i]+b[i]，用a[false,i]表示原来的b[i]，这样在j循环中就可以减少一次判断了。
  <li>显然f[n,*]只与f[n-1,*]有关，因此f应做成滚动数组f[boolean,0..maxm]（此处的maxm应为题目中的maxm*2+1）。因为在j循环中要屡次访问f[odd(i),*]和f[not odd(i),*]，因此用b1、b2两个布尔变量暂存odd(i)和not odd(i)的值，以减少odd函数的调用次数。
  <li>DP算法的一个特点是它计算的信息量很大，而算出来的信息往往有一部分是没有用的。如右图，整个矩形表示本题中DP计算的总信息量，而其中只有蓝色部分是有用的，这部分还占不上总信息量的一半。因此有必要仅计算蓝色部分所代表的信息，这就是j循环前计算的k、l的用途。这一操作可以显著提高程序效率。
  <li>继续观察状态转移方程。方程中有求较小值这一步，用程序中的方法做而不另外设一个临时变量，既可以省一个变量，在某些情况下还可以省去一次赋值。这样做导致了j循环必须用downto而不能用to，请仔细思考一下为什么。
  <li>再介绍一个好东西：{$R-}，即关闭range check。在保证程序不会发生数组越界等错误时，range check是既多余又耗时的。加上这一编译开关后，程序的运行时间缩短了一半以上，提交后用2.3s AC（虽然这个速度仍不是很快）。P.S.其实还有一个编译开关{$Q-}，即关闭overflow check，也能提高程序速度。</ol>
<script>detail 1169,"广告印刷"</script>
　　显然当广告面积最大时，要有一个建筑物被刷满。枚举这个建筑物的编号，然后寻找把这个建筑物刷满的广告向左、向右最远分别能延伸到什么位置。<br>
　　用l[i]、r[i]分别表示建筑物i被刷满时广告向左、向右最远能延伸到的位置。从左到右依次计算每个l[i]：初始时令l[i]=i，然后while h[i]<=h[l[i]-1] do l[i]:=l[l[i]]（h[i]表示第i个建筑物的高度）。r[i]的计算方法类似，只是方向为从右向左。为计算方便可令h[0]=h[n+1]=0。答案就是所有h[i]*(r[i]-l[i]+1)中的最大值。<br>
　　由于上述的while循环类似于并查集中的路径压缩，故本算法的复杂度可近似认为是O(n)，只是常数系数较大些。<p>
　　P.S.我在竞赛时，看到n的最大值是1000000，就不自觉地想O(nlogn)复杂度的算法，像静态排序二叉树，像堆，等等等等……花了两个小时，编了五个程序，换来一个TLE:(<br>
　　后来想到这个算法，5分钟编完程，2.2s AC。当时，我觉得这个算法就是O(n)的，看到用时这么长，感觉很奇怪。后来证明复杂度为O(n)时遇到了困难，才发现还有个常数系数在捣鬼。