vol3.htm

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

  <SCRIPT>detail 1255,"RAR or ZIP"</SCRIPT>
   
  　　由于给出了排序后方阵的最右一列，我们把这些字母排序（桶排即可）后自然可以得出方阵的最左一列。显然，方阵每一行的最后一个字母与第一个字母在原文中是相邻的（如果认为原文中最后一个字母与第一个字母也相邻的话）。我们自然产生了一种美好的设想：根据第一个字母就可以找到第二个字母，再根据第二个字母找到第三个字母……就这样按图索骥，就可以恢复出原文了！<BR>　　对样例进行试验，成功。但这样做没有问题吗？有！看totoro这个单词：<BR>
  <TABLE align=center>
    <TBODY>
    <TR>
      <TD align=middle><FONT 
        color=blue>构造字符串：</FONT><BR>totoro<BR>otorot<BR>toroto<BR>orotot<BR>rototo<BR>ototor 

      <TD align=middle><FONT 
        color=blue>将字符串排序：</FONT><BR>otorot<BR>orotot<BR>ototor<BR>rototo<BR>totoro<BR>toroto 

      <TD><FONT color=blue>压缩结果：</FONT><BR>S'=ttrooo<BR>p=1 
  </TD></TR></TBODY></TABLE>　　因为第一个字母是第一行末尾的t，所以第二个字母是o。但是，这个o是第四行末尾的o，还是第五行或者第六行末尾的o？这个问题难以解决，因为三个o在最右一列中的顺序是由<B>它们的下一个字母</B>决定的，而下一个字母并不已知。因此上述算法对重复字母无能为力。<BR>　　让我们来一下逆向思维：顺推不行，逆推行吗？答案是肯定的。所谓逆推，就是指当我们知道原文中某个字母在方阵中某一行的开头时，这一行末尾的字母就是原文中当前字母的上一个字母（把原文中最后一个字母看作第一个字母的上一个字母）。还以totoro为例：第一个字母是t。由于最左一列中相同字母是按<B>它们本身</B>在原文中的位置排列的，因此这个t必定是最左一列中最上面的t，即第五行的t。因此原文的最后一个字母是o。这个o自然应该是最左一列中最下面的o，即第三行的o。所以原文第五个字母是r，第四个字母是o，这个o在方阵中位于第二行第一列……哈，问题圆满解决。由于排序时运用了桶排，所以复杂度仅为O(n)。
  <SCRIPT>detail 1256,"奇怪的电梯"</SCRIPT>
   　　宽搜求最短路。
  <SCRIPT>detail 1257,"铸铁模具"</SCRIPT>
   
  　　开一个大小与模具相等的数组，存储每个位置被挖去的深度。然后一步一步地模拟刀片的运动，刀片每到一个在模具范围内的位置，就检查一下刀片的深度是否大于已挖去的深度。<BR>　　输入中的中括号是完全没有用的。本题的一个模块是读入数字。由于分号的结束符作用，我们不必开设缓冲区存储数字后的下一个字符。哈哈，知道Pascal中为什么每条语句后面都要有分号了:)
  <SCRIPT>detail 1258,"九数码问题"</SCRIPT>
   
  　　由目标状态开始，逆用移动规则，用BFS求出变换到每个状态所需的步数，然后问哪个状态就答哪个好了。为了存储每个状态的步数，需要给每个状态编一个号。我们不妨把0至8这九个数的所有排列按字典序排序，然后从0开始编号。求一个排列的编号可以如下进行：（为简便起见，以五个数的排列24103为例）<BR>　　2 
  4 1 0 3 //第一个数比2小的5个数的排列共有2*4!=24个<BR>　　　3 1 0 2 
  //把2去掉，剩下的数中比2大的都减小1，就成了一个0~3的排列。第一个数比3小的4个数的排列共有3*3!=18个<BR>　　　　1 0 2 
  //第一个数比1小的3个数的排列共有1*2!=2个<BR>　　　　　0 1 
  //第一个数比0小的2个数的排列共有0*1!=0个<BR>　　所以，排列24103的编号为24+18+2+0=44。
  <P>　　另外献上一点温馨提示：UNSOLVABLE的布局是不存在的。
  <SCRIPT>detail 1261,"数列拆分"</SCRIPT>
   
  　　本题没有什么统一的公式，所以还是要老老实实地分情况讨论。<BR>　　首先枚举项数n。项数的最小值为3。那么最大值呢？我们来看极端情况：各项和一定时，欲使项数尽可能大，应使每项尽可能小。那么数列就应该是1,2,3……因此，若设各项和为n，应有n*(n+1)/2=s。把n=sqrt(s*2)代入，左边大于右边，因此方程的正根小于sqrt(s*2)，故可用trunc(sqrt(s*2))作为n的最大值。<BR>　　在项数确定了的情况下，我们可以求出数列每项的平均数m=s*2/n以及最大的公差d=trunc((m-1)/((n-1)/2))（公差最大时首项为1，且m与1的差是(n-1)/2个公差）。下面还要对n分奇偶讨论： 

  <UL>
    <LI>当n为奇数时，m就是数列的中间一项，故m必须为整数。这时，满足条件的数列个数为d。 
    <LI>当n为偶数时，m为数列中间两项的平均值，它可以是整数，也可以是整数点五的形式。 
    <UL>
      <LI>若m是整数，则公差必为偶数。此时满足条件的数列个数为d div 2。 
      <LI>若m是整数点五，则公差必为奇数。此时满足条件数列个数为(d+1) div 2。</LI></UL></LI></UL>
  <SCRIPT>detail 1262,"空间站"</SCRIPT>
  　　本题我做得很麻烦，应该有优化的余地。
  <P>　　此题的模型就是：给定一棵带权无根树，求把它的任一条边的权改为0后，树中的最长路的最小长度。<BR>　　10<SUP>5</SUP>的数据规模启示我们使用DP算法。为了DP方便，我们以1号顶点为根，把无根树转化为有根树。我对每个顶点x定义了如下函数（哇，好多啊@:(）： 

  <UL>
    <LI>down1[x],down2[x],down3[x]：在以x为根的子树中，从x出发的最长路长度、次长路长度、第三长路长度。要求这三条路无公共边。 

    <LI>below[x]：在以x为根的子树中的最长路长度。注意这条最长路不一定经过x。 
    <LI>cbelow1[x],cbelow2[x]：x的孩子的below值中最大的一个和次大的一个。 
    <LI>up[x]：在原树中去掉以x为根的子树（但保留x结点）后，从x出发的最长路长度。 
    <LI>above[x]：在原树中去掉以x为根的子树及x与它父亲结点之间的边后，剩余部分的最长路长度。</LI></UL>　　上述所有函数在所对应的路径不存在时值均为0。<BR>　　DP总共进行两次。第一次自底向上进行，求出每个顶点的down1,down2,down3,below,cbelow1和cbelow2函数值；第二次自顶向下进行，求出每个顶点的up和above函数值，顺便算出答案。<BR>　　在第一次DP中，当处理到顶点x时，可以按如下方法求出x的一些函数值： 

  <UL>
    <LI>对于x的每一个孩子y，求出x,y之间边的长度与down1[y]之和。这些和中最大的三个就是<FONT 
    color=blue>down1[x],down2[x]和down3[x]</FONT>。 
    <LI>由于DP是自底向上进行的，x的所有孩子的below值中最大的两个就是<FONT 
    color=blue>cbelow1[x]和cbelow2[x]</FONT>。 
    <LI><FONT 
    color=blue>below[x]</FONT>为cbelow1[x]与down1[x]+down2[x]中的较大值。前者表示以x为根的子树中的最长路不经过x，后者表示经过x。</LI></UL>　　第二次DP则是这样：当处理到顶点x和它的孩子y时，可以按如下方法求出y的一些函数值： 

  <UL>
    <LI>求<FONT color=blue>up[y]</FONT>。up[y]对应的路径的第一条边必然是(x,y)（长度记为L），然后有两种可能：
    <UL>
      <LI>一种是继续往上走，这时up[y]=L+up[x]；
      <LI>还有一种是往下走。如果往下走，则不可以沿着(x,y)再回来，于是若down1[x]=L+down1[y]，则up[y]应等于L+down2[x]，否则就等于L+down1[x]。</LI></UL>
    <LI>求<FONT color=blue>above[y]</FONT>。有两种情况：
    <UL>
      <LI>一种情况是above[y]对应的路径不经过x。这时，它的长度可能是above[x]，也可能是cbelow1[x]（当cbelow1[x]&lt;&gt;below[y]时）或cbelow2[x]（当cbelow1[x]=below[y]时）。
      <LI>另一种情况是above[y]对应的路径经过x。这时，可以把由x出发的最长的两条路连起来。候选的路径长度有：up[x],down1[x],down2[x]。当然，如果down1[x]或down2[x]中有一个等于L+down1[y]，那么它就没有资格了，而用down3[x]来替代。取候选路长中的最大值和次大值相加，即得above[y]。</LI></UL>
    <LI>求<FONT color=blue>把(x,y)的权修改为0后整棵树中的最长路长度</FONT>。有三种情况：
    <OL>
      <LI>这条路经过(x,y)，这时路长为up[y]-L+down1[y]（注意up[y]-L不可以用up[x]代替，因为从x开始可以往下走）；
      <LI>这条路在(x,y)上方，这时路长为above[y]；
      <LI>这条路在(x,y)下方，这时路长为below[y]。</LI></OL>取这三者中的最大值，若这个最大值比当前最优解小，则更新最优解。</LI></UL>
  <SCRIPT>detail 1264,"河床"</SCRIPT>
  　　从左到右扫描，依次把每个深度加入“当前段”中。当“当前段”中的最大值与最小值的差超过限制时，就在“当前段”开头截去尽可能短的一段，使最大值与最小值的差重新满足要求。那么，本题的关键就在于在最大值（或最小值）被截去后，如何快速地找到新的最大值（或最小值）。<BR>　　用线段树等树形结构，可以轻松地在1M内存以内解决问题，但它的时间复杂度为O(nlogd)，经测试，运行完所有数据需要将近2s。而实际上本题的内存限制是很松的。所以我们采用时空复杂度均为O(n)的队列解决本题。<BR>　　开两个队列，一个叫做<B>大队</B>，一个叫做<B>小队</B>。如果一个深度满足它是从它所在位置到“当前段”末尾的最大值（最小值），那么它就属于大队（小队）。另外附加一条规则：如果大队或小队中有若干个深度相同，那么仅保留位置最靠前的那一个。容易看出，大队中深度是递减的，小队中的深度是递增的。<BR>　　当“当前段”向右延伸一个位置的时候，就把这个新的深度加到两个队列末尾。这时，大队或小队的单调性可能被破坏。如果发生了这种情况，就把单调性被破坏的队列的倒数第二个元素删除，直至单调性重新成立为止。现在检查一下“当前段”是否满足要求。若大队队首元素（就是“当前段”中的最大深度）与“当前段”尾的深度之差超过限制，那么就不断地删除大队队首元素直至满足要求，同时把“当前段”首指针移到最后删除的那个深度所在位置的下一个位置。若小队队首元素与“当前段”尾的深度之差超过限制，则可用类似的办法进行处理。计算“当前段”的长度，与最优解比较。
  <SCRIPT>detail 1265,"批次计划管理"</SCRIPT>
   　　DP，并用斜率优化法优化到O(n)。有关斜率优化法的原理请参看<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1171">1171</A>，在此只对本题进行数学推导。
  <P>　　逆推。用T[i]表示第i项工作以后的工作所需的总时间，F[i]表示第i项工作以后的工作的总处理成本因素。设<B>从0时间开始</B>做第i项工作以后的工作所需的总成本为cost[i]，则有状态转移方程：<BR>　　cost[n]=0<BR>　　cost[i]=min{(S+T[i]-T[j])*F[i]+cost[j]}(i&lt;j&lt;=n)<BR>　　cost[0]为所求。
  <P>　　决策a比决策b优(a&gt;b)的充要条件是：<BR>　　　　(S+T[i]-T[a])*F[i]+cost[a]&lt;(S+T[i]-T[b])*F[i]+cost[b]<BR>　　&lt;=&gt; 
  cost[a]-cost[b]&lt;(T[a]-T[b])*F[i]<BR>　　&lt;=&gt; 
  (cost[a]-cost[b])/(T[a]-T[b])&gt;F[i] (∵T[a]&lt;T[b])
  <P>　　定义(cost[a]-cost[b])/(T[a]-T[b])为决策a、b间的<B>斜率</B>。维护一个决策队列，使它满足相邻元素间的斜率递增。当阶段为i时，先将决策i+1加入队尾，通过不断删除队列倒数第二个元素来维护它斜率的单调性。然后若队首两元素间的斜率小于F[i]，则说明队首决策现在不是、将来也不会是最优决策，故将其删除。当队首两元素间斜率大于等于F[i]时，队首元素就是当前的最优决策了。
  <SCRIPT>detail 1266,"最小生成树"</SCRIPT>
   
  　　下文中，把输入的图称作G，选定的生成树称作S，S中的边叫做<B>树边</B>，其余的边叫做<B>非树边</B>。<BR>　　为什么要修改某些边的权值呢？这是因为，把一条非树边Y加入S后，S中会出现一个环，而这个环上的某一条树边X的权值(w[X])可能比Y的权值(w[Y])大。为了使S成为最小生成树，就必须减小X的权值，增大Y的权值，以使w[X]&lt;=W[Y]。如果把w[X]的变化量（当然是减小量）记作d[X]，把w[Y]的变化量（当然是增加量）记作d[Y]，那么我们可以列出不等式：w[X]-d[X]&lt;=w[Y]+d[Y]，即d[X]+d[Y]&gt;=w[X]+w[Y]。<BR>　　对于什么样的边对(X,Y)，需要列这样的不等式呢？这样的边需要满足的条件是：把Y加入S后，X在形成的环上。也就是说，X在S中Y的两个顶点间的路径上。对于任一条非树边Y，为了找出需要与它列不等式的所有树边X，我们需要把S看成一棵有根树，求出Y的两个端点u、v的最近公共祖先a。分别从u和v向上走到a，对路上满足w[X]&gt;w[Y]的边X都列出一个不等式。这一步求最近公共祖先，由于数据规模很小，朴素算法就可以，当然也可以用效率更高的Tarjan算法，详见<A 
  href="http://purety.jp/akisame/oi/TJU/vol1.htm#1068">1068</A>题。<BR>　　现在我们得到了一个不等式组，我们需要求出使所有变化量之和最小的一组解。观察这组不等式，发现它们与求<B>二分图最大权匹配</B>（参见<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1148">1148</A>题）时顶标所满足的条件形式完全相同。而求出最大权匹配后，顶标之和确实达到了最小。因此我们建立一个二分图B，把每条树边看成一个X顶点，每条非树边看成一个Y点。如果一个X点与一个Y点之间列了不等式，那么B中它们之间的边权就是不等式的右边，即它们在G中的权值之差；如果没有列，那么B中它们之间的边权为0。如果X点数与Y点数不相等，则补齐，并让它与所有异种点之间的边权全为0。然后用KM算法求出B的最大权匹配，这时匹配边的总权值（也就是所有顶点的顶标和）就是最小代价。同时，我们还求出了一种修改权值的方案：每个点的顶标就是它对应的G中的边的权值的变化量。<BR>　　其实，上面“补齐”的顶点若是X顶点（一般情况下非树边比树边多得多），则它们根本不必考虑，因为它们即使匹配上了，对权和的贡献也只是0。因此，匹配完原有的X顶点就可以停止了。
  <P>　　长郡中学的王俊提出了一种更简单的算法。他把求最大权匹配的问题转化为求最大匹配。他的思路是：题目中只要求求出最小代价，并没有要求求出修改方案，因此把边上的权值转移到点上。他建立了一个新的二分图B'，以所有的树边为X顶点，所有边（包括树边与非树边）为Y顶点。X顶点及边均无权值，Y顶点的权值为G中的边权。B'中的边是这样连的：B中每一条权不为0的边在B'中都有对应的边，另外每个代表树边的Y顶点都与代表同一树边的X顶点之间连一条边。这样做以后，B的完备匹配与B'的最大匹配之间就建立了一一对应的关系，且对应的两个匹配的权和之和为原图中所有树边的权值之和： 

  <UL>
    <LI>如果B的匹配中与某个X顶点相连的边权为0，那么B'中这个X顶点就匹配与自己代表同一树边的Y顶点。B中这条边的权值为0，B'中这条边的权值为这个顶点代表的树边本身的权值，其和为树边本身的权值。 

    <LI>如果B的匹配中与某个X顶点相连的边权不为0，那么B'中这个X顶点仍匹配B中X匹配的Y顶点。B中这条边的权值为w[X]-w[Y]，B'中这条边的权值为w[Y]，和仍为w[X]，即树边的权值。</LI></UL>　　因此，B和B'中对应匹配的权和之和为原图中所有树边的权值之和。欲求B的最大权匹配，只需求B'的最小权最大匹配。而G'的权值都在Y顶点上，因此把所有Y顶点按权值递增的顺序排序，依次匹配即可。<BR>　　（注：我的程序用的是王俊的算法，但X顶点和Y顶点被交换了过来。）
  <SCRIPT>detail 1267,"小店购物"</SCRIPT>