vol1.htm

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

<script>detail 1033,"线型网络"</script>
　　此题的确定算法，不是TLE就是MLE。这时，随机算法就大显神通了。<br>
　　首先随机生成一条路径，然后对其进行优化。用dist[a,b]表示路径上第a个点与第b个点之间的距离。假设存在某一对a,b使得dist[a-1,a]+dist[b,b+1]>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]。</ol>因此得到递推式：<blockquote>g[1]=1<br>g[i]=min{g[j]*2+f[i-j]}(1<=j&lti,i>1)</blockquote>
　　然而仅仅利用这个式子，算法复杂度是O(n<sup>2</sup>)的，对于n<=50000的数据范围，显然无法承受。因此，我们列出i值较小时的f[i]和g[i]，以期发现某种规律。<br>
  <table align=center cellspacing=0 width=40%>
    <tr align=center><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=center><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=center><th>g[i]<td>1<td>3<td>5<td>9<td>13<td>17<td>25<td>33<td>41<td>49<td>65
  </table>
　　观察这个表，我们可以大胆地猜想g[i]的规律：<b>从1开始，加2次2，再加3次4，再加4次8，再加5次16……</b>这个猜想的证明过程过于琐碎，详细、严谨的步骤反而会妨碍理解，我只说一下大概思路：显然g[2]是用g[1]和f[1]算出来的。假设g[i]=g[j]*2+f[i-j]，那么g[i+1]=min{g[j+1]*2+f[i-j],g[j]*2+f[i-j+1]}，即把f或g的下标增加1。为什么呢？因为f和g两个数列都是增长的，而且增长得越来越快。如果在最优解的基础上让f的下标变大、g的下标变小，或是相反，结果不是不变就是变大。亲手模拟一下g的计算过程，就会发现，<b>g数列加2<sup>k</sup>的次数等于g数列加2<sup>k-1</sup>的次数与f数列加2<sup>k</sup>的次数之和。</b>由此可以得出上面的猜想。<br>
　　这个问题可以推广到m塔的情况。用a[i]表示m柱i盘时所需的移动次数，则a数列有这样一个规律：a[1]=1，以后依次有<img src=img_vol1/1034_1.gif>项比前一项大2<sup>k</sup>，其中k从1开始取整数值。
<script>detail 1035,"撕邮票"</script>
　　搜索、判重。判重时若保存整个图象比较每个格子则嫌慢，其实有一点小技巧：把每个图象看作一串二进制数，用一个数来存储这个图象每个格子的信息，再加上一个宽度就可以唯一地表示一个图象了。由于一个图象经翻转、旋转可得到8种形态，我们需要按某种规则只存储一个（如宽度取较长边，宽度一定时使二进制数最小）。这样既节省了时间，又节省了空间。
<script>detail 1036,"序列函数"</script>
　　用一个队列q来存储序列，初始时设q[0]=1。设三个头指针f1,f2,f3，分别对应于三个质数p1,p2,p3（假设p1&ltp2&ltp3）。头指针的初值均为0。每次取q[f1]*p1,q[f2]*p2,q[f3]*p3中的最小值，如果当前队列为空或它与当前队尾元素不同，则将其放进队列。无论是否放进队列，都将产生最小值的头指针加1。当队列达到所需的长度时，输出队尾元素。
<script>detail 1037,"最短网络"</script>
　　赤裸裸的最小生成树模型。
<script>detail 1038,"化学方程式"</script>
　　思路极清晰：列多元一次方程组，用高斯消元法解。所谓高斯消元法，就是用一个含x<sub>i</sub>的方程（记为E<sub>i</sub>）与其它所有方程加减，消去其它方程中的x<sub>i</sub>，待解出x<sub>1</sub>至x<sub>i-1</sub>后，代入E<sub>i</sub>求x<sub>i</sub>。但编程极麻烦，具体来说，有下面几点提示或注意事项：
  <ul><li>跟<a href=vol2.htm#1117>1117</a>一样，列方程时最好在整个反应式最左边加个'+'，倒着进行。
  <li>消元时若待消的未知数已不存在，则No solution。
  <li>消元时若未知数比方程多两个或两个以上，即方程过少，则No solution。
  <li>消到只剩一个未知数时，方程应当一个也不剩，否则，剩下的方程中均只含最后一个未知数，它只能等于0，这是不合题意的。简言之，方程过多时也是No solution。
  <li>两个方程加减后不要忘了及时约掉各系数的最大公约数，以免过程中系数过大。
  <li>消元结束后，令x<sub>1</sub>=1，利用各E<sub>i</sub>依次推出各x<sub>i</sub>。若碰到某个x<sub>i</sub>为分数，则将x<sub>1</sub>至x<sub>i-1</sub>均乘以x<sub>i</sub>的分母。若碰到某个x<sub>i</sub><=0，则No solution。</ul>
