vol3.htm

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

prob "ac",1
prob "ac",1
prob "wa",0
'1260
prob "&nbsp",0
prob "ac",1
prob "ac",1
prob "&nbsp",0
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
'1270
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
'1280
prob "ac",1
prob "ac",1
</script>
</table>

<script>detail 1201,"内存分配"</script>
　　本题虽然数据规模比较大，但输入是比较随机的，也就是说，单纯的模拟就可以了。<br>
　　具体的方法是，用一个堆存储每个进程的结束时间，以便及时释放内存；同时用一个双向链表按每个进程在内存中的顺序存储其地址，这样在有新进程申请时就可以通过遍历链表而找到合适的地址运行它（所说的“输入比较随机”，就是指输入没有故意使得每次插入进程时都要遍历整个链表）。当然，还要有一个等待队列。为了让堆和链表同时更新，需要在堆和链表的对应元素间建立互链。这样处理每个进程的流程就可以描述如下：
  <ol><li>读入一个进程的信息；
  <li>将在新进程开始前或开始时结束的进程删除，检查等待队列首的进程是否可以运行；
  <li>判断新进程是可以运行还是需放进等待队列。</ol>
　　为了在所有进程都放进堆后可以清空堆，可以在最后假设读入了一个在无穷大时间结束的进程。<br>
　　上述流程中的第2步的实现要注意：既不能先把在新进程开始前或开始时结束的进程统统删除，再检查等待队列；也不能删除一个进程就检查一次队列。正确的做法是：把与堆顶进程同时结束的进程全部删除，检查等待队列，重复进行直至堆顶进程的结束时间晚于新进程的开始时间。为什么不能采用第2种做法呢？因为堆中元素仅仅按结束时间排序，若删除一个就检查一次等待队列，则可能造成在同时结束的进程中，地址大的先被删除，等待队列首的进程就正好被放在大地址了，而实际上它应该放在小地址，这样就造成了以后的混乱。<br>
<script>detail 1206,"青蛙过河"</script>
　　程序只有两行！<br>
　　先考虑比较弱的荷叶的作用。假设没有荷叶，那么从一个石墩往另一个石墩只能跳一只青蛙。若有1片荷叶，那么可以让较小的青蛙跳到荷叶上，较大的青蛙从起始石墩跳到目标石墩上，较小的青蛙再跳到较大的青蛙背上。这个过程相当于2只青蛙一起从起始石墩跳到目标石墩上。同理，若有2片荷叶，则相当于3只青蛙一起跳，推而广之，若有m片荷叶，则相当于m+1只青蛙一起跳。这就是荷叶唯一的作用。<br>
　　现在去掉荷叶，只考虑石墩。用F<sub>n</sub>表示河中有n个石墩，没有荷叶时可以过河的青蛙数。当河中没有石墩时，显然只能过1只青蛙，即F<sub>0</sub>=1。当河中有n个石墩时，过河过程这样进行，过河的青蛙数最多：
  <ol><li>for i:=n downto 1 do 利用i-1个石墩，让F<sub>i-1</sub>只青蛙跳到第i个石墩上。
  <li>左岸的一只青蛙直接跳到右岸。
  <li>for i:=1 to n do 利用i-1个石墩，让第i个石墩上的F<sub>i</sub>只青蛙跳到右岸。</ol>
