vol3.htm

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

　　Miller-Rabin算法基于这样一个定理：把满足a<sup>n-1</sup> mod n=1的整数n叫做基于a的<b>伪素数</b>，那么，若一个数是伪素数，那么它有很大的概率是素数，而若一个数不是伪素数，它一定不是素数。Miller-Rabin的过程就是随机地选取若干个基，若对于每个基，n都是素数，则可以认为n是素数。<br>
　　Miller-Rabin并不是一个确定算法。在只选一次基的情况下，一个合数是伪素数的概率的理论上界是1/4。但对于本题这么大的数据，Miller-Rabin算法出错的概率是微乎其微的（有人试过，大约是0.3%）。因此，只选一个基就可以AC了。如果觉得不保险，可以选取2-3个。<br>
　　本题要求一个幂对一个数的余数，自然要用二分法。由于本题并不需要输出Fib[n]的值，因此本题的高精度可以不用十进制而用二进制（或2<sup>n</sup>进制，如我使用了32768进制）来实现，这样在求余数时可以避免试商，只需要进行移位和减法运算。<p>
　　Miller-Rabin算法是很慢的，在本题规定的时限内用Miller-Rabin算法判断前500个Fib数是否为素数几乎不可能。但我们可能通过这样一条定理来省去不少Miller-Rabin测试：<br>
　　<b>若m是n的倍数，则Fib[m]是Fib[n]的倍数。</b><br>
　　证明：当n<=2时，由于Fib[n]=1，结论显然成立。当n>=3时，设Fib[n+1] mod Fib[n]=x，则Fib[n+2] mod Fib[n]也等于x，由此可得Fib[n+i] mod Fib[n]=Fib[i]*x mod Fib[n]。所以Fib[n的倍数] mod Fib[n]=Fib[n] mod Fib[n]=0。<br>
　　由此可以得出：当n>4时，若n为合数，则Fib[n]必为合数。因此本题的最终算法是这样的：<br>
　　对于一个比较小的Fib数，不必用Miller-Rabin测试，直接使用普通的素数测试法即可。对于一个比较大的Fib数，先检查它的下标，若是素数再进行Miller-Rabin测试。<p>
　　最后献上一条温馨提示：由于本题const的人比较多，因此n的范围在不断被扩大。猫老大说了，只要发现一个const的就加大一次数据范围。因此在程序中不要把maxn设为500，要留一点余地，比如设成1000哦:)
<script>detail 1251,"键盘设计者"</script>
　　用sum[i,j]表示把从第i个字母开始的连续j个字母放到同一个键上的代价。这个数组可在平方级的时间内算出来。用cost[i,j]表示在i个键上放j个字母的最小代价，cut[i,j]表示在代价最小时，前i-1个键上放置的字母的个数。很容易写出状态转移方程：cost[i,j]=min{cost[i-1,k]+sum[k+1,j]},i-1<=k<=j-1，使cost[i,j]取最小值的最小的k（因为要求最后一个键上的字母尽可能多）就是cut[i,j]。这种DP的时间复杂度是立方级的。<br>
　　但本题的时间复杂度还可以降至平方级。这需要用到下面这个不等式：cut[i-1,j]<=cut[i,j]<=cut[i,j+1]。这个不等式的直观理解就是：当键减少一个时，最后一个键上的字母数不会比原来少；当字母增加一个时，最后一个键上的字母同样不会比原来少。下面给出证明：<p>
　　<img align=right src=img_vol3/1251_1.gif>先证cut[i-1,j]<=cut[i,j]。我们采用反证法，即证若cut[i-1,j]>cut[i,j]，那么不等号右边对应的方案不是最优方案。右图表示四种不同的划分方案，每条线段表示j个字母，线段的第i段表示第i个键上的字母。我们把线段上标出的点称为<b>分点</b>。方案一为i-1个键，j个字母的最优划分方案，对应着不等号的左边；方案二为i个键，j个字母的某种划分方案，且满足cut[i-1,j]>cut[i,j]，它对应着不等号的右边。我们称线段的每一段（包括左分点，但不包括右分点）为一个<b>区间</b>。由于方案一中分点的个数比方案二少一个，故由抽屉原理，方案一中必存在这样一个区间，它在方案二中对应的位置有至少两个分点，而这个区间显然不是最后一个区间。设这一个区间为[A,B)，它在方案二中对应段上最右面两个分点称为a,b。我们仿照方案一、二构造了方案三、四。由于方案一是i-1个键，j个字母的最优划分方案，故cost<sub>1</sub>&ltcost<sub>3</sub>（用cost<sub>i</sub>表示第i种方案中某些字母的代价，这里指所有字母的总代价）。然后我们比较cost<sub>3</sub>-cost<sub>1</sub>与cost<sub>2</sub>-cost<sub>4</sub>的大小：<br>
　　对于绿色部分左边的部分，cost<sub>3</sub>=cost<sub>1</sub>，cost<sub>2</sub>=cost<sub>4</sub>，故cost<sub>3</sub>-cost<sub>1</sub>=cost<sub>2</sub>-cost<sub>4</sub>；<br>
　　对于绿色部分右边的部分，cost<sub>3</sub>=cost<sub>2</sub>，cost<sub>1</sub>=cost<sub>4</sub>，故cost<sub>3</sub>-cost<sub>1</sub>=cost<sub>2</sub>-cost<sub>4</sub>；<br>
　　对于绿色部分，　　　　　cost<sub>3</sub>=cost<sub>2</sub>，cost<sub>1</sub>>cost<sub>4</sub>，故cost<sub>3</sub>-cost<sub>1</sub>&ltcost<sub>2</sub>-cost<sub>4</sub>。<br>
　　三部分相加，得cost<sub>3</sub>-cost<sub>1</sub>&ltcost<sub>2</sub>-cost<sub>4</sub>。因为cost<sub>1</sub>&ltcost<sub>3</sub>，所以cost<sub>2</sub>>cost<sub>4</sub>，所以在i个键，j个字母的划分方案中，方案四比方案二优。证毕。<p>
　　<img align=right src=img_vol3/1251_2.gif>再证cut[i,j]<=cut[i,j+1]。同样采用反证法。右图表示四种不同的划分方案，方案一为i个键，j个字母的最优划分方案，对应着不等号的左边；方案二为i个键，j+1个字母的某种划分方案，且满足cut[i,j]>cut[i,j+1]，它对应着不等号的右边。方案四的代价与方案一的代价之差等于方案四中多出的一个字母的代价，方案二的代价与方案三的代价之差等于方案二中多出的一个字母的代价，显然前者小于后者，即cost<sub>4</sub>-cost<sub>1</sub>&ltcost<sub>2</sub>-cost<sub>3</sub>。又因为cost<sub>1</sub>&ltcost<sub>3</sub>，所以cost<sub>2</sub>>cost<sub>4</sub>，所以在i个键，j+1个字母的划分方案中，方案四比方案二优。证毕。<p>
　　有了这个不等式以后，我们可以按照i递增，j递减的顺序来计算min和cut数组。这样计算每一个元素时，它所用到的元素（min[i-1,*],cut[i-1,j],cut[i,j+1]）都已求得。当然，在确定cut[i,j]的循环范围时，不要忘了i-1<=cut[i,j]<=j-1这一限制条件。下面进行时间复杂度分析。如果我们画一个直角坐标系，i轴向右，j轴向下，则每一个呈“捺”状的斜行对应的元素的cut值的范围恰好连成0..j-1，即计算每一个斜行的时间复杂度为线性的。这样的斜行的数量与问题规模同样成线性关系，因此DP的时间复杂度是平方级的。求sum数组的时间也是平方级的，故整个算法的复杂度仍为平方级。
<script>detail 1252,"遗传基因"</script>
　　把遗传特征看成一个有向图。找出一个包含所有特征的基因段，即遍历图中所有的边。显然，为了使基因段最短，我们应该用最少的笔数遍历图，因为每画一笔，经过的点数就要比边数多1。于是，我们只要求出整个图需要几笔画成，再加上图中的边数，就得到答案。<br>
　　求一个图需要几笔画成，可以一个连通块一个连通块地计算。对于一个连通块，若它的每个点的入度和出度均相等，则它仅需一笔画成；否则，所需笔数为所有出度大于入度的点的出度与入度的差之和。
<script>detail 1254,"高速公路"</script>
　　本题的模型是把起点、终点和所有的测量点看成一个图中的点，两点之间的边权为在这两点之间直线修路的费用，然后求从起点到终点的最短路。实际上这个模型是有问题的，因为有可能存在一种情况，转弯点设在山脚下，但并不在测量点。虽然题目禁止了这种方案，但我们可以将转弯点稍稍移动一下，使它离开山脚，但总费用的变化可以忽略。在此，我只能讲一下这个不完全正确的模型的解法。<br>
　　求最短路用Dijkstra算法即可。关键的问题在于如何求在两点间直线修路的费用。为了求出这个费用，我们需要求出这条路在每座山内部的路程。对于一座山，我们可以求出路与山的各条边的交点。如果山的顶点也恰在路上，那么这些顶点也算在交点内。这些交点将路分成了若干段，现在我们要做的就是求出每一段是否在山内。扫描线法是容易想到了，但这种方法并不好，因为我们不能说一个是顶点的交点两侧的路段必定一个在山内，一个在山外。于是我们换一种思路：求出每一段的中点（其实段上非端点的任一点均可），判断这个中点是否在山内，以此断定这一段是否在山内。判断不在山的轮廓上的一点是否在山内，可以从这一点向远处一点（“远处”可以保证在山外）引线段，求这条线段经过的山的边数的奇偶性——若奇，则点在山内；若偶，则点在山外。为了保证这条线段不经过山的顶点，远处一点的坐标要选得不规则一些。上面的奇偶法只适用于不在山的轮廓上的点，因此在使用之前要判断点是否在边上（因为我们判断的点都不是交点，所以它不可能在顶点上），在边上的点认为在山外。<br>
　　本题的运算量很大，所以要注意细节上的优化。尽量省略只使用一次的中间变量（如计算叉积、点积的函数只写一条语句），大约可以节省一半的运行时间。
<script>detail 1255,"RAR or ZIP"</script>
　　由于给出了排序后方阵的最右一列，我们把这些字母排序（桶排即可）后自然可以得出方阵的最左一列。显然，方阵每一行的最后一个字母与第一个字母在原文中是相邻的（如果认为原文中最后一个字母与第一个字母也相邻的话）。我们自然产生了一种美好的设想：根据第一个字母就可以找到第二个字母，再根据第二个字母找到第三个字母……就这样按图索骥，就可以恢复出原文了！<br>
　　对样例进行试验，成功。但这样做没有问题吗？有！看totoro这个单词：<br>
  <table align=center><tr>
    <td align=center><font color=blue>构造字符串：</font><br>totoro<br>otorot<br>toroto<br>orotot<br>rototo<br>ototor
    <td align=center><font color=blue>将字符串排序：</font><br>otorot<br>orotot<br>ototor<br>rototo<br>totoro<br>toroto
    <td><font color=blue>压缩结果：</font><br>S'=ttrooo<br>p=1
  </tr></table>
