vol2.htm

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

　　=xR(<img src=img_vol2/1133_3.gif>)+R(<img src=img_vol2/1133_2.gif>) （此步选定的是左上方的格子）<br>
　　=x(xR( )+R( ))+xR( )+R(<img src=img_vol2/1133_3.gif>)<br>
　　=x(x+1)+x+x+1<br>
　　=x<sup>2</sup>+3x+1<p>
　　<font color=blue><b>棋盘多项式要怎么用？</b></font><br>
　　想象一个n*n的棋盘，输入中的1是棋盘的禁区。设禁区的棋盘多项式的i次项的系数为f<sub>i</sub>。在整个棋盘上放置n个棋子，至少有i个落入禁区的方法数为f<sub>i</sub>*(n-1)!。由容斥原理，在整个棋盘上放置n个棋子，无一落入禁区的方法数为<img align=middle src=img_vol2/1133_4.gif>。因此计算出禁区的棋盘多项式，问题就解决了。当然，需要用高精度。<p>
　　<font color=blue><b>复杂度问题！</b></font><br>
　　在计算有n个格子禁区的棋盘多项式的过程中，总共要计算多少个棋盘的棋盘多项式呢？感觉是2<sup>n</sup>个。这个复杂度无论是时间上还是空间上都是无法承受的。怎么办呢？其实什么也不用办，因为实际上计算的棋盘数不会超过2<sup>n/2+1</sup>。如果计算棋盘多项式时，每次都选定最上面一行的最左面一格，则这个上限会在棋盘上每列都有至少2个格子，且列与列之间没有格子同行，且对于任意两列a、b，a的最高格总是高于b的次高格时达到。假设棋盘共有m列，则在需计算的棋盘中，若第x列的最高格已经不存在了，则第1至x-1列的最高格必然也不存在了。故第1列的最高格存在的棋盘只有1（即2<sup>0</sup>）个，第1列的最高格不存在而第2列的最高格存在的棋盘有2<sup>1</sup>个（因为第1列除去最高格后的部分有存在与不存在两种可能），前2列的最高格不存在而第3列的最高格存在的棋盘有2<sup>2</sup>个（前2列除去最高格后的部分都可能存在或不存在）……m列的最高格都不存在的棋盘有2<sup>m</sup>个。也就是说，棋盘总数的上限大约为2<sup>m+1</sup>。因为对这种棋盘有m<=n/2，故实际计算的棋盘数不会超过2<sup>n/2+1</sup>。在n<=25时，这个复杂度在时间上是完全可以承受的，在空间上，若给每个棋盘编一个号，使用哈希表存储棋盘多项式，也没有问题。<p>
　　本题使用了高精度、二进制编号、哈希表等多种算法和数据结构，对编程能力也是一个极好的锻炼。
<script>detail 1136,"回家"</script>
　　把边当作点，点当作边，Dijkstra即可。
<script>detail 1137,"赌场的规矩"</script>
　　很明显，这是一道图论题。首先构造一个图：每一个洞作为一个顶点，在某两个洞之间交换了几次，就在代表这两个洞的顶点之间连几条边。把最后可能藏有小球的洞对应的顶点叫做<b>可达</b>的顶点，其它顶点叫做<b>不可达</b>顶点。显然，可达顶点只存在于包含顶点1的连通分支中。以下的讨论都是针对包含1号顶点的连通分支。<br>
　　现在提出两个结论：<p>
　　<font color=blue><b>结论1：若顶点1到顶点x有一条经过3个或3个以上顶点的路径，则顶点x是可达的。</b></font><br>
　　<b>证明：</b>如果依次进行路径上的边所代表的操作，则显然小球最后会在x号洞里。我们只需让不在这条路径上的边（以下称作“多余边”）代表的操作全部成为空操作即可。<br>
　　而这一点是很容易做到的。以路径上有且只有3个顶点的情况为例。把这3个顶点分别记作A、B、C。当小球在A洞里时，可以进行B、C之间多余的边（如果有的话）所代表的操作，这时，这些操作全部为空操作。同理，当小球在B洞里时，可以使A、C之间的多余操作成为空操作；当小球在C洞里时，可以使A、B之间的多余操作成为空操作。与A相连但不与B、C相连的多余边所代表的操作可以在小球不在A洞时进行，只与B或C相连的多余边可同理处理。与A、B、C均不相连的多余边，则可以在任意时刻处理掉。证毕。<p>
　　<font color=blue><b>结论2：不可达的顶点至多只有一个。</b></font><br>
　　<b>证明：</b>由结论1易知，与顶点1的距离（到顶点1的最短路长度）大于1的所有顶点皆可达。对于顶点1本身和与顶点1直接相连的顶点，分以下几种情况讨论：
  <table align=center cellspacing=0 width=73%>
    <tr><td width=73%>if 顶点1为孤立顶点 then<td>&nbsp
    <tr><td>　不存在不可达的顶点<td>&nbsp
    <tr><td>else if 顶点1在某个环上 then<td>&nbsp
    <tr><td>　不存在不可达的顶点<td>//因为顶点1到环上的顶点必存在经过3个或更多顶点的路径，顶点1到环外的顶点总可以先走一遍环
    <tr><td>else if 与顶点1关联的边全部为单边 then<td>&nbsp
    <tr><td>　有且只有顶点1不可达<td>//因为一旦进行了与顶点1关联的操作，小球离开了1号洞，它就不可能再回来了
    <tr><td>else if 与顶点1关联的边中有一组重边（设这组重边连接的另一顶点为a） then<td>&nbsp
    <tr><td>　if 除重边(1,a)以外还有重边与顶点a关联 or 顶点a在某个环上 then<td>&nbsp
    <tr><td>　　不存在不可达的顶点<td>//顶点1到顶点a存在这样一条路径：先走重边(1,a)中的一条，再走a的另一组重边或环；顶点1到自身存在这样一条路径：先走重边(1,a)中的一条，再走a的另一组或环，再走重边(1,a)中的另一条；顶点1到与顶点1相连的其它任一顶点b存在路径1-a-1-b：以上路径经过的顶点数均>=3
    <tr><td>　else<td>&nbsp
    <tr><td>　　if (1,a)为奇重边 then 有且只有顶点1不可达 else 有且只有顶点a不可达<td>//顶点1到与顶点1相连的其它任一顶点b存在路径1-a-1-b；重边(1,a)中的所有边无法成为空操作，因为如果想让重边(1,a)中的某一条成为空操作，小球必须离开顶点1和顶点a，而走了就回不来了
    <tr><td>else if 与顶点1关联的边中有超过一组的重边（设顶点1与顶点a、b均以重边相连） then<td>&nbsp
    <tr><td>　不存在不可达的顶点<td>//顶点1到自身存在路径1-a-1-b-1；顶点1到顶点a存在路径1-b-1-a；顶点1到顶点b存在路径1-a-1-b；顶点1到与顶点1相连的其它任一顶点c存在路径1-a-1-c：以上路径经过的顶点数均>=3
  </table><p>
