vol3.htm

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
'1270
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
prob "&nbsp",0
</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>
　　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数组的时间也是平方级的，故整个算法的复杂度仍为平方级。