vol2.htm

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

prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",0
prob "ac",1
'1170
prob "ac",1
prob "ac",1
prob "ac",0
prob "ac",0
prob "ac",1
prob "ac",1
prob "ac",1
prob "ac",1
prob "&nbsp",0
prob "&nbsp",0
'1180
prob "ac",0
prob "ac",0
prob "ac",0
prob "ac",0
prob "ac",0
prob "ac",0
prob "ac",1
prob "ac",0
prob "ac",0
prob "ac",0
'1190
prob "ac",1
prob "ac",0
prob "&nbsp",0
prob "ac",0
prob "ac",0
prob "&nbsp",0
prob "ac",1
prob "ac",0
prob "ac",0
prob "ac",1
</script>
</table>

<script>detail 1100,"勇闯黄金十二宫……白羊宫"</script>
　　四件圣衣分别计算，相加即可。把一件圣衣上所有洞的破损程度值分成和尽可能接近的两组，则和较大的一组的和就是修补这件圣衣所需的最少时间。这个时间的求法可参看<a href=vol1.htm#1017>1017 石子归并</a>问题。
<script>detail 1101,"勇闯黄金十二宫……金牛宫"</script>
　　根据定义，一个数n是牛数的充要条件是它有4个或更多的质因数。因此将它分解质因数即可。注意可能有一个因数可能大于sqrt(n)。
<script>detail 1102,"勇闯黄金十二宫……双子宫"</script>
　　如果A的斧子在B手里，B的斧子在C手里……X的斧子在A手里，那么称A,B,C……X为一个<b>循环</b>。如果某个人的斧子恰在自己手里，那么他自己构成一个循环。循环中的人数称为<b>循环的长度</b>。<br>
　　先来看第一个问题：最少交换次数。长度为1和2的循环的最少交换次数显然分别为0和1。在一个长度为n的循环中，可以进行一次交换使其中一个人拿到自己的斧子，这样相当于把此循环分解成了两个循环，一个长度为1，另一个长度为n-1。由数学归纳法易知，长度为n的循环的最少交换次数为n-1。因此，总的最少交换次数等于总人数减去循环数。<br>
　　再看第二个问题：最短交换时间。长度为1和2的循环的最短交换时间同样显然分别为0和1。对于一个长度为n(n>2)的循环（其中的人按顺序编号为1..n），可以构造这样一种交换方法：
  <ul><li>第1个时间单位，第n个人不动，第i(1&le;i&le;n/2)个人与第n-i个人交换斧子；
  <li>第2个时间单位，第i(1&le;i&le;(n+1)/2)个人与第n+1-i个人交换斧子。</ul>
