tongji online judge solutions b.htm

同济大学 online 在线题库题目及解题报告完整版

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>
  </TR></TBODY></TABLE>
<SCRIPT>detail 1100,"勇闯黄金十二宫……白羊宫"</SCRIPT>
　　四件圣衣分别计算，相加即可。把一件圣衣上所有洞的破损程度值分成和尽可能接近的两组，则和较大的一组的和就是修补这件圣衣所需的最少时间。这个时间的求法可参看<A 
href="http://purety.jp/akisame/oi/TJU/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&gt;2)的循环（其中的人按顺序编号为1..n），可以构造这样一种交换方法： 

<UL>
  <LI>第1个时间单位，第n个人不动，第i(1≤i≤n/2)个人与第n-i个人交换斧子； 
  <LI>第2个时间单位，第i(1≤i≤(n+1)/2)个人与第n+1-i个人交换斧子。</LI></UL>　　所以最短交换时间为2。因此，若最大循环长度为1，则总的最短交换时间为0；若最大循环长度为2，则总的最短交换时间为1；否则为2。
<SCRIPT>detail 1103,"勇闯黄金十二宫……巨蟹宫"</SCRIPT>
 　　这道题与<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#1084">1084</A>是极为类似的。同样是搜索每个质因数的指数，用同样的公式计算约数个数，用同样的不等式剪枝。此题与<A 
href="http://purety.jp/akisame/oi/TJU/vol1.htm#1084">1084</A>相比较简单的一点是，虽然在试乘的过程中数值会超出longint甚至cardinal的范围，但不必使用高精度，用int64即可。
<SCRIPT>detail 1107,"勇闯黄金十二宫……天蝎宫"</SCRIPT>
 　　<B>气死人的题：题目中说n&lt;=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&gt;=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&lt;=b&lt;=c&lt;=d&lt;=e。令A=(a-b)(a-c)(a-d)(a-e), 
  B、C、D、E的定义类似。<BR>显然A,C,E&gt;=0,B,D&lt;=0.<BR>比较|A|和|B|：<BR>因为|a-b|=|b-a|,|a-c|&gt;=|b-c|,|a-d|&gt;=|b-d|,|a-e|&gt;=|b-e|<BR>所以|A|&gt;=|B|<BR>所以A+B&gt;=0<BR>同理D+E&gt;=0<BR>又因为C&gt;=0，所以A+B+C+D+E&gt;=0，即Fan(5)&gt;=0恒成立。 
</BLOCKQUOTE>
<SCRIPT>detail 1121,"Random的问题"</SCRIPT>
　　const即可。不要忽略b=0的情况。
<SCRIPT>detail 1122,"乐队"</SCRIPT>
 　　见加强版<A href="http://purety.jp/akisame/oi/TJU/vol2.htm#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="Tongji Online Judge Solutions B.files/1133_1.gif">上，放置0个棋子且互不冲突的方法数为1，放置1个棋子且互不冲突的方法数为3，放置2个棋子且互不冲突的方法数为1，放置3个棋子且互不冲突的方法数为0，那么棋盘<IMG 
