vol3.htm

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

  　　首先要突破一个思维定势：同一种商品如果要买多个，其实不必同时购买。这样我们就可以得出一种购买策略：先把需要买的东西各买一件，然后用最低的优惠价购买剩下的商品。后一步显然很简单，所以，题目转化为如何用最少的钱购买每种所需商品各一件。为叙述方便，下文中所说的“商品”都是指需要购买的商品，设这些商品共n种。<BR>　　我们建立一个有向图G，图中有0至n共n+1个顶点。1至n号顶点各代表一种商品。从0向每个顶点引一条边，边权为这种商品的原价。另外，如果商品A可以优惠商品B，就从A到B引一条边，边权为优惠价。理想的情况是每种商品都以最低价购买，因此我们把通往1至n号每个顶点的权最小的边挑出来组成G的子图H。子图H具有这样一个性质：<B>每个顶点的入度均为1。</B>如果H可以进行拓扑排序，那么我们就可以根据这个拓扑序来以最低价购买每种商品了，总费用就是H中所有边的权和。<BR>　　那么现在的问题就是H中有圈怎么办。如果H中有圈，那么圈上的物品是不可能均以最低价购买的，必然有一个最低价要被放弃。那么放弃哪一个呢？我们通过把缩圈来确定。缩圈的方法如下： 

  <UL>
    <LI>首先把圈上所有边的权值都累加到总费用中。 
    <LI>然后把起点A在圈外，终点B在圈内的边的权值减少一个值，这个值等于圈内指向B的权值。 
    <LI>最后把圈缩成一点C。现在C的入度变成了0，为使H的性质依然成立，我们需要找出G中指向C的权最小的边，并把这条边加入H中。</LI></UL>　　我们决定不以最低优惠价购买的商品，就是新加入的边在缩圈以前指向的顶点所代表的商品，因为这样做增加的总费用（缩圈后新加边的权值）最小。不断缩圈直至H中无圈，问题便得到了解决。
  <SCRIPT>detail 1268,"树的序号"</SCRIPT>
   　　设有n个结点的二叉树共有c[n]棵，则c[n]可以通过公式<IMG src="vol3.files/1268_1.gif" 
  align=absMiddle>计算（i为左子树的结点数）。<BR>　　有了c数组，便很容易求出输入的序号表示的二叉树有几个结点，在有这么多结点的树中它的序号（从0开始）是多少。然后枚举左子树的结点数，又很容易求出它的左右子树各有几个结点，在相同结点数的子树中它们的序号各是多少。递归下去即可求出整个树了。
  <SCRIPT>detail 1269,"亮底牌"</SCRIPT>
   　　只存第一个人的牌可以节省内存（如果这也算技巧的话）。
  <SCRIPT>detail 1270,"杂务"</SCRIPT>
   　　每个杂务的完成时间等于它的所有先行杂务的完成时间的最大值加上它本身需要的时间。答案就是所有杂务完成时间的最大值。
  <SCRIPT>detail 1271,"括号序列"</SCRIPT>
   
  　　首先运用一点技巧：把输入序列中相邻且配对的括号全都去掉，一直去到不能再去为止。这一步可以减小一般数据的规模。<BR>　　然后进行DP。设f[i,j]为简化后字符串中第i个字符至第j个字符构成的子串需要添加的括号数。 

  <UL>
    <LI>当i&gt;j时我们规定f[i,j]=0。 
    <LI>当i=j时显然有f[i,j]=1。 
    <LI>当i&lt;j时，我们可以把这个字符串分为两段分别处理，因此f[i,j]为所有f[i,k]+f[k+1,j]中的最小值，这里i&lt;=k&lt;j。另外，如果第i个字符和第j个字符恰好配对，那么可以就让它们配对，即f[i,j]还可以等于f[i+1,j-1]。</LI></UL>　　按j-i递增的顺序计算f数组，答案就是f[1,l]（l为简化后的字符串的长度）。<BR>　　另外注意：<B>输入中可能有空串，因此程序结尾处的until 
  seekeof一定要改为until eof，否则空串就会被忽略掉。</B>
  <P>　　P.S.如果谁有O(n<SUP>2</SUP>)或者更优的算法，请告诉我。
  <SCRIPT>detail 1272,"生产计划"</SCRIPT>
   
  　　先解释一下题意：工厂每天都有一定的产品需求量，这些产品可以当天生产，也可以调用以前的库存。第n天的产品如果当前生产，那么生产每吨产品的花费就是cost[n]；如果在第m天生产后存储到第n天，那么每吨产品的总花费就是cost[m]+s*(n-m)。<BR>　　算法是很简单的。设第n天每吨产品的最小花费为best[n]，则best[n]=min{cost[i]+s*(n-i)}(1&lt;=i&lt;=n)。显然best的递推式为best[1]=cost[1],best[n]=min{cost[n],best[n-1]+s}(n&gt;1)。
  <SCRIPT>detail 1273,"逆序统计"</SCRIPT>
   
  　　下面的叙述中省略取模运算。<BR>　　用DP进行预处理。设f[n,k]为有k个逆序对的n个数的排列的数目。当k&lt;0或k&gt;n*(n-1)/2时，规定f[n,k]=0。计算非0的f[n,k]时，考察数n的位置。如果它是最后一个数，那么它与其它数构成了0个逆序对；如果它是倒数第二个数，则它构成了1个逆序对……如果它是第1个数，则它构成了n-1个逆序对。故有<IMG 
  src="vol3.files/1273_1.gif" 
  align=absMiddle>。<BR>　　为计算方便，我们设s[n,k]为f[n,0]至f[n,k]的累加和（k&lt;0时s[n,k]=0），这样状态转移方程便化为s[n,k]=s[n-1,k]-s[n-1,k-n]。我们不必计算f数组而可以直接计算s数组，当提问f[n,k]时，输出s[n,k]-s[n,k-1]。<BR>　　注意到当a+b=n*(n-1)/2时，f[n,a]=f[n,b]。因此，数组的第二维下标的最大值不必设为maxn*(maxn-1)/2，而只需设为此值的一半。这样会节省一半的空间和一定的时间。你可以看一下本题的状态，我是第一个用少于1M的内存解决问题的:)
  <SCRIPT>detail 1274,"二进制问题"</SCRIPT>
   　　设输入的数的二进制表示中最右边的一组连续的1有n个，则把这组1前面的那一个0改成1，这一组1本身改为0，并把整个数的最后n-1位改为1。
  <SCRIPT>detail 1275,"补丁VS错误"</SCRIPT>
   
  　　用二进制数表示每个错误存在与否的状态，以及每个补丁的使用条件和使用效果，可以用位运算简便地求出每个状态可以使用哪些补丁及使用后的新状态编号。于是问题转化为求一个有向图中某两点间最短路的问题。可采用用堆优化的Dijkstra算法，复杂度为O(nlogn+nm)（n为状态总数，m为补丁数）。
  <SCRIPT>detail 1276,"倒水问题"</SCRIPT>
   
  　　宽搜求最短路。由于每个任一时刻至少有一个杯子是空的或满的，所以状态可以用一个二元组表示：(0,x)表示第1个杯子空，(1,x)表示第1个杯子满，(2,x)表示第2个杯子空，(3,x)表示第2个杯子满；四种情况的x均表示另一个杯子中的水量。两杯都空的特殊状态用(0,0)或(2,0)表示均可，两杯都满的情况类似。
  <SCRIPT>detail 1277,"独木舟上的旅行"</SCRIPT>
   
  　　把体重超过独木舟最大载重量一半的人叫做<B>胖子</B>，其余的人叫做<B>瘦子</B>。首先把所有的人按体重排序（当然用桶排，因为人可能很多，而体重的可能值却很少）。按体重递减的顺序处理每一个胖子，如果有瘦子可以跟他同乘一条船，则把他们安排到同一条船上，否则只好让胖子独坐一条船了。当胖子处理完后，剩下的瘦子就可以一对一对地上船了。
  <SCRIPT>detail 1278,"午餐"</SCRIPT>
   
  　　首先，同一队中的人必须满足一个条件：吃饭越慢的越排在前面。简单证明一下：假设两个人打饭的时间分别为a、b，吃饭的时间分别为c、d，其中c&lt;d。假设第一个人排在前面，则第一个人吃完饭的时刻为a+c，第二个人吃完饭的时刻为a+b+d，这两个时刻的较大值为a+b+d（因为c&lt;d）。如果把他们的位置对换，则两个时刻分别为b+d和b+a+c。显然这两个都小于a+b+d。因此我们先把所有人按吃饭时间降序排列。<BR>　　然后使用DP算法。用buy[i]和eat[i]分别表示第i个人打饭和吃饭所需时间，sum[i]表示前i个人打饭所需的时间之和。设time[i,j]表示前i个人排队，第一队的总打饭时间为j时，最后一个人吃完饭的最早时刻。如果(i,j)是一种不可能的状态，则time值为无穷大。初始时只有time[0,0]为0，其余皆为无穷大。求time[i,j]时，对第i个人所排的队分情况讨论： 

  <UL>
    <LI>当j&gt;=buy[i]且time[i-1,j-buy[i]]不等于无穷大时，第i个人可以排第一队。这时最后一个吃完饭的人可能就是第i个人，也可能不是。如果是，则他吃完饭的时刻就是j+eat[i]；如果不是，则其余i-1个人吃完饭的时刻就是time[i-1,j-buy[i]]（很巧妙的）。这两个时刻的较大值就是所有i个人吃完饭的时刻，记作t1（如果第i个人不可以排第一队，则t1为无穷大）。 

    <LI>当time[i-1,j]不等于无穷大时，第i个人可以排第二队。如果最后一个吃完饭的人就是第i个人，则他吃完饭的时刻就是sum[i]-j+eat[i]，否则其余i-1个人吃完饭的时刻就是time[i-1,j]。这两个时间的较大值就是所有i个人吃完饭的时刻，记作t2（如果第i个人不可以排第二队，则t2为无穷大）。</LI></UL>　　t1和t2的较小值就是time[i,j]。答案就是所有time[n,j]的最小值，其中j的取值范围为0~sum[n]。
  <SCRIPT>detail 1279,"金字塔"</SCRIPT>
   
  <TABLE cellPadding=9>
    <TBODY>
    <TR>
      <TD><IMG src="vol3.files/1279_1.gif"> 
      <TD><IMG src="vol3.files/1279_2.gif"> 
      <TD>　　如图，把四面体放到坐标系中，使B点与原点重合，C点落在x轴正半轴上，D点位于xOy平面且y坐标为正，A点z坐标为正。B、C坐标很容易写出。利用两点间距离公式及BD、CD的长度，可以解出D点坐标。再利用两点间距离公式及AB、AC、AD的长度，可以解出A点坐标。四面体的体积就是dnz/6。 
    </TR></TBODY></TABLE>
  <SCRIPT>detail 1280,"九数码问题-版本2"</SCRIPT>
  　　双向广搜，即分别以初始状态和目标状态为根建两棵搜索树，这边搜一层，那边搜一层……。状态编号与<A 
  href="http://purety.jp/akisame/oi/TJU/vol3.htm#1258">版本1</A>相同。经试验，双向广搜在最坏的情况下的搜索量也只有4~5万个状态（总状态数有9!=362880个之多），效率很高。
  <SCRIPT>detail 1281,"星际大战"</SCRIPT>
   
  　　显然，分出的每项应尽量接近，否则，让大数减1，小数加1将使积更大。而且，分出的每个数不可以超过4，因为超过4的数总可以再分成两半，这两半的积比原数大。又显然不可以分出1，故分出的数只能是2,3,4。<BR>　　因为2*2=4，所以2和4的效果是一样的。那么问题就是尽量多分2还是多分3的问题。由于2^3&lt;3^2，所以尽量多分3是正确的选择。如果人数是3的倍数，那么就全分成3人组；如果人数除以3余2，那么就把剩下2人分为一组；如果余1，那么就拿出4人分成一组。 
<!-- START HOME FREE FOOTER CODE --></OBJECT></LAYER>
  <DIV></DIV></SPAN></STYLE></NOSCRIPT></TABLE></SCRIPT></APPLET>
  <CENTER></CENTER>
  <DIV class=ad_text align=center>
  <SCRIPT type=text/javascript><!--
google_ad_client = "pub-7093259457636557";
google_ad_width = 234;
google_ad_height = 60;
google_ad_format = "234x60_as";
google_ad_type = "text_image";
//2007-10-01: 2style(2style.net)
google_ad_channel = "5598176498";
google_color_border = "191919";
google_color_bg = "FFFFFF";
google_color_link = "0000FF";
google_color_text = "000000";
google_color_url = "008000";
google_ui_features = "rc:6";
//-->
</SCRIPT>

  <SCRIPT src="vol3.files/show_ads.js" type=text/javascript>
</SCRIPT>
  <A href="http://2style.net/" target=_blank><IMG height=1 alt=2style.net 
  src="vol3.files/fstats.htm" width=1 border=0></A> </DIV><!-- END HOME FREE FOOTER CODE --></LI></UL></BODY></HTML>