　　所以最短交换时间为2。因此，若最大循环长度为1，则总的最短交换时间为0；若最大循环长度为2，则总的最短交换时间为1；否则为2。
<script>detail 1103,"勇闯黄金十二宫……巨蟹宫"</script>
　　这道题与<a href=#1084>1084</a>是极为类似的。同样是搜索每个质因数的指数，用同样的公式计算约数个数，用同样的不等式剪枝。此题与<a href=vol1.htm#1084>1084</a>相比较简单的一点是，虽然在试乘的过程中数值会超出longint甚至cardinal的范围，但不必使用高精度，用int64即可。
<script>detail 1107,"勇闯黄金十二宫……天蝎宫"</script>
　　<b>气死人的题：题目中说n<=10，但测试数据中的n没有超过6的！！！</b>所以，朴素搜索即可，不必加任何剪枝。
<script>detail 1113,"反约瑟夫"</script>
　　用F[n]表示n个人围一圈时，最后剩下的人的编号。显然F[1]=1。当我们知道F[i-1]时，我们可以算出F[i]：首先数过去M个人，然后剩下的人相当于在玩i-1个人的约瑟夫游戏，所以最后剩下的人在这i-1个人中的次序应该是F[i-1]。因此F[i]=(M+F[i-1]) mod i，当结果为0时修正为i。<br>
　　有了这个复杂度为O(n)式子，我们便可以从小到大枚举M了。
<script>detail 1117,"分子量计算"</script>
　　一点窍门：在整个式子左边加一个'('，倒着递归计算比较方便。
<script>detail 1119,"范式"</script>
　　这道题显然要用构造法。首先我们要知道哪些数的结果是Yes，最好能证明，还需要知道结果是No的数反例如何构造。<br>
　　做个实验就会发现，对大于等于4的偶数，反例遍地都是，而大于等于7的奇数，反例不多，但是存在。<br>
　　先看简单的情况，即偶数。设n为偶数，则Fan(n)为n组n-1个括号相乘相加。我们只需使第一组括号乘积为负，其它组括号乘积全为0即可。于是很容易想出反例：2 3 3...（共n-1个3）。<br>
　　再看奇数。仍用上面的思路，但这次要构造一组负积就困难一些了。设n为奇数。令A1=2，则A2至An中，需要有奇数个数大于2，奇数个数小于2。如果小于2的只有1个，假设为A2=1，那么第2组括号将为正值而不为0。于是我们只好令A2=A3=A4=1，而A5至An全部等于3。同样，大于2的数也不能只有一个，因此n至少等于7。<br>
　　那么Yes的情况就只能有2、3、5了。下面试着证明。为书写方便，不用A1、A2等表示每个数，而用a、b等表示。<br>
　　Fan(2)=(a-b)+(b-a)=0>=0是显然的。Fan(3)=(a-b)(a-c)+(b-a)(b-c)+(c-a)(c-b)=a<sup>2</sup>+b<sup>2</sup>+c<sup>2</sup>-ab-bc-ca=[(a-b)<sup>2</sup>+(b-c)<sup>2</sup>+(c-a)<sup>2</sup>]/2也容易证明。下面给出较难的n=5时的证明：
  <blockquote>
    假设a<=b<=c<=d<=e。令A=(a-b)(a-c)(a-d)(a-e), B、C、D、E的定义类似。<br>
    显然A,C,E>=0,B,D<=0.<br>
    比较|A|和|B|：<br>
    因为|a-b|=|b-a|,|a-c|>=|b-c|,|a-d|>=|b-d|,|a-e|>=|b-e|<br>
    所以|A|>=|B|<br>
    所以A+B>=0<br>
    同理D+E>=0<br>
    又因为C>=0，所以A+B+C+D+E>=0，即Fan(5)>=0恒成立。
  </blockquote>
<script>detail 1121,"Random的问题"</script>
　　const即可。不要忽略b=0的情况。
<script>detail 1122,"乐队"</script>
　　见加强版<a href=#1146>1146</a>。
<script>detail 1133,"难题"</script>
　　真是一道难题，要用到<font color=blue><b>棋盘多项式</b></font>。另外，我把1的个数的上限定为20的时候，RE216了，定为25才AC。<p>
　　<font color=blue><b>什么是棋盘多项式？</b></font><br>
　　棋盘多项式是一个关于x的多项式，式中n次项的系数表示在棋盘上放置n个棋子，且无任意两个棋子同行或同列（称“互不冲突”）的方法数。例如在棋盘<img src=img_vol2/1133_1.gif>上，放置0个棋子且互不冲突的方法数为1，放置1个棋子且互不冲突的方法数为3，放置2个棋子且互不冲突的方法数为1，放置3个棋子且互不冲突的方法数为0，那么棋盘<img src=img_vol2/1133_1.gif>的棋盘多项式就是x<sup>2</sup>+3x+1，记作R(<img src=img_vol2/1133_1.gif>)=x<sup>2</sup>+3x+1。<p>
　　<font color=blue><b>怎样计算棋盘多项式？</b></font><br>
　　显然对于空棋盘，R( )=1。对非空棋盘A，任意选定一个格子g，设从A中去掉g及所有与g同行或同列的格子后剩余的棋盘为A1，从A中仅去掉g后剩余的棋盘为A2，则R(A)=xR(A1)+R(A2)。<br>
　　例如：R(<img src=img_vol2/1133_1.gif>)<br>