vol2.htm

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· HTM 代码 · 共 446 行 · 第 1/5 页

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>