vol2.htm

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

　　本题的结果不超过qword范围，因此不必使用高精度。
<script>detail 1142,"虫食算"</script>
　　只用最简单的搜索方法即可：从右到左依次搜索每一列中的每一个字母代表的数字（这样可以充分利用进位的信息）。每假设出一个字母的值，就检查一下它左边的每一列是否可能成立。检查也很简单：如果一列的3个字母的值都已确定，那么判断一下它在进位和不进位两种情况下是否有可能成立；如果仅确定了两个字母，那么计算一下剩下的那个字母在进位和不进位两种情况下分别应取的值，如果这两个值都已被别的字母占用，则剪枝；在检查最左一列时，如果发现它向“第0位”进位了，也可以剪枝。<br>
　　为了避免试探字母取值时屡次碰到已用过的字母，除了用布尔数组used记录每个数字是否用过（检查时要用）外，还可以建立一个链表，其中存储当前尚未用过的数字。这样会在一定程度上提高程序的速度。<br>
　　但奇怪的是，对于某一个字母，按怎样的顺序试探它的值对程序效率有很大的影响。从2004年11月NOIP到2005年4月，我一直是按从0到n-1的升序试探的，最快的程序通过全部10个数据也需要2s左右的时间。借鉴了一下静默守护的程序，发现他是按0,n-1,1,n-2,2,n-3...的顺序试探的，速度比我的快得多。我又编了两个程序，分别用n-1到0的降序和随机序进行试探，发现降序的程序比静默守护的还快，随机序稍慢。下面是某电脑上我编的三个程序的运行时间比较：
  <table align=center cellspacing=0>
    <tr><th>试探顺序<th>运行时间
    <tr><td align=center>升序<td>1.970s~1.987s
    <tr><td align=center>降序<td>0.011s~0.016s
    <tr><td align=center>随机序<td>1.026s~1.042s
  </table>
　　现在我无法从理论上说明逆序和随机序哪个更优。我感觉，既然总搜索量是一定的，影响出解速度的因素只是解在搜索树中的位置，也就是说，无论哪种试探顺序，出解时间的期望都是一样的，只是本题的测试数据可能恰好适于降序试探。专门用来对付降序的测试数据也是可能存在的。所以，我比较提倡随机序。在压缩包中，我提供了升序(1142up.pas)、降序(1142down.pas)和随机序(1142rnd.pas)三个程序。
<script>detail 1143,"二五语言-版本2"</script>
　　以下叙述中，“单词”均指合法单词。<br>
　　举个例子说明：若为单词转编码，如求单词ACF……的编码，则设一累加器，先累加以AB开头的单词的个数，再累加以ACB开头的单词的个数（这个数为0，但若已知6个字母的位置，B拐到了第2行，则可能不为0），再累加以ACD开头的单词的个数，再累加以ACE开头的单词的个数……最后加1即得答案。若为编码转单词，如求第n个单词，同样设一累加器s，先累加以AB开头的单词的个数，若s>=n了，说明第二个字母就是B，否则继续累加以AC开头的单词的个数……直到s>=n，这样第二个字母就确定了。将最后一次累加的数减去，用类似的方法确定第三、第四……个字母，直至结束。<br>
　　现在的问题是：如何求出以某给定序列开头的单词的个数？这个问题是用记忆化搜索解决的。用f[a,b,c,d,e](5>=a>=b>=c>=d>=e>=0)表示把前a+b+c+d+e个字母填入第1行的前a个格，第2行的前b个格……第5行的前e个格，且已经确定位置的字母各就各位时可能的单词数，那么f[0,0,0,0,0]就表示以给定序列开头的单词数。下面以求以AC开头的单词数为例说明递归求f数组的方法：<br>
  <ul><li>第一层递归安置字母A。因其位置已固定，故f[0,0,0,0,0]=f[1,0,0,0,0]，进入第二层递归计算f[1,0,0,0,0]。
  <li>第二层递归安置字母B。B的位置尚未固定，于是枚举所有合法位置（合法位置指左、上方均已填有字母的位置，认为第0行与第0列均已填满。此例中为12、21），分别进入第三层递归计算f[2,0,0,0,0]（这个值等于0，下面会讨论其原因）与f[1,1,0,0,0]。f[1,0,0,0,0]即等于这二者之和。
  <li>第三层递归安置字母C。这层递归的过程与第一层递归类似。更深层递归的过程与第二层递归类似。若在某一次递归中，需要计算的f值已经算出，则不必再递归下去，直接退出即可。</ul>
