vol2.htm

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

<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]<=1）。那么unary[1]+unary[n-1]<=unary[2]+unary[n-2]<=unary[3]+unary[n-3]<=unary[4]+unary[n-4]<=unary[5]+unary[n-5]，而这一串不等式中，不仅所有的<=全取等号的可能性微乎其微，而且在一般情况下，unary[5]+unary[n-5]比unary[1]+unary[n-1]要大不少。因此可近似认为，若unary[i]+unary[n-i](i<=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>=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>i，因为n div i&lti，故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&ltj<=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>=k<sub>1</sub>>k<sub>2</sub>>i，且S[k<sub>1</sub>]>S[k<sub>2</sub>]时，B[i,k<sub>1</sub>]>=B[i,k<sub>2</sub>]（决策k<sub>1</sub>不劣于k<sub>2</sub>）的充要条件：<br>
　　　　B[i,k<sub>1</sub>]>=B[i,k<sub>2</sub>]<br>
　　<=> F[k<sub>1</sub>]+(S[k<sub>1</sub>]-S[i])<font color=red>*i</font>-T>=F[k<sub>2</sub>]+(S[k<sub>2</sub>]-S[i])<font color=red>*i</font>-T<br>
　　<=> F[k<sub>2</sub>]-F[k<sub>1</sub>]<=(S[k<sub>1</sub>]-S[k<sub>2</sub>])*i<br>
　　<=> (F[k<sub>2</sub>]-F[k<sub>1</sub>])/(S[k<sub>1</sub>]-S[k<sub>2</sub>])<=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>]>=B[i,k<sub>2</sub>] <=> g(k<sub>1</sub>,k<sub>2</sub>)<=i<br>
　　同理有B[i,k<sub>1</sub>]&ltB[i,k<sub>2</sub>] <=> g(k<sub>1</sub>,k<sub>2</sub>)>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<=n且a[i+2]=0，那么显然i+1不是最优决策，此步不必进行。否则，将决策i+1放到队列末尾，这样保证了q<sub>j</sub>递减。但对于此时队尾的三个决策a,b,c，g(a,b)>g(b,c)不一定成立。关注一下g(a,b)<=g(b,c)的情况：
    <ul><li>若g(a,b)<=i，则B[i,a]>=B[i,b]，决策a不劣于b。
    <li>若g(a,b)>i，则g(b,c)>i，B[i,b]&ltB[i,c]，决策c优于b。</ul>
    无论哪种情况，b要么不是最优决策，要么是最优决策但不唯一。因此可不断删除队列中倒数第二个决策，直至队列中决策不足三个或g(a,b)>g(b,c)为止。
  <li>现在阶段i的可能决策都已经在队列中了。用a,b表示队列中的头两个决策。若g(a,b)>i，那么a不是最优决策。由于g(a,b)>i-1，因此a在以后也永远不可能成为最优决策，故可将其删除。不断删除队首决策直至g(a,b)<=i。这时由于队列中所有g(a,b)均<=i，故决策的效益是递减的，所以a为最优决策，F[i]=B[i,a]。</ol>
　　由于队列在整个过程中只被遍历一次，故算法复杂度为O(n)。<p>
　　<big><font color=blue><b>上述题解写于2005年4月。7月，我学到了一种较好地理解上述算法的方法：</b></font></big><br>
　　如右图，把队列中的决策画到一个坐标系中（<b>注意，右边的点位于队首，左边的点位于队尾</b>）。那么，阶段i的最优决策应满足的性质是：过此点作一条斜率（指绝对值，下同）为i的直线，其它所有决策应都位于此直线下方（或直线上）（记作性质①）。下面我们来看如何利用这个图来理解上述算法：
  <ul><img align=right src=img_vol2/1171_1.gif><li>g函数的值就是两点连线的斜率；
  <li>在队尾删除的决策，在图中处于点C的位置，而点C无论何时都不会满足性质①；
  <li>在队首删除的决策，在图中处于点A的位置，由于i递减，直线的斜率会越来越小，点A以后永远不会满足性质①。</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的系数。总之，若某一段的分值非正，则在这一段前划分的决策一定不是最优决策。</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次交换。</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。</ul>
　　由编号还原出完美数的方法如下：
  <ul><li>若编号首位为1且第二位不为0，则说明对应的完美数为偶数位。去掉首位的1得到的就是完美数的前一半。
  <li>若编号首位大于1或前两位为10，则说明对应的完美数为奇数位。若首位大于1则在首位减1，否则在第2位减1，得到的就是完美数的前一半。</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<=400说成m<=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>>=a的不等式组成的不等式组的解。我们构建一个有向图，图中的每个结点代表一个x<sub>i</sub>。对于每个不等式x<sub>i</sub>-x<sub>j</sub>>=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>>=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>>=s成立。再看无解的情况。设从x<sub>i</sub>到其本身有一条权为s的正权回路，则要求x<sub>i</sub>-x<sub>i</sub>>=s，即0>=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<=S<sub>i</sub>-S<sub>i-1</sub><=1(1<=i<=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<=S<sub>i</sub>-S<sub>i-L0</sub><=L0-A0(L0<=i<=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<=S<sub>i</sub>-S<sub>i-L1</sub><=B1(L1<=i<=N)。故对于每个i，从S<sub>i-L1</sub>向S<sub>i</sub>连一条权为A1的边，从S<sub>i</sub>向S<sub>i-L1</sub>连一条权为-B1的边。</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,"棋盘分割"</script>
　　下文中，<font size=4>&Sigma;</font>符号下方的i=1与上方的n均省略。<br>
　　首先，我们对均方差的公式&sigma;=sqrt(<font size=4>&Sigma;</font>(x<sub>i</sub>-<span style=text-decoration:overline>x</span>)<sup>2</sup>/n)进行分析：根号显然是没有用的；对于一个特定的棋盘，n为定值，故根号下的分母也是没有用的。我们继续整理根号下的分子：<br>
　　　<font size=4>&Sigma;</font>(x<sub>i</sub> - <span style=text-decoration:overline>x</span>)<sup>2</sup><br>
　　= <font size=4>&Sigma;</font>(x<sub>i</sub><sup>2</sup> - 2x<sub>i</sub><span style=text-decoration:overline>x</span> + <span style=text-decoration:overline>x</span><sup>2</sup>)<br>
　　= <font size=4>&Sigma;</font>x<sub>i</sub><sup>2</sup> - 2n<span style=text-decoration:overline>x</span><sup>2</sup> + n<span style=text-decoration:overline>x</span><sup>2</sup><br>
　　= <font size=4>&Sigma;</font>x<sub>i</sub><sup>2</sup> - n<span style=text-decoration:overline>x</span><sup>2</sup><br>
　　分析整理后的式子：对于一个特定的棋盘，n是定值，<span style=text-decoration:overline>x</span>也是定值（等于棋盘每个格子的权之和除以n）。因此，问题的目标就由均方差最小转化为平方和最小。显然这个问题可以用动态规划解决：对于每块棋盘，我们用四类处理方法：切去左边的一部分，切去右边的一部分，切去上边的一部分，切去下边的一部分。<br>
　　在动态规划的过程中需要屡次用到某块棋盘的权和，我们可以用预处理的方法使得不必每次都重新累加：设s[i,j]为棋盘(1,1)-(i,j)的权和（若i=0或j=0，则s[i,j]=0），则棋盘