<script>detail 1039,"核电站问题"</script>
　　DP。用f[n]表示n个坑时的放法数，则有<br>
　　f[0]=1<br>
　　f[n]=f[n-1]*2 (1<=n&ltm)<br>
　　f[n]=<img align=absmiddle src=img_vol1/1039_1.gif> (n>=m)<br>
　　注意到f[n-1]=<img align=absmiddle src=img_vol1/1039_2.gif> (n>m)，两式相减得f[n]-f[n-1]=f[n-1]-f[n-m-1] (n>m)。于是可以化简最后一个方程：<br>
　　f[m]=f[n-1]*2-1<br>
　　f[n]=f[n-1]*2-f[n-m-1] (n>m)
<script>detail 1040,"N的倍数"</script>
　　妙极了的算法：最短路。<br>
　　把自然数除以N的每个可能余数，即0~N-1，分别看成一个结点。若一个数字d是可用的，那么对任一顶点x，连一条从x到(x*10+d) mod N的有向边，边上标有数字d。然后把结点0看成两个结点0和0'，用简单的BFS找一条从0到0'的最短路，路径上所有边上标的数字连起来就是答案。<br>
　　用BFS似乎只能保证答案的位数最少而不能保证值最小，其实不然。只要在扩展结点时按边上所标数字从小到大的顺序进行，答案的值也一定是最小的。
<script>detail 1041,"战略游戏"</script>
  <ul><li><font color=blue><b>树型DP</b></font>（我的算法）：首先建树，任选一个结点为根。设要看守住以x为根的子树中所有边，x处有士兵时需要的最少士兵数为yes[x]，x处无士兵时需要的最少士兵数为no[x]。自下而上地计算每个结点的yes值和no值：一个结点的yes值等于它所有子树的yes值与no值的较小值之和再加1；no值等于它所有子树的yes值之和。根结点的yes值和no值中的较小值即为答案。
  <li><font color=blue><b>贪心</b></font>：找出所有度为1的结点，把与它们相连的结点上都放上士兵，然后把这些度为1的结点及已放上士兵的结点都去掉。重复上述过程直至树空为止。
  <li><font color=blue><b>二分图最小覆盖</b></font>（by HybridTheory）：把树看成一个二分图，奇数层的结点放到一边，偶数层的结点放到一边，然后求这个二分图的最小覆盖数（等于最大匹配数）。</ul>
<script>detail 1042,"替换问题"</script>
　　好奇异的算法，不知<b>Cocoran</b>大牛是怎么想出来的。<br>
　　用S<sub>i</sub>表示a<sub>1</sub>至a<sub>i</sub>的和，S'<sub>i</sub>表示b<sub>1</sub>至b<sub>i</sub>的和。下面研究三种操作对各S<sub>i</sub>的影响：
  <ul><li>对a<sub>i-1</sub>、a<sub>i</sub>、a<sub>i+1</sub>(1&lti&ltn)进行操作，相当于交换了S<sub>i-1</sub>和S<sub>i</sub>。
  <li>对a<sub>n</sub>、a<sub>1</sub>、a<sub>2</sub>进行操作，相当于把所有的S<sub>i</sub>都减去a<sub>1</sub>，再交换S<sub>1</sub>与S<sub>n</sub>。
  <li>对a<sub>n-1</sub>、a<sub>n</sub>、a<sub>1</sub>进行操作，相当于把所有的S<sub>i</sub>都加上a<sub>n</sub>，再交换S<sub>n-1</sub>与S<sub>n</sub>。</ul>