　　因为每次计算单词个数时给定的序列都不同，所以每次都必须从头递归。<p>
　　程序的实现用了一点小技巧。上文中说，B的合法位置有两个，分别是12和21。但实际上，12这个位置已经被字母C占据，只是在第二次递归时程序并不知道这一点。请看程序第26行中的这一条件：len[x[c]]+1=y[c]。如果某个位置已固定的字母的位置已被别的字母占据，那么这个条件就为假，从而求出的单词数就成了0。当然，可以在递归之前把已被占据的位置做上标记，但因为需要搜索的状态总数本来就不多（只有252种），做标记不会显著提高时间效率，反而会增加编程复杂度。<br>
　　除上段所说的以外，还有几点可以优化的地方，如以ACB开头的单词数可不经搜索直接得到0，再如当递归深度超过了所有已固定的字母时，可直接利用<a href=#1144>版本1</a>中的DP获得结果，而不须递归下去。然而，不加这些优化的算法的复杂度已经很低了（最坏情况下为25(25个位置)*25(每个位置可能放25个字母)*252(记忆化搜索的状态总数)*5(每个状态最多有5个合法位置)=787500），这些优化都显得不太值得。
<script>detail 1144,"二五语言-版本1"</script>
　　以下叙述中，“单词”均指合法单词。<br>
　　用count[a,b,c,d,e](5>=a>=b>=c>=d>=e>=0)表示把前a+b+c+d+e个字母填入第1行的前a个格，第2行的前b个格……第5行的前e个格后，剩下字母的填法数。count数组可用DP计算，其思路为：如果某一行已填的字母数少于上一行已填的字母数（可认为第0行填了5个字母），那么第a+b+c+d+e+1个字母就可以填到这一行的下一个位置。具体实现可参考程序中的calcount过程。<br>
　　有了这个数组，解决问题就简单了：
  <ul><li>若为单词转编码，则依次处理每个字母，累加把它放在给定单词中它所在位置以前的所有合法位置（指左、上方均已填有字母的位置，认为第0行与第0列均已填满）可构造出的单词数，最后把结果加1。比如，若A,B,C三个字母分别放在11,21,31三个位置，则在处理B时，累加将其放在位置12时的单词数（即count[2,0,0,0,0]）；处理c时也累加将其放在位置12时的单词数（即count[2,1,0,0,0]），但不能累加把它放在位置22时的单词数（因为如果这样位置12的字母将大于位置22的字母，不合法）。
  <li>若为编码转单词，则依次枚举每个字母可能的位置并累加这时产生的单词数。若某时刻累加和超过或等于了编码，则当前处理的字母应放的位置就找到了，减去最后一次累加的数值，继续处理下一个字母，直至结束。</ul>
<script>detail 1145,"敲七-版本4"</script>
　　把与7有关的n位数分成两种：
  <ul><li><b>不含数字7，但是7的倍数的n位数</b>。用rem[d,r]表示不含数字7且除以7除r的d位数的个数。易写出如下伪代码：
    <pre>
      rem[0,0]:=1;for i:=1 to 6 do rem[0,i]:=0;
      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 align=absmiddle src=img_vol2/1145_1.gif>（其中i表示数字7的个数）。</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]<=t*m,这个j就是答案。<br>
　　f数组可做成滚动数组。这个算法的复杂度为O(n<sup>2</sup>)，绝不会超时。
<script>detail 1147,"战略游戏-版本2"</script>
　　同<a href=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结点上有士兵时所需的最少士兵数。</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]}之和。</ul></ul>
　　设根结点为root，则min{need[root,1],need[root,2]}就是答案。
<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 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>