　　这样便得到了{F<sub>n</sub>}的递推式：F<sub>n</sub>=<img align=middle src=img_vol3/1206_1.gif>+1。显然{F<sub>n</sub>}的通项式为F<sub>n</sub>=2<sup>n</sup>。再把荷叶的作用考虑进去，得出利用n个石墩，m片荷叶可以过河的青蛙数为2<sup>n</sup>(m+1)。
<script>detail 1209,"反正切函数的应用"</script>
　　∵arctan(1/a)=arctan(1/b)+arctan(1/c)<br>
　　∴1/a=(1/b+1/c)/(1-1/bc)，整理得c=a+(a<sup>2</sup>+1)/(b-a)<br>
　　不妨设b≤c，则b≤a+(a<sup>2</sup>+1)/(b-a)，(b-a)<sup>2</sup>≤a<sup>2</sup>+1，b≤a+sqrt(a<sup>2</sup>+1)<br>
　　又显然b≥a，故b的取值范围为[a+1,trunc(a+sqr(a<sup>2</sup>+1))]。<br>
　　到此已经可以枚举b，取所有的b+c中的最小值。但仍可利用b+c的单调性进行优化：<br>
　　令f(b)=b+c=b+a+(a<sup>2</sup>+1)/(b-a)，对其求导得f'(b)=1-(a<sup>2</sup>+1)/(b-a)<sup>2</sup>。∵(b-a)<sup>2</sup>≤a<sup>2</sup>+1，∴f'(b)≤0，∴f(b)单调递减。<br>
　　因此，可以从trunc(a+sqr(a<sup>2</sup>+1))开始从大到小依次枚举b，一旦遇到一个整数值f(b)，那它就是答案了。
<script>detail 1219,"木棒游戏"</script>
　　首先说明一点数据的问题：数据中有连续9个数字，但使用longint仍然可以。<br>
　　先把右边的项全移到左边。这一步不必真的修改算式，只要在以后处理等号右边时，把正负号反过来即可。以后说到算式，均指移项后的。扫描算式，算出每一位数字的权值（即这一位上的1相当于1后面接几个0）及它所在数字的正负，同时算出算式的左边需要加上多少才能变成0（记为sum）。然后试图修改算式。分两种情况讨论：
  <ul><li><b>把一根木棒拿走后，放到同一位数字上。</b>可能的变化有：2<->3，3<->5，0<->6，6<->9，9<->0。一位一位地试探，如果在某一位修改后引起的算式左边的变化量恰为sum，那么成功。<br>
  <li><b>把一根木棒拿走后，放到另一位数字上。</b>向一个数字上加一根木棒可能的变化有0->8，1->7，3->9，5->6，5->9，6->8，9->8，若减一根木棒，则反之。一位一位地试探，若某一位的改变（加或减一根木棒）在算式左边引起的变化量为a，在此位<b>之前</b>试探过的某一位的相反的改变（减或加一根木棒）在算式左边引起的变化量为b，且恰好有a+b=sum，则成功。已经试探过的数位的修改方案可以存储在一个数组中，当当前试探的数位可以产生a的改变量时，就可直接到数组中寻找改变量为sum-a的方案。
