tongji online judge solutions b.htm

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

<P>　　<FONT 
color=blue><B>结论2：不可达的顶点至多只有一个。</B></FONT><BR>　　<B>证明：</B>由结论1易知，与顶点1的距离（到顶点1的最短路长度）大于1的所有顶点皆可达。对于顶点1本身和与顶点1直接相连的顶点，分以下几种情况讨论： 

<TABLE cellSpacing=0 width="73%" align=center>
  <TBODY>
  <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：以上路径经过的顶点数均&gt;=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：以上路径经过的顶点数均&gt;=3 
  </TR></TBODY></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&lt;=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="Tongji Online Judge Solutions B.files/1141_1.gif">
<P>其中H为重组合的符号，<IMG 
src="Tongji Online Judge Solutions B.files/1141_2.gif">表示从n个元素中可重复地取出m个的组合数，<IMG 
src="Tongji Online Judge Solutions B.files/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 cellSpacing=0 align=center>
  <TBODY>
  <TR>
    <TH>试探顺序
    <TH>运行时间 
  <TR>
    <TD align=middle>升序
    <TD>1.970s~1.987s 
  <TR>
    <TD align=middle>降序
    <TD>0.011s~0.016s 
  <TR>
    <TD align=middle>随机序
    <TD>1.026s~1.042s 
</TR></TBODY></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&gt;=n了，说明第二个字母就是B，否则继续累加以AC开头的单词的个数……直到s&gt;=n，这样第二个字母就确定了。将最后一次累加的数减去，用类似的方法确定第三、第四……个字母，直至结束。<BR>　　现在的问题是：如何求出以某给定序列开头的单词的个数？这个问题是用记忆化搜索解决的。用f[a,b,c,d,e](5&gt;=a&gt;=b&gt;=c&gt;=d&gt;=e&gt;=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值已经算出，则不必再递归下去，直接退出即可。</LI></UL>　　因为每次计算单词个数时给定的序列都不同，所以每次都必须从头递归。
<P>　　程序的实现用了一点小技巧。上文中说，B的合法位置有两个，分别是12和21。但实际上，12这个位置已经被字母C占据，只是在第二次递归时程序并不知道这一点。请看程序第26行中的这一条件：len[x[c]]+1=y[c]。如果某个位置已固定的字母的位置已被别的字母占据，那么这个条件就为假，从而求出的单词数就成了0。当然，可以在递归之前把已被占据的位置做上标记，但因为需要搜索的状态总数本来就不多（只有252种），做标记不会显著提高时间效率，反而会增加编程复杂度。<BR>　　除上段所说的以外，还有几点可以优化的地方，如以ACB开头的单词数可不经搜索直接得到0，再如当递归深度超过了所有已固定的字母时，可直接利用<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#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&gt;=a&gt;=b&gt;=c&gt;=d&gt;=e&gt;=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>若为编码转单词，则依次枚举每个字母可能的位置并累加这时产生的单词数。若某时刻累加和超过或等于了编码，则当前处理的字母应放的位置就找到了，减去最后一次累加的数值，继续处理下一个字母，直至结束。</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;