　　于是我们看出，无论进行多少次怎样的操作，结果只是把所有的S<sub>i</sub>都加上或减去了某一数值，然后进行了若干次交换。于是把a<sub>1</sub>至a<sub>n</sub>、b<sub>1</sub>至b<sub>n</sub>分别排序，若所有的S<sub>i</sub>-S'<sub>i</sub>均相等，则YES，否则NO。
<script>detail 1043,"黑白棋"</script>
　　简单深搜。只是面对某一个棋局时，若轮到的一方无处下子，要妥善处理pass的情况。
<script>detail 1046,"立方馅饼"</script>
　　把x+y+z的为奇数的格子染成黑色，x+y+z为偶数的格子染成白色。若n为奇数，则Yes的充要条件是起点与终点均为黑色；若n为偶数，则Yes的充要条件是起点与终点异色。
<script>detail 1047,"自然数序列"</script>
　　每次取数列的后四项，让两头两项为正，中间两项为负（当然反过来也行），这样这四项的和就是0了，将这四项删去。这样做到最后最多只剩3项。若剩3项或一项也不剩（即n mod 4=3或0），则答案为0，否则答案为1（因为添加负号不改变和的奇偶性，而这时所有数的和为奇数，故答案无法达到0）。
<script>detail 1048,"Tom的烦恼"</script>
　　用best[t]表示在时间t以前Tom得到的最大加工费。按时间递增的顺序计算best数组。对每个best[t]，首先令其为上一个时间的best值，然后对于每一个在时间t结束的工作（设其开始时间为s，加工费为m），比较best[s]+m与best[t]的值，取大者。<br>
　　由于时间的数值可能远远大于工作的数量，因此最好首先对时间进行离散化。
<script>detail 1049,"砝码问题"</script>
　　思路参看<a href=#1017>1017 石子归并</a>问题。本题的大数据规模版本就是<a href=vol2.htm#1166>1166 背包问题</a>。
<script>detail 1057,"办公室失窃案"</script>
　　把每个时间段看成一条线段，用扫描线法找到被n条线段同时覆盖的区间，输出。当然要注意输入输出的细节。
<script>detail 1058,"地板覆盖问题"</script>
　　老老实实地按题目说的顺序判断，即先判断所有砖中是否有交叉，再判断所有砖中是否有越界情况，最后判断地板是否全被覆盖。切不可看到第一块砖越界了就下结论，因为第二块和第三块可能交叉。两块砖(x1,y1)-(x2,y2)与(x3,y3)-(x4,y4)交叉的充要条件是(x1&ltx4) and (x3&ltx2) and (y1&lty4) and (y3&lty2)。第三步判断砖是否盖满地板时，可以累加所有砖的面积，若这个和与地板的面积相等，则盖满。
<script>detail 1059,"数的计数"</script>
　　用f[n]表示最后一个数是n时，可以构造出的数的总数。规定f[0]=1，则显然有f[n]=f[0]+f[1]+...+f[n div 2]。<br>
　　但若直接使用这个方程，则会既TLE又MLE。注意到右边其实是f数组开头若干个元素的和，因此可开一个s数组，用s[n]来存储f[0]至f[n]的和。这样时间上显然没有问题。实际上，现在f数组已经不必要了，因为用s数组可写出如下状态转移方程：s[n]=s[n-1]+f[n]=s[n-1]+s[n div 2]。当读入n时，输出s[n div 2]即可。<br>
　　结果很大，高精度是当然的。可以用3个int64来存储一个数。这里我们看到用s数组代替f数组同样解决了MLE的问题，因为s数组的大小只有f数组的一半，题目允许的内存不能容纳f数组，却恰好可以容纳s数组。
<script>detail 1060,"方程的解数"</script>
　　查了一下NOI的原题，发现有一个重要条件，题目中落掉了：<b><font size=4>&Sigma;</font>Ki*M<sup>Pi</sup><=maxlongint</b>。这个条件告诉我们，无论每个x取什么值，结果不会超过longint范围，因此不必考虑int64或是高精度之类的问题。另外，由于150<sup>5</sup>>maxlongint，所以P不会超过4。<br>
　　这道题只能用枚举法，其瓶颈显然在于计算速度。注意到乘幂运算需屡次进行，因此很自然地想到用预处理先计算出所有的乘幂值（只有150*4=600个而已）。然而这毕竟只是细节上的优化，本质的还在于找一个高效的算法。<br>
　　把方程的半数项移到右边。得到的新方程与原方程是相似的，只是右边不再为0。但是，每一边的项数不超过3，也就是说枚举量不超过150<sup>3</sup>=3375000，这个复杂度是完全可以承受的。我们可以枚举左边，用一个表将所有可能的结果及其出现次数存储起来，然后枚举右边，在表中查找右边结果的相反数，累加表中存储的出现次数即得到答案。现在的问题是：用什么表来存储结果呢？<br>
　　如果用有序表和二分查找的话，那么对300多万个数进行排序就需要好几秒，对同样多的数进行二分查找又需要同样多的时间，显然不可取。本题适用的数据结构是：<b>哈希表</b>。哈希函数很好找：设x为结果，那么hash(x)=abs(x) mod bigprime，其中bigprime为一个取定的大质数。这样，存储和查找就几乎都是线性的了。这样处理以后，算法的时间复杂度为O(M<sup>3</sup>)，带一个适中的常数系数。<br>
　　然而本题的内存限制是很紧的，哈希表这种耗内存的数据结构一不小心就会MLE。我的经验是：
  <ul><li>不要用指针，而用数组来模拟，因为指针本身就耗内存，而且分配、回收操作也浪费不少时间。至于处理冲突的问题，可以建立公共溢出区，即把冲突的元素统统放到公共溢出区中。
  <li>哈希表中无需存储原始的元素。假设原始元素为x，那么在hash表中只需存储x div bigprime+ord(x>0)。之所以要加入ord(x>0)一项，是因为如果不加，-1和1就会变成同一个数0。经过这一变换，x的范围就由原来的longint变为integer（我的bigprime取的是999983），又省了大量内存。</ul>
