tongji online judge solutions b.htm

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

  <LI>a[i]、b[i]这两个值需要经常用到，因此需对其进行预处理。注意到在状态转移方程中，是加a[i]+b[i]还是加b[i]与m的奇偶有关，于是用a[true,i]表示原来的a[i]+b[i]，用a[false,i]表示原来的b[i]，这样在j循环中就可以减少一次判断了。 

  <LI>显然f[n,*]只与f[n-1,*]有关，因此f应做成滚动数组f[boolean,0..maxm]（此处的maxm应为题目中的maxm*2+1）。因为在j循环中要屡次访问f[odd(i),*]和f[not 
  odd(i),*]，因此用b1、b2两个布尔变量暂存odd(i)和not odd(i)的值，以减少odd函数的调用次数。 
  <LI>DP算法的一个特点是它计算的信息量很大，而算出来的信息往往有一部分是没有用的。如右图，整个矩形表示本题中DP计算的总信息量，而其中只有蓝色部分是有用的，这部分还占不上总信息量的一半。因此有必要仅计算蓝色部分所代表的信息，这就是j循环前计算的k、l的用途。这一操作可以显著提高程序效率。 

  <LI>继续观察状态转移方程。方程中有求较小值这一步，用程序中的方法做而不另外设一个临时变量，既可以省一个变量，在某些情况下还可以省去一次赋值。这样做导致了j循环必须用downto而不能用to，请仔细思考一下为什么。 

  <LI>再介绍一个好东西：{$R-}，即关闭range check。在保证程序不会发生数组越界等错误时，range 
  check是既多余又耗时的。加上这一编译开关后，程序的运行时间缩短了一半以上，提交后用2.3s 
  AC（虽然这个速度仍不是很快）。P.S.其实还有一个编译开关{$Q-}，即关闭overflow check，也能提高程序速度。</LI></OL>