　　因为第一个字母是第一行末尾的t，所以第二个字母是o。但是，这个o是第四行末尾的o，还是第五行或者第六行末尾的o？这个问题难以解决，因为三个o在最右一列中的顺序是由<b>它们的下一个字母</b>决定的，而下一个字母并不已知。因此上述算法对重复字母无能为力。<br>
　　让我们来一下逆向思维：顺推不行，逆推行吗？答案是肯定的。所谓逆推，就是指当我们知道原文中某个字母在方阵中某一行的开头时，这一行末尾的字母就是原文中当前字母的上一个字母（把原文中最后一个字母看作第一个字母的上一个字母）。还以totoro为例：第一个字母是t。由于最左一列中相同字母是按<b>它们本身</b>在原文中的位置排列的，因此这个t必定是最左一列中最上面的t，即第五行的t。因此原文的最后一个字母是o。这个o自然应该是最左一列中最下面的o，即第三行的o。所以原文第五个字母是r，第四个字母是o，这个o在方阵中位于第二行第一列……哈，问题圆满解决。由于排序时运用了桶排，所以复杂度仅为O(n)。
<script>detail 1256,"奇怪的电梯"</script>
　　宽搜求最短路。
<script>detail 1257,"铸铁模具"</script>
　　开一个大小与模具相等的数组，存储每个位置被挖去的深度。然后一步一步地模拟刀片的运动，刀片每到一个在模具范围内的位置，就检查一下刀片的深度是否大于已挖去的深度。<br>
　　输入中的中括号是完全没有用的。本题的一个模块是读入数字。由于分号的结束符作用，我们不必开设缓冲区存储数字后的下一个字符。哈哈，知道Pascal中为什么每条语句后面都要有分号了:)
<script>detail 1258,"九数码问题"</script>
　　由目标状态开始，逆用移动规则，用BFS求出变换到每个状态所需的步数，然后问哪个状态就答哪个好了。为了存储每个状态的步数，需要给每个状态编一个号。我们不妨把0至8这九个数的所有排列按字典序排序，然后从0开始编号。求一个排列的编号可以如下进行：（为简便起见，以五个数的排列24103为例）<br>
　　2 4 1 0 3 //第一个数比2小的5个数的排列共有2*4!=24个<br>
　　　3 1 0 2 //把2去掉，剩下的数中比2大的都减小1，就成了一个0~3的排列。第一个数比3小的4个数的排列共有3*3!=18个<br>
　　　　1 0 2 //第一个数比1小的3个数的排列共有1*2!=2个<br>
　　　　　0 1 //第一个数比0小的2个数的排列共有0*1!=0个<br>
　　所以，排列24103的编号为24+18+2+0=44。<p>
　　另外献上一点温馨提示：UNSOLVABLE的布局是不存在的。
<script>detail 1261,"数列拆分"</script>
　　本题没有什么统一的公式，所以还是要老老实实地分情况讨论。<br>
　　首先枚举项数n。项数的最小值为3。那么最大值呢？我们来看极端情况：各项和一定时，欲使项数尽可能大，应使每项尽可能小。那么数列就应该是1,2,3……因此，若设各项和为n，应有n*(n+1)/2=s。把n=sqrt(s*2)代入，左边大于右边，因此方程的正根小于sqrt(s*2)，故可用trunc(sqrt(s*2))作为n的最大值。<br>
　　在项数确定了的情况下，我们可以求出数列每项的平均数m=s*2/n以及最大的公差d=trunc((m-1)/((n-1)/2))（公差最大时首项为1，且m与1的差是(n-1)/2个公差）。下面还要对n分奇偶讨论：
  <ul><li>当n为奇数时，m就是数列的中间一项，故m必须为整数。这时，满足条件的数列个数为d。
  <li>当n为偶数时，m为数列中间两项的平均值，它可以是整数，也可以是整数点五的形式。
    <ul><li>若m是整数，则公差必为偶数。此时满足条件的数列个数为d div 2。
    <li>若m是整数点五，则公差必为奇数。此时满足条件数列个数为(d+1) div 2。</ul></ul>
