vol1.htm

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

prob "ac",1
prob "ac",1
prob "ac",0
prob "ac",0
prob "ac",0
prob "ac",1
</SCRIPT>
  </TR></TBODY></TABLE>
<SCRIPT>detail 1002,"全排序问题"</SCRIPT>
　　放心大胆地做吧，不会TLE:)
<SCRIPT>detail 1004,"防御导弹"</SCRIPT>
 
　　第一问即经典的最长不上升子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模好像不需要。<BR>　　高效算法是这样的：用a[x]表示原序列中第x个元素，b[x]表示长度为x的不上升子序列的最后一个元素的最大值，b数组初值为0。容易看出，这个数组是递减的（当然可能有相邻两个元素相等）。当处理a[x]时，用二分法查找它可以连接到长度最大为多少的不上升子序列后（即与部分b[x]比较）。假设可以连到长度最大为y的不上升子序列后，则b[y+1]:=max{b[y+1],a[x]}。最后，b数组被赋值的元素最大下标就是第一问的答案。由于利用了二分查找，这种算法的复杂度为O(nlogn)，优于一般的O(n<SUP>2</SUP>)。<BR>　　第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。<BR>　　<FONT 
color=red><B>注意：</B></FONT>第二问不可以用每次删除最长不上升序列的方法做。比如，当来袭的导弹共有4颗，高度依次为2 4 1 
3的时候，如果不巧找到的最长不上升序列为4 1，那么剩下的2和3就只能另外启用两套系统了。这显然不是最优解。
<SCRIPT>detail 1005,"母牛生小牛"</SCRIPT>
 　　用a[i]表示第i年牛的总数，则a[i]=a[i-1]+a[i-3]，即3年前所有的牛所生的小牛加上上一年所有的牛。
<SCRIPT>detail 1006,"敲七"</SCRIPT>
 　　挨个检查即可。
<SCRIPT>detail 1009,"蛇行矩阵"</SCRIPT>
 　　把三角形的下角拖到右面去，便可以编出连数组都不用的程序了:)
<SCRIPT>detail 1010,"数素数"</SCRIPT>
 
　　用筛法求素数即可。关键是怎么把求得的素数都保存下来。可以用1个字节保存8个二进制位，即8个数是否为素数。再用count[i]表示i*8以内素数的个数（前缀表示法）。求m到n之间素数个数时，除了用两个count值相减外（前缀表示法的常用技巧），还要注意处理一下m和n附近的素数。
<SCRIPT>detail 1011,"阶乘末尾非零数求和"</SCRIPT>
 　　在乘的过程中，我们只需保留最后一位非零数。这位数在n&gt;1时为偶数。当要乘的数中含有因数5时，我们可以把所有的因数5都当作8来乘，因为： 
<BLOCKQUOTE>...2*5=...10（舍）或...60，最后一位非零数为6。而恰好2*8=16，末位为6。<BR>...4*5=...70（舍）或...20，最后一位非零数为2。而恰好4*8=32，末位为2。<BR>...6*5=...30（舍）或...80，最后一位非零数为8。而恰好6*8=48，末位为8。<BR>...8*5=...90（舍）或...40，最后一位非零数为4。而恰好8*8=64，末位为4。 
</BLOCKQUOTE>
<SCRIPT>detail 1012,"约瑟夫问题"</SCRIPT>
　　用数组模拟链表即可。
<SCRIPT>detail 1013,"高精度整数去位取最小问题"</SCRIPT>
 
　　每一个保留的数字都从可取的范围中取最小的一位即可。用a[i]表示第i个保留的数字在原数中的位置，设a[0]=0，则a[i]的范围为a[i-1]+1~n-m+i。
<SCRIPT>detail 1014,"阶乘结果末尾有多少零？"</SCRIPT>
 　　借用化学术语说，“一个2跟一个5反应生成一个0，因为2过量，所以照5算”。n!末尾零的个数就是1~n这n个数中因数5的个数，即n div 5+n div 
5<SUP>2</SUP>+n div 5<SUP>3</SUP>...直到某项减少至0为止。
<SCRIPT>detail 1016,"请求N!左边第二位的数字"</SCRIPT>
 　　用实数乘，超过100就除以10，最后取个位即可。
<SCRIPT>detail 1017,"石子归并"</SCRIPT>
 
　　开一个最小下标为0，最大下标为最大总质量的一半(maxw)的布尔数组b，初始时仅b[0]为true。依次读入每一个石子的质量。设当前石子的质量为m，则对于原来的任一个值为true的b[i](0&lt;=i&lt;=maxw-m)，令b[i+m]为true。处理完每个石子后，设值为true的b值中最大下标为x，则x就是把石子按质量尽可能平均地分为两堆后较轻的那一堆的质量。
<SCRIPT>detail 1018,"编制一个乘法运算的程序"</SCRIPT>
 　　垃圾题。不要按照一般的乘法竖式输出，而要观察样例程序的输出，然后照葫芦画瓢……SPOJ上有一道Simple 