<SCRIPT>detail 1169,"广告印刷"</SCRIPT>
　　显然当广告面积最大时，要有一个建筑物被刷满。枚举这个建筑物的编号，然后寻找把这个建筑物刷满的广告向左、向右最远分别能延伸到什么位置。<BR>　　用l[i]、r[i]分别表示建筑物i被刷满时广告向左、向右最远能延伸到的位置。从左到右依次计算每个l[i]：初始时令l[i]=i，然后while 
h[i]&lt;=h[l[i]-1] do 
l[i]:=l[l[i]]（h[i]表示第i个建筑物的高度）。r[i]的计算方法类似，只是方向为从右向左。为计算方便可令h[0]=h[n+1]=0。答案就是所有h[i]*(r[i]-l[i]+1)中的最大值。<BR>　　由于上述的while循环类似于并查集中的路径压缩，故本算法的复杂度可近似认为是O(n)，只是常数系数较大些。
<P>　　P.S.我在竞赛时，看到n的最大值是1000000，就不自觉地想O(nlogn)复杂度的算法，像静态排序二叉树，像堆，等等等等……花了两个小时，编了五个程序，换来一个TLE:(<BR>　　后来想到这个算法，5分钟编完程，2.2s 
AC。当时，我觉得这个算法就是O(n)的，看到用时这么长，感觉很奇怪。后来证明复杂度为O(n)时遇到了困难，才发现还有个常数系数在捣鬼。
<SCRIPT>detail 1170,"一进制计数"</SCRIPT>
 
　　用unary[n]表示n的一进制表达式的最短长度。这个表达式的最后一步可以是加，也可以是乘。如果是加的话，那么几乎肯定有一个加数是1（这个我没有证明）；如果是乘的话，则需要枚举n的约数i（大于1，小于等于trunc(sqrt(n))）。由此得状态转移方程：unary[n]=min{unary[n-1]+1,unary[i]+unary[n 
div 
i]}。<BR>　　下面解释一下为什么我认为“如果最后一步是加，则几乎肯定有一个加数是1”：整个unary数组的总趋势是增加的，而且越是在开头，增加得越快，较往后的位置基本在同一数值附近摆动。更为甚者，开头5个元素恰好是1,2,3,4,5，增长得不能再快了（因为unary[n+1]-unary[n]&lt;=1）。那么unary[1]+unary[n-1]&lt;=unary[2]+unary[n-2]&lt;=unary[3]+unary[n-3]&lt;=unary[4]+unary[n-4]&lt;=unary[5]+unary[n-5]，而这一串不等式中，不仅所有的&lt;=全取等号的可能性微乎其微，而且在一般情况下，unary[5]+unary[n-5]比unary[1]+unary[n-1]要大不少。因此可近似认为，若unary[i]+unary[n-i](i&lt;=n-i)中的i再增大，由于unary[i]的增长速度快于unary[n-i]的下降速度，这个式子的值是不会变得小于unary[1]+unary[n-1]的。实践也证明了这一点。<BR>　　但是，如果对于每一个n，从2至trunc(sqrt(n))依次检验每个数是否为n的约数，则算法复杂度为O(n<SUP>3/2</SUP>)，运行将花费20~30秒，严重超时。于是换一种思路：给每个数开一个栈（当然也可以用队列）。假设当前处理到n，则i就在i的倍数中不小于n且最小的那一个的栈中。处理n(n&gt;=2)时，首先令unary[n]=unary[n-1]+1，然后对于n的栈中的每一个元素f，(1)检查unary[f]+unary[n 
div 
f]是否小于当前的unary[n]，若小于则更新；(2)将f从n的栈中取出，放到n+f的栈里。我的程序中，栈是用数组模拟的链表实现的。另外，每一个数i不必在开始时就放到i的栈里，可等到处理到sqr(i)时再放进sqr(i)的栈，因为在此之前，若i在n的栈里，则若n=i，显然i无用，若n&gt;i，因为n 
div i&lt;i，故i也无用。<BR>　　这种改进算法避免了检验一个数是否是另一个数的约数，只用了2s多就AC。
<SCRIPT>detail 1171,"最大奖励"</SCRIPT>
 　　呼呼，思路比程序还长，有些地方还显得很突兀，不知怎么能想到。我问了21天，终于搞懂了。谢谢<B>Wanght_1</B>的整理。
<P>　　此题的DP用<B>逆推</B>。至于为什么用逆推，下文会讲。用F[i]表示第i题以后的题的最大总得分（i就是阶段）。状态转移方程为：<BR>　　　　F[n]=0（显然）<BR>　　　　F[i]=max{F[j]+W[i,j]}(i&lt;j&lt;=n)<BR>　　其中，W[i,j]=(S[j]-S[i])*i-T<BR>　　　　S[n]为前n道题的分值和。<BR>　　依次计算F[n-1]至F[0]，F[0]就是答案。
<P>　　用B[i,k]表示阶段i的决策k（决策k表示第i题之后的那一段到第k题为止）的结果，则B[i,k]=F[k]+W[i,k]。<BR>　　下面寻找n&gt;=k<SUB>1</SUB>&gt;k<SUB>2</SUB>&gt;i，且S[k<SUB>1</SUB>]&gt;S[k<SUB>2</SUB>]时，B[i,k<SUB>1</SUB>]&gt;=B[i,k<SUB>2</SUB>]（决策k<SUB>1</SUB>不劣于k<SUB>2</SUB>）的充要条件：<BR>　　　　B[i,k<SUB>1</SUB>]&gt;=B[i,k<SUB>2</SUB>]<BR>　　&lt;=&gt; 
F[k<SUB>1</SUB>]+(S[k<SUB>1</SUB>]-S[i])<FONT 
color=red>*i</FONT>-T&gt;=F[k<SUB>2</SUB>]+(S[k<SUB>2</SUB>]-S[i])<FONT 
color=red>*i</FONT>-T<BR>　　&lt;=&gt; 
F[k<SUB>2</SUB>]-F[k<SUB>1</SUB>]&lt;=(S[k<SUB>1</SUB>]-S[k<SUB>2</SUB>])*i<BR>　　&lt;=&gt; 
(F[k<SUB>2</SUB>]-F[k<SUB>1</SUB>])/(S[k<SUB>1</SUB>]-S[k<SUB>2</SUB>])&lt;=i<BR>　　令g(k<SUB>1</SUB>,k<SUB>2</SUB>)=(F[k<SUB>2</SUB>]-F[k<SUB>1</SUB>])/(S[k<SUB>1</SUB>]-S[k<SUB>2</SUB>])，则B[i,k<SUB>1</SUB>]&gt;=B[i,k<SUB>2</SUB>] 
&lt;=&gt; 
g(k<SUB>1</SUB>,k<SUB>2</SUB>)&lt;=i<BR>　　同理有B[i,k<SUB>1</SUB>]&lt;B[i,k<SUB>2</SUB>] 
&lt;=&gt; g(k<SUB>1</SUB>,k<SUB>2</SUB>)&gt;i。
<P>　　现在说一下为什么用逆推而不是顺推。观察上面推导过程中两个红色的*i。括号外的这个系数是取决于一段开头的位置的。如果用逆推，这个系数对应的是阶段，因此上面的推导能够进行。如果用顺推，这个系数将对应于决策，而我们现在讨论的就是<B>不同</B>决策的优劣，这个系数不同将使推导遇到相当大的困难。
<P>　　维护一个决策队列q，使q<SUB>j</SUB>递减，g(q<SUB>j</SUB>,q<SUB>j+1</SUB>)也递减。（谁知道怎么想到的呢？）<BR>　　依次计算F[n-1]至F[0]。下面考虑计算F[i]时的情形。 

<OL>
  <LI>目前决策i+1尚未进入队列。如果i+2&lt;=n且a[i+2]=0，那么显然i+1不是最优决策，此步不必进行。否则，将决策i+1放到队列末尾，这样保证了q<SUB>j</SUB>递减。但对于此时队尾的三个决策a,b,c，g(a,b)&gt;g(b,c)不一定成立。关注一下g(a,b)&lt;=g(b,c)的情况： 

  <UL>
    <LI>若g(a,b)&lt;=i，则B[i,a]&gt;=B[i,b]，决策a不劣于b。 
    <LI>若g(a,b)&gt;i，则g(b,c)&gt;i，B[i,b]&lt;B[i,c]，决策c优于b。</LI></UL>无论哪种情况，b要么不是最优决策，要么是最优决策但不唯一。因此可不断删除队列中倒数第二个决策，直至队列中决策不足三个或g(a,b)&gt;g(b,c)为止。 

  <LI>现在阶段i的可能决策都已经在队列中了。用a,b表示队列中的头两个决策。若g(a,b)&gt;i，那么a不是最优决策。由于g(a,b)&gt;i-1，因此a在以后也永远不可能成为最优决策，故可将其删除。不断删除队首决策直至g(a,b)&lt;=i。这时由于队列中所有g(a,b)均&lt;=i，故决策的效益是递减的，所以a为最优决策，F[i]=B[i,a]。</LI></OL>　　由于队列在整个过程中只被遍历一次，故算法复杂度为O(n)。
<P>　　<BIG><FONT 
color=blue><B>上述题解写于2005年4月。7月，我学到了一种较好地理解上述算法的方法：</B></FONT></BIG><BR>　　如右图，把队列中的决策画到一个坐标系中（<B>注意，右边的点位于队首，左边的点位于队尾</B>）。那么，阶段i的最优决策应满足的性质是：过此点作一条斜率（指绝对值，下同）为i的直线，其它所有决策应都位于此直线下方（或直线上）（记作性质①）。下面我们来看如何利用这个图来理解上述算法： 

<UL><IMG src="Tongji Online Judge Solutions B.files/1171_1.gif" align=right>
  <LI>g函数的值就是两点连线的斜率； 
  <LI>在队尾删除的决策，在图中处于点C的位置，而点C无论何时都不会满足性质①； 
  <LI>在队首删除的决策，在图中处于点A的位置，由于i递减，直线的斜率会越来越小，点A以后永远不会满足性质①。</LI></UL>　　由于算法可以利用斜率来理解，因此它被称为<FONT 
color=blue><B>斜率优化法</B></FONT>。<BR>　　由此也可以理解为什么本题使用逆推：因为斜率对应着阶段，而本题中，连续提交的一段题的系数是取决于这一段左端的位置的，左端为阶段而右端为决策，所以要用逆推。
<P>　　这种算法要求S具有单调性。那么，扩展一下，如果有某些题的分值为负怎么办呢？可以证明，若某一段（最左一段除外，记作A）的开头一部分（记作B）总分非正，则这一定不是一种最优划分。分两种情况考虑： 

<UL>
  <LI>若A总分值非正，则把A与上一段合并，这样不仅省了一次提交（少减了T分），而且减小了A的系数； 
  <LI>若A的总分为正，则这一段中除去B后剩下的一段（记作C）总分仍为正，故可将B移到前一段去，这样一来减小了B的系数，二来增大了C的系数。总之，若某一段的分值非正，则在这一段前划分的决策一定不是最优决策。</LI></UL>因此，可从最后一题向前扫描，累加分值，得到一个正分值后就把累加的这一段压缩成一道题，并把累加和清零。这样压缩以后，除了第一题分值可能非正以外，其余题的分值均为正数，于是便可以使用斜率优化法了。
<SCRIPT>detail 1174,"第一章 胜利的逃亡"</SCRIPT>
 　　用Bellman-Ford求2次最小费用增广路即可。当然，第一次用Dijkstra会更快些。
<SCRIPT>detail 1175,"第二章 文明的复兴"</SCRIPT>
 
　　首先将词典排序，然后从文本中的每个单词中提取出字母，用二分查找的方法确定这些字母组成的单词是否在词典中。用一般的方法对词典排序可能太慢，可以用一种部分桶排的方法：首先把所有单词按第一个字母排序，这样首字母相同的单词就各自聚到了一起；然后把首字母相同的单词按第二个字母排序……这样的排序方法避免了直接比较单词时，前面的字母都相同带来的冗余比较，对于此题来说是比较适合的排序算法。<BR>　　当然，建trie树的方法也是可行的。
<SCRIPT>detail 1176,"第三章 光荣的梦想"</SCRIPT>
 　　若数列中有这样两个数，前面的那个数比后面的大，那么这两个数就称为一个<B>逆序对</B>。下面证明最小的交换次数等于数列中逆序对的个数x。 
<UL>
  <LI><B>x次是足够的</B>。当数列中存在逆序对的时候，一定有一个逆序对是相邻的两个数，否则，整个数列就成了不递减的，与数列中存在逆序对矛盾。那么，每一次交换一定可以消灭一个逆序对，因此x次是足够的。 

  <LI><B>x次是必需的</B>。显然，一次交换最多只能消灭一个逆序对，因此要消灭全部x个逆序对至少需要x次交换。</LI></UL>　　现在的问题就是如何高效地求出数列中逆序对的数目。如果先把数列离散化，再用静态排序二叉树等树形数据结构计算每个数之前比它大的数有多少个，然后累加的方法，那么离散化和树形数据结构的复杂度均为O(nlogn)，这个复杂度的算法被执行了两次。能不能只执行一次呢？答案是肯定的：利用归并排序。<BR>　　回忆一下归并排序的过程：将数列分为长度相等或相差1的两段，分别归并排序后，把两段看成两个队列，每次取队首元素的较小值，排成一列后就得到有序的数列。观察排序前的数列，它当中的逆序对可以分为3类：1.两个数都在前一半的；2.两个数都在后一半的；3.一个数在前一半，一个数在后一半的。前两种情况的逆序对的个数可在对那一半的归并排序中计算，对整个序列的归并排序的主程序中只需计算第3种情况。注意到归并过程中，当第二个队列的队首元素小于第一个队列的队首元素时，第二个队列的队首元素与第一个队列中剩下的元素均构成了逆序对，这时在答案上加上第一个队列中剩余元素的个数即可。只加这么一条语句，就可以在归并排序的过程中顺便求出逆序对的个数了。
<SCRIPT>detail 1177,"第四章 英雄的叛变"</SCRIPT>
 　　<B>这道题的输入中有前导的0，请加以处理，否则会WA掉！</B>
<P>　　下文提到一个数的“前一半”时，若这个数有奇数位，“前一半”均包括中间一位。<BR>　　给每个完美数编一个号，使得相邻的完美数的编号也相邻。编号方法如下： 

<UL>
  <LI>若其位数为偶数，则取其前一半，在最高位前一位加1。如456654的编号为1456。 
  <LI>若其位数为奇数，则取其前一半，在最高位上加1。如121的编号为22，92429的编号为1024。</LI></UL>　　由编号还原出完美数的方法如下： 
<UL>
  <LI>若编号首位为1且第二位不为0，则说明对应的完美数为偶数位。去掉首位的1得到的就是完美数的前一半。 
  <LI>若编号首位大于1或前两位为10，则说明对应的完美数为奇数位。若首位大于1则在首位减1，否则在第2位减1，得到的就是完美数的前一半。</LI></UL>　　这样子算法就很简单了：求出前一半与a相同的完美数的编号。若a比这个完美数小，则将编号减1。在编号上加上k，还原成完美数，就得到答案。
<SCRIPT>detail 1186,"卫星覆盖"</SCRIPT>
 
　　在USACO上学到了一种既简单又优秀的“切法”，它不仅适用于正方体，同时也适用于长方体。<BR>　　这种“切法”依次计算每个长方体不与以前的长方体重叠的部分的体积，相加。计算过程是递归进行的。在计算第x个长方体时，调用cal(x-1,第x个长方体)。过程cal(m,长方体C)的内容是：从第m个长方体到第1个长方体依次判断与长方体C的相交情况，如果都不相交，则累加长方体C的体积；如果有一个长方体与长方体C相交了（不妨设是第y个），就把长方体C在第y个长方体外的部分切成若干块，对每一块D执行过程cal(y-1,长方体D）。切的方法是：如果长方体C有在第y个长方体左边的部分，就把它切下来；然后剩下的部分如果有在第y个长方体右边的部分，也把它切下来；上、下、前、后四个方向按同样方法处理。<BR>　　这种切法对于一般数据来说效率是很高的。它所遇到的最坏情况就是输入的长方体都是扁平的板状，交织成三维网络（当然，本题输入的都是正方体，没有这个问题），这种情况下此法会切出数量级为O(n<SUP>3</SUP>)的小长方体（感觉跟离散化了一样）。但大多数的小长方体不会再被切割了，因此这种切法的最坏时间复杂度可以近似认为是O(n<SUP>3</SUP>)。使用线段树可以把平均时间复杂度降至O(n<SUP>2</SUP>logn)，但编程复杂度明显高于切法。
<SCRIPT>detail 1190,"个人所得税"</SCRIPT>
 　　BS题目把m&lt;=400说成m&lt;=50000吓唬人。另外，注意输入中相邻两项之间可能有<B>多个空格</B>。
<SCRIPT>detail 1196,"01串"</SCRIPT>
 　　利用本题，我来讲一下<FONT 
color=blue><B>差分约束系统</B></FONT>。<BR>　　所谓差分约束系统，就是求关于x<SUB>i</SUB>的由一系列形如x<SUB>i</SUB>-x<SUB>j</SUB>&gt;=a的不等式组成的不等式组的解。我们构建一个有向图，图中的每个结点代表一个x<SUB>i</SUB>。对于每个不等式x<SUB>i</SUB>-x<SUB>j</SUB>&gt;=a，连一条从x<SUB>j</SUB>到x<SUB>i</SUB>的权为a的边。不妨设x<SUB>1</SUB>=0，那么令x<SUB>i</SUB>等于x<SUB>1</SUB>至x<SUB>i</SUB>的最长路的长度，这样就得到了一组可行解。若图中存在正权回路，即对于某些点最长路不存在，那么不等式组无解。<BR>　　为什么呢？先看有解的情况。因为若从x<SUB>i</SUB>到x<SUB>j</SUB>的有一条长为s的路，则要求x<SUB>j</SUB>-x<SUB>i</SUB>&gt;=s。现在x<SUB>j</SUB>与x<SUB>i</SUB>的差是x<SUB>i</SUB>到x<SUB>j</SUB>的最长路的长度，那么对于从x<SUB>i</SUB>到x<SUB>j</SUB>的任一条路（设其长为s），自然有x<SUB>j</SUB>-x<SUB>i</SUB>&gt;=s成立。再看无解的情况。设从x<SUB>i</SUB>到其本身有一条权为s的正权回路，则要求x<SUB>i</SUB>-x<SUB>i</SUB>&gt;=s，即0&gt;=s，这显然是不可能的。<BR>　　有了差分约束系统这个武器，解决本题就不难了。用S<SUB>i</SUB>表示01串前i位的和，规定S<SUB>0</SUB>=0。建一个含有N+1个结点的有向图，每个结点分别代表S<SUB>0</SUB>至S<SUB>N</SUB>。然后在图中连边： 

<UL>
  <LI>由于每个数非0即1，故有0&lt;=S<SUB>i</SUB>-S<SUB>i-1</SUB>&lt;=1(1&lt;=i&lt;=N)，即对于每个i，从S<SUB>i-1</SUB>向S<SUB>i</SUB>连一条权为0的边，从S<SUB>i</SUB>向S<SUB>i-1</SUB>连一条权为-1的边。 

  <LI>对任意长度为L0的子串，其中0的个数不小于A0，不大于B0，即其中1的个数不小于L0-B0，不大于L0-A0。故有L0-B0&lt;=S<SUB>i</SUB>-S<SUB>i-L0</SUB>&lt;=L0-A0(L0&lt;=i&lt;=N)。故对于每个i，从S<SUB>i-L0</SUB>向S<SUB>i</SUB>连一条权为L0-B0的边，从S<SUB>i</SUB>向S<SUB>i-L0</SUB>连一条权为A0-L0的边。 

  <LI>对任意长度为L1的子串，其中1的个数不小于A1，不大于B1，即A1&lt;=S<SUB>i</SUB>-S<SUB>i-L1</SUB>&lt;=B1(L1&lt;=i&lt;=N)。故对于每个i，从S<SUB>i-L1</SUB>向S<SUB>i</SUB>连一条权为A1的边，从S<SUB>i</SUB>向S<SUB>i-L1</SUB>连一条权为-B1的边。</LI></UL>　　求S<SUB>0</SUB>到每个结点的最长路，就可以求出每个S<SUB>i</SUB>了。01串中的第i位s<SUB>i</SUB>也就等于S<SUB>i</SUB>-S<SUB>i-1</SUB>。
<SCRIPT>detail 1199,"棋盘分割"</SCR