<script>detail 1262,"空间站"</script>
　　本题我做得很麻烦，应该有优化的余地。<p>
　　此题的模型就是：给定一棵带权无根树，求把它的任一条边的权改为0后，树中的最长路的最小长度。<br>
　　10<sup>5</sup>的数据规模启示我们使用DP算法。为了DP方便，我们以1号顶点为根，把无根树转化为有根树。我对每个顶点x定义了如下函数（哇，好多啊@:(）：
  <ul><li>down1[x],down2[x],down3[x]：在以x为根的子树中，从x出发的最长路长度、次长路长度、第三长路长度。要求这三条路无公共边。
  <li>below[x]：在以x为根的子树中的最长路长度。注意这条最长路不一定经过x。
  <li>cbelow1[x],cbelow2[x]：x的孩子的below值中最大的一个和次大的一个。
  <li>up[x]：在原树中去掉以x为根的子树（但保留x结点）后，从x出发的最长路长度。
  <li>above[x]：在原树中去掉以x为根的子树及x与它父亲结点之间的边后，剩余部分的最长路长度。</ul>
　　上述所有函数在所对应的路径不存在时值均为0。<br>
　　DP总共进行两次。第一次自底向上进行，求出每个顶点的down1,down2,down3,below,cbelow1和cbelow2函数值；第二次自顶向下进行，求出每个顶点的up和above函数值，顺便算出答案。<br>
　　在第一次DP中，当处理到顶点x时，可以按如下方法求出x的一些函数值：
  <ul><li>对于x的每一个孩子y，求出x,y之间边的长度与down1[y]之和。这些和中最大的三个就是<font color=blue>down1[x],down2[x]和down3[x]</font>。
  <li>由于DP是自底向上进行的，x的所有孩子的below值中最大的两个就是<font color=blue>cbelow1[x]和cbelow2[x]</font>。
  <li><font color=blue>below[x]</font>为cbelow1[x]与down1[x]+down2[x]中的较大值。前者表示以x为根的子树中的最长路不经过x，后者表示经过x。</ul>
　　第二次DP则是这样：当处理到顶点x和它的孩子y时，可以按如下方法求出y的一些函数值：
  <ul><li>求<font color=blue>up[y]</font>。up[y]对应的路径的第一条边必然是(x,y)（长度记为L），然后有两种可能：<ul><li>一种是继续往上走，这时up[y]=L+up[x]；<li>还有一种是往下走。如果往下走，则不可以沿着(x,y)再回来，于是若down1[x]=L+down1[y]，则up[y]应等于L+down2[x]，否则就等于L+down1[x]。</ul>
  <li>求<font color=blue>above[y]</font>。有两种情况：<ul><li>一种情况是above[y]对应的路径不经过x。这时，它的长度可能是above[x]，也可能是cbelow1[x]（当cbelow1[x]<>below[y]时）或cbelow2[x]（当cbelow1[x]=below[y]时）。<li>另一种情况是above[y]对应的路径经过x。这时，可以把由x出发的最长的两条路连起来。候选的路径长度有：up[x],down1[x],down2[x]。当然，如果down1[x]或down2[x]中有一个等于L+down1[y]，那么它就没有资格了，而用down3[x]来替代。取候选路长中的最大值和次大值相加，即得above[y]。</ul>
  <li>求<font color=blue>把(x,y)的权修改为0后整棵树中的最长路长度</font>。有三种情况：<ol><li>这条路经过(x,y)，这时路长为up[y]-L+down1[y]（注意up[y]-L不可以用up[x]代替，因为从x开始可以往下走）；<li>这条路在(x,y)上方，这时路长为above[y]；<li>这条路在(x,y)下方，这时路长为below[y]。</ol>取这三者中的最大值，若这个最大值比当前最优解小，则更新最优解。</ul>
<script>detail 1264,"河床"</script>
　　从左到右扫描，依次把每个深度加入“当前段”中。当“当前段”中的最大值与最小值的差超过限制时，就在“当前段”开头截去尽可能短的一段，使最大值与最小值的差重新满足要求。那么，本题的关键就在于在最大值（或最小值）被截去后，如何快速地找到新的最大值（或最小值）。<br>
　　用线段树等树形结构，可以轻松地在1M内存以内解决问题，但它的时间复杂度为O(nlogd)，经测试，运行完所有数据需要将近2s。而实际上本题的内存限制是很松的。所以我们采用时空复杂度均为O(n)的队列解决本题。<br>
　　开两个队列，一个叫做<b>大队</b>，一个叫做<b>小队</b>。如果一个深度满足它是从它所在位置到“当前段”末尾的最大值（最小值），那么它就属于大队（小队）。另外附加一条规则：如果大队或小队中有若干个深度相同，那么仅保留位置最靠前的那一个。容易看出，大队中深度是递减的，小队中的深度是递增的。<br>
　　当“当前段”向右延伸一个位置的时候，就把这个新的深度加到两个队列末尾。这时，大队或小队的单调性可能被破坏。如果发生了这种情况，就把单调性被破坏的队列的倒数第二个元素删除，直至单调性重新成立为止。现在检查一下“当前段”是否满足要求。若大队队首元素（就是“当前段”中的最大深度）与“当前段”尾的深度之差超过限制，那么就不断地删除大队队首元素直至满足要求，同时把“当前段”首指针移到最后删除的那个深度所在位置的下一个位置。若小队队首元素与“当前段”尾的深度之差超过限制，则可用类似的办法进行处理。计算“当前段”的长度，与最优解比较。
<script>detail 1265,"批次计划管理"</script>