Arithmetics，比这个题好得多，推荐做一下。
<SCRIPT>detail 1021,"麻将游戏"</SCRIPT>
 
　　说是麻将游戏，其实就是连连看嘛。好像有不少人看不懂题意，可以Google一个连连看玩一下。<BR>　　这个题的解法就是简单BFS。从起点出发，每次扩展就是沿上下左右四个方向闯下去，直到碰到一张牌或边界为止。这里的“边界”应是原棋盘再往外的一圈，因为连线可以超出棋盘。如果碰到的牌正好是终点，那么BFS成功。<BR>　　另外还要注意，输出的应是路径上线段的条数，而不是拐的弯数。
<SCRIPT>detail 1022,"数制转换"</SCRIPT>
 
　　初学者的基础题，我就不讲算法了。要说的是题目叙述的第一行不应是“A$='mp'”，而应是“A$='m&lt;n&gt;p'”，&lt;n&gt;被当成HTML标签吃掉了。看一下样例你就不会迷茫了:)
<SCRIPT>detail 1024,"特殊三角形"</SCRIPT>
 　　这个题是TJU上一道极垃圾的题。虽然是Special Judge，但实际上能AC的只有按升序排列在最前面的那一个三角形。这样看来，连样例输出都是错的:(
<SCRIPT>detail 1025,"N*N的棋盘"</SCRIPT>
 　　深搜。为了加快速度，可以不用布尔数组记录一个数是否用过，而用数组模拟的链表。
<SCRIPT>detail 1026,"整除65的多项式"</SCRIPT>
 　　注意到k,a,x的范围其实都只是0~64，于是枚举即可。
<SCRIPT>detail 1027,"洗牌问题"</SCRIPT>
 
<UL>
  <LI><FONT 
  color=blue><B>Maigo的原始算法：</B></FONT><BR>　　我们把每个数逛来逛去最后又回家的过程叫做一个<B>循环</B>，循环中经过的位置个数叫做循环的<B>长度</B>。如N=4时，有两个循环：1-2-4-8-7-5-1，长度为6；3-6-3，长度为2。答案就是所有循环长度的最小公倍数。显然算法时空复杂度均为O(n)（因为需要记录一个数是否已被某个循环经过）。<BR>
  <LI><FONT 
  color=blue><B>Wasltone的高效算法：</B></FONT><BR>　　1所在的循环长度就是答案。时间复杂度小于O(n)，空间复杂度为O(1)，编程复杂度也远低于原始算法。这个算法是建立在如下结论之上的：“1所在的循环长度是其它任一循环长度的倍数”，或者表述为“1回家时，其它任一数字也一定回了家”。Wasltone本人没有给出这个结论的证明。 

  <LI><FONT 
  color=blue><B>Ahyangyi给出的证明：</B></FONT><BR>　　题目中的移动规则，其实就是每次把在第x个位置的数移动到位置x*2 
  mod (2*n+1)。这个式子是十分巧妙的，请用心领悟。由这个式子可以得出任一数字x在p步之后的位置：x*2<SUP>p</SUP> mod 
  (2*n+1)。假设1经过p步回了家，那么可得1*2<SUP>p</SUP> mod 
  (2*n+1)=1。由此可得对任一数字x，均有x*2<SUP>p</SUP> mod (2*n+1)=x，即1回家时任一数字都回了家。 </LI></UL>
<SCRIPT>detail 1029,"埃及分数"</SCRIPT>
　　本题若用BFS，则每个结点可扩展的子结点数会巨大，空间复杂度无法承受。因此采用DFS-ID，即先假设解的深度（单位分数的个数）为1，进行DFS，若不成功，再假设解的深度为2，DFS……直到找到解为止。<BR>　　DFS-ID解决了空间问题，但还有一个问题就是每个结点扩展子结点的范围，因为单位分数的分母没有限制，必须人为找一个限制条件。 

<UL>
  <LI>对于<B>非叶子结点</B>：当前待确定分母的最小值就是max{上一个分母加1，当前剩余分数的倒数的整数部分加1}。第2项之所以加1，是因为当前分母必须小于以后的分母。它的最大值则是min{当前剩余分数除以尚未确定的分数个数的商的倒数的整数部分，当前最优解的最后一个分母减1}。前一项可以这样理解：如果当前待确定分母大于这一项，那么以后的分母都会大于这一项，当前待确定的及以后的分数加起来肯定小于当前剩余分数。后一项则是显然的：如果当前分母都大于等于当前最优解的最大分母了，那么当前结点一定不会扩展出更优解。 

  <LI>对于<B>叶子结点</B>：这里就无需讨论什么范围了。若当前剩余分数的分子恰好为1，且分母大于上一个分数的分母，且分母小于最优解的最大分母，则更新解，否则退出。</LI></UL>　　上述过程中，为计算准确及在叶子结点处获得剩余分数的分母方便，剩余分数不要采用实数类型计算，而是设两个整型变量分别表示分子和分母。
<P>　　<B>注：</B>本题的题目描述不甚清楚。在多解的情况下，题目只说要分数个数最少，分数个数相同的情况下最大的分母最小。但是，若最大的分母还相同怎么办呢？比如8/27，是分解成1/4+1/36+1/54，还是分解成1/6+1/9+1/54？对此，我的程序输出的是找到的第一个解4 
36 54，亦即认为在最大的分母还相同的情况下，取字典顺序最小的一个。这可能不是出题者的原意，但用这种标准，我AC了。
<SCRIPT>detail 1030,"字符串的序号"</SCRIPT>
 
　　假设我们要求kensta的序号，那么我们只要求出以a开头的、以e开头的、以ka开头的……字符串各有多少，累加就行了。剩下的任务就是已知一些字符，求它们可以组成多少个不同的字符串。这是一个重排列问题。假设共有n种字符，其中字符c<SUB>i</SUB>有a<SUB>i</SUB>个，那么求这些字符可以组成的不同字符串数的公式为<IMG 
src="vol1.files/1030_1.gif" align=absMiddle>。
<SCRIPT>detail 1031,"猫和老鼠"</SCRIPT>
 　　宽搜即可，因为总状态数只有(10*10*4)<SUP>2</SUP>=160000。
<SCRIPT>detail 1032,"等式问题"</SCRIPT>
 　　先用预处理算出符号的所有填法对应的结果，然后问哪个输出哪个就行。
<SCRIPT>detail 1033,"线型网络"</SCRIPT>
 
　　此题的确定算法，不是TLE就是MLE。这时，随机算法就大显神通了。<BR>　　首先随机生成一条路径，然后对其进行优化。用dist[a,b]表示路径上第a个点与第b个点之间的距离。假设存在某一对a,b使得dist[a-1,a]+dist[b,b+1]&gt;dist[a-1,b]+dist[a,b+1]（规定dist[0,*]=dist[*,N+1]=0），那么把第a个点至第b个点这一段路反向，得到的新路径会更短。不断把某一段路反向直至无法再优化为止。<BR>　　这样做并不能保证得到的解最优，因为有时“退一步海阔天空”，而这种本质是贪心的随机算法却“退”不下这一步。然而，这种情况毕竟是少见的。因为N的范围并不大，所以把上一段所述的过程重复一定次数（我的程序中为99次），就基本可以保证得到最优解了。
<SCRIPT>detail 1034,"四塔问题"</SCRIPT>
 　　我们把利用三个、四个柱子移动i个盘子所需的移动次数分别记为f[i]、g[i]。为了推出g[i]的表达式，把用四个柱子移动i个盘子的过程分为三步：
<OL>
  <LI>把上面j个盘子移到某一工作柱上。这一步可以用四个柱子，所需移动次数为g[j]。
  <LI>把下面i-j个盘子移到目的柱上。因为上一步占用的工作柱在此步中不能使用，因此此步所需移动次数为f[i-j]。
  <LI>再把工作柱上的j个盘子移到目的柱上，所需移动次数为g[j]。</LI></OL>因此得到递推式：
<BLOCKQUOTE>g[1]=1<BR>g[i]=min{g[j]*2+f[i-j]}(1&lt;=j&lt;i,i&gt;1)</BLOCKQUOTE>　　然而仅仅利用这个式子，算法复杂度是O(n<SUP>2</SUP>)的，对于n&lt;=50000的数据范围，显然无法承受。因此，我们列出i值较小时的f[i]和g[i]，以期发现某种规律。<BR>
<TABLE cellSpacing=0 width="40%" align=center>
  <TBODY>
  <TR align=middle>
    <TH>i
    <TD>1
    <TD>2
    <TD>3
    <TD>4
    <TD>5
    <TD>6
    <TD>7
    <TD>8
    <TD>9
    <TD>10
    <TD>11 
  <TR align=middle>
    <TH>f[i]
    <TD>1
    <TD>3
    <TD>7
    <TD>15
    <TD>31
    <TD>63
    <TD>127
    <TD>255
    <TD>511
    <TD>1023
    <TD>2047 
  <TR align=middle>
    <TH>g[i]
    <TD>1
    <TD>3
    <TD>5