tongji online judge solutions b.htm

同济大学 online 在线题库题目及解题报告完整版

      for d:=1 to n do
        for i:=0 to 6 do
          for j:=0 to 9 except 7 do //j表示第d位数
            inc(rem[d,(i*10+j) mod 7],rem[d-1,i]);</PRE>　　不含数字7，但是7的倍数n位数的个数就是rem[n,0]。 

  <LI><B>含数字7的n位数</B>。显然这一类数的总数为<IMG 
  src="Tongji Online Judge Solutions B.files/1145_1.gif" 
  align=absMiddle>（其中i表示数字7的个数）。</LI></UL>
<SCRIPT>detail 1146,"乐队（加强版）"</SCRIPT>
　　<B>首先把一盘CD装不下的歌全部踢掉！！！</B>
<P>　　剩下的工作就是DP了。用f[i,j]表示在前i首歌中选出j首在CD上占的最小时间。这里说的时间包括除最后一盘外的CD上浪费的时间。f[i,j]=min{f[i-1,j],sum(f[i-1,j-1],第i首歌的长度)}。这里的sum的含义是：如果最后一盘CD剩下的时间正好可以放下第i首歌，那么直接相加即可，否则要再加上最后一盘CD剩下的时间（这些时间已被浪费了）。找一个最大的j使f[n,j]&lt;=t*m,这个j就是答案。<BR>　　f数组可做成滚动数组。这个算法的复杂度为O(n<SUP>2</SUP>)，绝不会超时。
<SCRIPT>detail 1147,"战略游戏-版本2"</SCRIPT>
 　　同<A 
href="http://purety.jp/akisame/oi/TJU/vol1.htm#1041">版本1</A>一样，本题也可以用树型DP来解。但本题的状态设计比版本1要复杂一些。具体来说，有以下三个状态： 

<UL>
  <LI>need[n,0]：表示以n为根的子树中，除n以外的结点全被了望到，而只有n本身没有被了望到所需的最少士兵数； 
  <LI>need[n,1]：表示以n为根的子树中的全部结点都被了望到，但n结点上没有士兵时所需的最少士兵数； 
  <LI>need[n,2]：表示以n为根的子树中的全部结点都被了望到，且n结点上有士兵时所需的最少士兵数。</LI></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]&lt;need[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。</LI></UL></LI></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]&gt;=w[i,j]始终成立。KM算法的正确性基于以下定理：<BR>　　<B>若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做<B>相等子图</B>）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。</B><BR>　　这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。<BR>　　初始时为了使A[i]+B[j]&gt;=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]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。</LI></UL>　　现在的问题就是求d值了。为了使A[i]+B[j]&gt;=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&lt;=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 src="Tongji Online Judge Solutions B.files/1165_1.gif" align=right><IMG 
src="Tongji Online Judge Solutions B.files/1165_2.gif" align=left> 
　　先讨论比较简单的直线的情况。若直线没有切着蛋糕，则答案显然。下面只讨论直线切着蛋糕的情况。观察一下右面这个图，图中直线的上方有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&lt;=b）时，将两区间合并为一个区间。这里体现了半开半闭区间的优越性之一：若用闭区间，则条件为c&lt;=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="http://purety.jp/akisame/oi/TJU/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 src="Tongji Online Judge Solutions B.files/1167_1.gif" align=right> 
<OL>