　　有了上面两个结论以及关于不可达顶点的详细分析，剩下的工作就是判断顶点1和与顶点1直接相连的顶点是否在环上了。这一点也不难。为了找到含顶点1的连通分支，我们需要以顶点1为根做一次“灌水法”。实现时用BFS，并记录从顶点1到每个顶点的路径上的第2、3个顶点（记作r1、r2）。若在BFS的过程中碰到一条连接两个已访问的顶点的边，则比较这两个顶点的r1和r2。若r1不同，则顶点1在环上，否则若r2不同，则相同的r1在环上。<br>
　　这种算法的核心只是一次灌水法，复杂度为O(n<sup>2</sup>)，题目所给的数据范围n<=20完全是小菜一碟了。
<script>detail 1138,"多项式乘法"</script>
　　依次把每项相乘，降幂排序，合并同类项即可。<br>
　　数据很弱，我是把每个式子的最大项数定为1000的。如果定为10000，则会MLE;)<br>
　　至于输入中的多余空格的问题，我是宁信其有不信其无。也就多加那么几条语句而已:)
<script>detail 1140,"烷烃命名之Step 1"</script>
　　显然这个题是求一棵树中的最长路。以顶点a为根的子树中的最长路长度=max{顶点a的所有子树中最长路长度最大值（最长路不经过a的情况）,顶点a的所有子树深度的最大值与次大值之和+1（最长路经过a的情况）}。注意到根结点有4棵子树，其余的C有各有3棵子树，H无子树，于是可用递归轻松解决问题。
<script>detail 1141,"统计一氯代烷同分异构体数目"</script>
　　还是DP。把连有Cl原子的C原子看作树根，那么它有3棵子树。设f[n]表示一氯n烷的同分异构体数目，则有状态转移方程<p align=center><img src=img_vol2/1141_1.gif><p>其中H为重组合的符号，<img src=img_vol2/1141_2.gif>表示从n个元素中可重复地取出m个的组合数，<img src=img_vol2/1141_3.gif>（用隔板原理想一下就会明白）。状态转移方程的第三项当且仅当n mod 3=1时存在。<br>
　　本题的结果不超过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本身没有被了望到所需的最少士兵数；