<script>detail 1241,"约数研究"</script>
<img align=right src=img_vol3/1241_2.gif>
　　显然，1~n的每个数的约数个数之和，等于这些数中约数1的个数，加上约数2的个数……一直加到约数n的个数。即答案为<img align=absmiddle src=img_vol3/1241_1.gif>。<br>
　　然而，本题的数据组数达到了20000，而上述公式的复杂度为O(n)，在n可能达到999999的情况下，肯定会超时。怎么办呢？让我们来观察一下上面的公式都加了些什么。<br>
　　把第一象限内所有满足x*y<=n的整点都描出来（右图示n=9的情况），则这些点的个数就是1~n的每个数的约数个数之和。而按上面的公式编出的循环程序在累加时，是一列一列地累加的。注意到图象右边很大一部分（绿点部分）每一列都只有极少数的点，因此循环在此浪费了大量时间。可不可以不累加这一部分呢？答案是肯定的！因为图象关于直线y=x对称，所以可以只累加一半。具体做法是，不从1累加到n，而只累加到trunc(sqrt(n))（红点组成的正方形一边上点的个数），这样就只累加了蓝点和红点的部分，累加和乘以2就是所有点数加上红点数（因为蓝点数和绿点数相等），再减去红点数，就得到答案了。这样，算法的复杂度成功地降为O(sqrt(n))。
<script>detail 1247,"照像也疯狂"</script>
　　本题很容易设计出朴素的DP算法：用cost[x]表示恰好照x张照片的花费，price[i]和count[i]表示每种照法的价格和照片数，则有cost[x]=min{cost[x-count[i]]+price[i]}，若无法正好取得x张照片，则cost[x]为无穷大。由于实际上Will照的照片可能稍多于k张，所以答案是cost[k]至cost[k+modulo-1]的最小值，其中modulo表示count[i]中的最大值。当然，计算过程需要用大小为modulo的滚动数组。<br>
　　但这样做有一个显然的问题：k的值可以达到4*10<sup>8</sup>，而这种算法的复杂度为O(kn)（n为照法数），必定TLE。那么如何减少计算量呢？注意到当需要的照片数足够多时，Will显然会尽量选择单价最低的照法。若用cheap表示单价最低的照法的编号（如有多个，取张数最小者），那么，当照片数到达一定数量以后，就会有cost[x]=cost[x-count[cheap]]+price[cheap]①。如果出现了这种情况，在cost数列以后的部分中每count[cheap]项取出一项，则取出的项恰构成一个等差数列，因此可直接将k缩小到略大于x的某一值（新旧k值应对模count[cheap]同余），计算出cost[k]至cost[k+modulo-1]的中的最小值，再利用等差数列的公式求出刚才跳过的部分的总价即可。<br>
　　那么，从什么时候起可以保证cost数列以后的部分具有上述性质呢？有人说，在10000以后就可以基本保证这样了。然而，这并不保险。保险的做法是，如果在cost数列中发现连续count[cheap]项都满足①式，则可以大刀阔斧地砍去大量计算了。<br>
　　在编程时我还发现了一个问题：如果各个count值的最大公约数大于1，那么cost数列中将会有不少无穷大项，这些项使得“连续count[cheap]项都满足①式”这一条件无法满足。解决方法是，在DP之前先求出各个count值的最大公约数g，然后用g除每个count值和k（若k mod g>0，则入上，即k:=k div g+ord(k mod g>0)）。
<script>detail 1248,"Fibonacci数列"</script>
　　递推关系<img align=middle src=img_vol3/1248_1.gif>（其中x<sub>i</sub>为常数）叫做k阶常系数线性递推关系，求满足此递推关系的数列的第n项的最正点的方法是<b>矩阵乘法</b>（简称矩乘），其复杂度为O(k<sup>3</sup>logn)。当然，这类数列通常增长都比较快，因此往往求的是第n项除以某个数的余数。<br>
　　先来讲一下矩阵乘法及矩阵幂的快速计算。两个矩阵可以相乘，当且仅当第一个矩阵的列数等于第二个矩阵的行数。由此亦可看出，矩乘没有交换律。现有两个矩阵A和B，A的大小为m*n，B的大小为n*p，则A*B的结果C是一个m*p的矩阵。它的每个元素满足<img align=absmiddle src=img_vol3/1248_2.gif>。矩乘的编程实现是十分简单的。<br>
　　计算矩阵幂，当然可以一次一次地乘。但是，由于矩乘满足结合律(A*B)*C=A*(B*C)，故可以用二分法计算矩阵幂。例如计算A<sup>n</sup>时，若n为偶数，则A<sup>n</sup>=A<sup>n/2</sup>*A<sup>n/2</sup>；若n为奇数，则A<sup>n</sup>=A<sup>(n-1)/2</sup>*A<sup>(n-1)/2</sup>*A。<br>
　　那么矩乘与矩阵幂在求满足k阶常系数线性递推关系的数列通项时有什么用呢？我们想办法构造一个矩阵A，使得[a<sub>p</sub> a<sub>p+1</sub> ... a<sub>p+k-1</sub>]*A=[a<sub>p+1</sub> a<sub>p+2</sub> ... a<sub>p+k</sub>]。容易得出矩阵A有如下特征：
  <ul><li>它的大小为k*k；
  <li>它的第k列为x<sub>1</sub>至x<sub>k</sub>，即递推关系中的系数；
  <li>第i(1<=i&ltk)列中除第i+1行元素为1外，其余元素均为0。</ul>
　　这样，每乘一次A，就可以多求出数列的一项，乘以A的n-k次幂，结果矩阵的最右一个元素就是要求的a<sub>n</sub>了。<br>
　　Fibonacci数列是满足k阶常系数线性递推关系的数列中比较简单的一个，它的k=2，x<sub>1</sub>=x<sub>2</sub>=1。由于它的递推关系的特殊性，本题的程序是有很大优化余地的，但我并没有进行优化，而是保留了矩乘的原始程序。<br>
<script>detail 1250,"摩天大楼"</script>
　　本题的实质就是输入n，判断Fibonacci数列的第n项（记作Fib[n]）是否为素数。由于Fib[n]的增长是极为迅速的，因此需要用Miller-Rabin算法来判断一个大整数是否为素数。<br>