src="Tongji Online Judge Solutions B.files/1133_1.gif">的棋盘多项式就是x<SUP>2</SUP>+3x+1，记作R(<IMG 
src="Tongji Online Judge Solutions B.files/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="Tongji Online Judge Solutions B.files/1133_1.gif">)<BR>　　=xR(<IMG 
src="Tongji Online Judge Solutions B.files/1133_3.gif">)+R(<IMG 
src="Tongji Online Judge Solutions B.files/1133_2.gif">) 
（此步选定的是左上方的格子）<BR>　　=x(xR( )+R( ))+xR( )+R(<IMG 
src="Tongji Online Judge Solutions B.files/1133_3.gif">)<BR>　　=x(x+1)+x+x+1<BR>　　=x<SUP>2</SUP>+3x+1
<P>　　<FONT 
color=blue><B>棋盘多项式要怎么用？</B></FONT><BR>　　想象一个n*n的棋盘，输入中的1是棋盘的禁区。设禁区的棋盘多项式的i次项的系数为f<SUB>i</SUB>。在整个棋盘上放置n个棋子，至少有i个落入禁区的方法数为f<SUB>i</SUB>*(n-1)!。由容斥原理，在整个棋盘上放置n个棋子，无一落入禁区的方法数为<IMG 
src="Tongji Online Judge Solutions B.files/1133_4.gif" 
align=middle>。因此计算出禁区的棋盘多项式，问题就解决了。当然，需要用高精度。
<P>　　<FONT 
color=blue><B>复杂度问题！</B></FONT><BR>　　在计算有n个格子禁区的棋盘多项式的过程中，总共要计算多少个棋盘的棋盘多项式呢？感觉是2<SUP>n</SUP>个。这个复杂度无论是时间上还是空间上都是无法承受的。怎么办呢？其实什么也不用办，因为实际上计算的棋盘数不会超过2<SUP>n/2+1</SUP>。如果计算棋盘多项式时，每次都选定最上面一行的最左面一格，则这个上限会在棋盘上每列都有至少2个格子，且列与列之间没有格子同行，且对于任意两列a、b，a的最高格总是高于b的次高格时达到。假设棋盘共有m列，则在需计算的棋盘中，若第x列的最高格已经不存在了，则第1至x-1列的最高格必然也不存在了。故第1列的最高格存在的棋盘只有1（即2<SUP>0</SUP>）个，第1列的最高格不存在而第2列的最高格存在的棋盘有2<SUP>1</SUP>个（因为第1列除去最高格后的部分有存在与不存在两种可能），前2列的最高格不存在而第3列的最高格存在的棋盘有2<SUP>2</SUP>个（前2列除去最高格后的部分都可能存在或不存在）……m列的最高格都不存在的棋盘有2<SUP>m</SUP>个。也就是说，棋盘总数的上限大约为2<SUP>m+1</SUP>。因为对这种棋盘有m&lt;=n/2，故实际计算的棋盘数不会超过2<SUP>n/2+1</SUP>。在n&lt;=25时，这个复杂度在时间上是完全可以承受的，在空间上，若给每个棋盘编一个号，使用哈希表存储棋盘多项式，也没有问题。
<P>　　本题使用了高精度、二进制编号、哈希表等多种算法和数据结构，对编程能力也是一个极好的锻炼。
<SCRIPT>detail 1136,"回家"</SCRIPT>
 　　把边当作点，点当作边，Dijkstra即可。
<SCRIPT>detail 1137,"赌场的规矩"</SCRIPT>
 
　　很明显，这是一道图论题。首先构造一个图：每一个洞作为一个顶点，在某两个洞之间交换了几次，就在代表这两个洞的顶点之间连几条边。把最后可能藏有小球的洞对应的顶点叫做<B>可达</B>的顶点，其它顶点叫做<B>不可达</B>顶点。显然，可达顶点只存在于包含顶点1的连通分支中。以下的讨论都是针对包含1号顶点的连通分支。<BR>　　现在提出两个结论：
<P>　　<FONT 
color=blue><B>结论1：若顶点1到顶点x有一条经过3个或3个以上顶点的路径，则顶点x是可达的。</B></FONT><BR>　　<B>证明：</B>如果依次进行路径上的边所代表的操作，则显然小球最后会在x号洞里。我们只需让不在这条路径上的边（以下称作“多余边”）代表的操作全部成为空操作即可。<BR>　　而这一点是很容易做到的。以路径上有且只有3个顶点的情况为例。把这3个顶点分别记作A、B、C。当小球在A洞里时，可以进行B、C之间多余的边（如果有的话）所代表的操作，这时，这些操作全部为空操作。同理，当小球在B洞里时，可以使A、C之间的多余操作成为空操作；当小球在C洞里时，可以使A、B之间的多余操作成为空操作。与A相连但不与B、C相连的多余边所代表的操作可以在小球不在A洞时进行，只与B或C相连的多余边可同理处理。与A、B、C均不相连的多余边，则可以在任意时刻处理掉。证毕。