<script>detail 1061,"堆栈计算"</script>
　　题目中的表达式是一个树型结构，因此想到用树型DP解决这个问题。<br>
　　把在表达式中位置为i的字符代表的结点称作结点i。首先用递归的方法找到每个B结点的左孩子的位置。结点i的左孩子用child[i]表示，显然结点i的右孩子为i-1。<br>
　　用space[i]表示计算以i为根的子树所需的最少堆栈空间，swap[j,i]表示如果有大小为j的堆栈空间可用，计算以i为根的子树所需的最少交换次数。堆栈大小不同时，这个次数是不同的，例如...BB在堆栈空间为2时需要交换1次，而在堆栈空间为3时则一次也不需要。<br>
　　按堆栈空间的大小j划分阶段，j的初值为1，这时对每个.结点i，有space[i]=1，swap[1,i]=0；对每个B结点i，有space[i]=无穷大，swap[1,i]=无穷大，这里的无穷大表示还没有算出来。<br>
　　设表达式长为l，则当space[l]=无穷大时，j加1，进行下面的状态转移。从左到右依次处理每一个结点的space值和swap值。
  <ul><li><b>space值的计算</b>：如果一个B结点(i)的space值为无穷大，而它的两个孩子（a、b）的space值都已算出，且有一个小于j（不妨设space[a]&ltj），那么令space[i]为j。这是因为可先利用大小为j的堆栈空间计算以b为根的子树，1个单位的堆栈空间被用来存储结果，而剩下的j-1个单位的堆栈空间足以计算以a为根的子树。
  <li><b>swap值的计算</b>：对于.结点，swap[j,i]显然为0。对于B结点(i，左右孩子分别为a、b)，则swap[j,i]=min{swap[j-1,i],swap[j,a]+swap[j-1,b],swap[j,b]+swap[j-1,a]+1}。注意最后一个元素，若先计算右子树，后计算左子树，则最后需交换两个结果，因此要加1。</ul>
　　注意到在计算swap数组的第j行时只用到了第j-1行，因此swap数组可用滚动数组来实现。
<script>detail 1068,"商务旅行"</script>
  <table align=right><tr><td>
    <img src=img_vol1/1068_1.gif><br>
    处理结点10的时候并查集的情况<br>
    （假设结点是按从左到右的顺序处理的）<br>
    与10的LCA是10的结点集合：{10}<br>
    与10的LCA是8结点集合：{8 9 11}<br>
    与10的LCA是3的结点集合：{3 7}<br>
    与10的LCA是1的结点集合：{1 2 5 6}<br>
    不属于任何集合的结点：4 12
  </table>
　　<font color=blue><b>感谢Faint.Wisdom讲解求最近公共祖先(LCA)的Tarjan算法！</b></font>下面是算法的详细讲解：<br>
　　首先，Tarjan算法是一种离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。而打乱这个顺序正是这个算法的巧妙之处。看完下文，你便会发现，如果偏要按原来的顺序处理询问，Tarjan算法将无法进行。<br>