vol1.htm

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

<SCRIPT>detail 1074,"镜子迷宫"</SCRIPT>
 
　　本题数据范围很小（这是当然的），所以可以用分层图BFS解决。<BR>　　分层图的每一层对应着所有镜子的一个状态。不妨用二进制给每个状态编号：假设共有5个镜子，其中3、5号镜子被旋转了，则可用10100<SUB>2</SUB>=20<SUB>10</SUB>表示这个状态。于是，我们首先需要求出在每一层中，有哪些位置是不可到达的。这一过程很简单：在确定每个镜子的方向后，从每个发射器出发，把不可到达的位置依次做上标记即可。<BR>　　然后，从初始层的起点出发，进行BFS。扩展队列有两种方法：一是向四个方向之一前进一步，二是旋转某个镜子，即进入另一层。假设原来在第10100<SUB>2</SUB>层，旋转了第2个镜子，那么就来到了第10100<SUB>2</SUB> 
xor 00010<SUB>2</SUB>=10110<SUB>2</SUB>层。如果搜到了任一层的终点，则成功。
<SCRIPT>detail 1075,"一道简单题-版本2"</SCRIPT>
 　　A <B>simple</B> prob isn't usually an <B>easy</B> 
prob.<BR>　　首先提出一个性质：如果某一段开头一部分的和&lt;=0，那么把这一段删去后，剩余部分的和不会比原来小。<BR>　　设置两个指针p和i，p分别指向累加段的左端的前一位置，i指向累加段的右端。再设一个变量s，保存当前的累加和。初始时，p=0，i=l1，s=前l1个数之和。然后将i不断移直至n。记i-l1=j。对于i的每一个位置，第j个数以后的数是必须取的，而第j个数及以前的数都是可取可不取的（以下称第j个数及以前的数为<B>自由段</B>）。若自由段开头某一段的和&lt;=0，那么这一段就可以删去了。因此可另开一个累加器s0，每次把i后移一个位置，在s上加上第i个数，在s0上加上第j个数。若某时刻s0&lt;=0，则p:=j;dec(s,s0);s0:=0。<BR>　　但我们又遇到了一个问题：我们只有在自由段的开头有一段的和&lt;=0时才缩短累加段，那么如果累加段的长度已经达到了l2，而自由段开头任一段的和均为正值怎么办？当i再后移时，必须删掉自由段开头的一部分了！当然，我们还是希望删掉部分的和越小越好。那么怎么知道加到哪里的和最小呢？<BR>　　我们不再使用累加器s0，而是把它换成两个队列a和b。队列中存储的是把自由段分成的若干段，a[x]表示一段的和，b[x]表示一段的结束位置。下面用r表示队尾。i每后移一个位置，就往s上累加第i个数，同时把第j个数连同它的位置一同放到队尾：inc(r);a[r]:=第j个数;b[r]:=j。若a[r]&lt;=0，那么： 

<UL>
  <LI>若队列中只有一段，那么这一段就是自由段开头的一段，因为它的和&lt;=0，故把它删去即可。 
  <LI>若队列中不只这一段，那么可以把这一段与上一段合并：inc(a[r-1],a[r]);b[r-1]:=b[r];dec(r)，因为反正这一段的和&lt;=0，若删掉最后这一段之前的所有段，不如把这一段一起删掉。重复合并直至队列中只剩一段或a[r]&gt;0为止。</LI></UL>　　删除某一段时，令p为这一段的b值，并从s中减去这一段的和。比较i在每个位置时的s值，其中最大值就是答案。<BR>　　这种算法解决了累加段长度达到l2时，自由段开头没有和&lt;=0的一段的问题：因为这时队列中所有段的a值均为正，所以仅删第一段的损失最小。此算法的时间复杂度为O(n)，优于<A 
href="http://purety.jp/akisame/oi/TJU/vol1.htm#1071">版本1</A>中所述。<BR>　　然而现在内存上还有一个严峻的问题：每个队列的大小最大可能为n，开两个大小为n的longint数组就要耗用4*300000*2=2400KB的内存，MLE了。也许你会想：b数组存放的是位置，它的大小不会超过n，因此存储每个数用3个字节就够了；而题目中说中间结果及最后结果绝对值都不超过100000，a数组每个数用3个字节似乎也行。但实际上本题可以只开一个数组的：对队列中的每一段，若它的长度为1，那么它的b值不必存储，可利用上一段的b值加1间接得出（“第一段的上一段的b值”就是p），因此队列中只存它的a值；若它的长度&gt;1，则只能把a、b两值都存下（我的程序中把b值放在前面）。那么怎么区分队列中的值哪些是a值，哪些是b值呢？注意到所有的a值都是正的（除非队列中只有一段），因此把所有的b值存为它的相反数即可。这样做以后，长度为1的段在队列中占用一个longint，更长的段占用2个longint，也就是说总共只需n个longint。尽管这样做队列的操作会麻烦一些。程序请见ac1075a.pas。
<P>　　P.S.楼天城大牛有不用数组的算法，程序运行的时间也只有我的1/3——25ms左右。他是怎样做的我就不知道了(-_-b)
<P>　　<FONT 
color=blue><B>一种更简单的O(n)算法：</B></FONT><BR>　　考虑前i个数的和——部分和s[i]。把s[i]-s[j]中的i看作阶段，j看作决策。开一个决策队列，使队列中的决策具有部分和递增的性质。当处理到第i个数时，把过时(i-j&gt;l2)的决策从队首删除，并把新产生的决策(j=i-l1)放到队尾。若决策部分和的递增性被破坏，即倒数第二个决策优于最后一个决策，则倒数第二个决策永远不会最优。不断删除倒数第二个决策直至部分和递增性成立。这时队首决策为当前最优决策。<BR>　　ac1075b.pas存放了这个算法的程序。空间问题我是采用以3个字节表示一个数的方法解决的，因为这样编程复杂度较低。
<SCRIPT>detail 1077,"挑战"</SCRIPT>
 
　　首先算出彩虹可以挨打的次数a和猫老大可以挨打的次数b。<BR>　　比较容易想到的算法是DP：设f[a,b]为猫老大的胜率，则f[a,b]=(f[a,b-1]+f[a-1,b])/2，边界情况为f[0,x]=1，f[x,0]=0（x为正整数）。但是，a和b的最大值均为32767，在极端情况下DP会超时。<BR>　　然后想到组合的方法。猫老大若想取胜，则在前a+b-1个回合中，他至少要进攻a次。那么猫老大的胜率=<IMG 
src="vol1.files/1077_1.gif">。之所以化成第二种形式是为了方便计算，是因为第二种形式中和式的每一项的计算过程中只用了乘除法，可以用对数计算，而结果不超过1，可以直接相加。另外，不必每个组合数都重新计算，计算一个组合数时，在上一个的基础上乘以一个数再除以一个数即可。这样设计出的算法是线性的，虽然每次运算慢了点。
<SCRIPT>detail 1079,"赌博游戏"</SCRIPT>
 
　　典型的博弈问题，寻找猫的必败态。显然，0是必败态。观察每次可以拿的黄金的块数，发现它们都不能被3整除，因此，3的倍数都是必败态。因此，如果开始时黄金块数是3的倍数，则王胜，否则猫胜，第一次拿走黄金块数除以3的余数即可。因为10 
mod 3=1，所以求一个数除以3的余数只要把所有数位相加，这个和除以3的余数就是原数除以3的余数。
<SCRIPT>detail 1080,"礼物"</SCRIPT>
 
　　枚举左右两边（不要忘了整块布的左右边界），然后在左右两边确定的竖条中用扫描线法找能切出的高度最大的手绢。可在预处理中把所有的上下边排一下序，做扫描线时直接利用。
<SCRIPT>detail 1081,"猫老大数"</SCRIPT>
 
　　先用预处理求出sqrt(maxlongint)以内的质数表。对一个给定的数n，若n正好是某个质数的平方，那么它是一个猫老大数。以下讨论n不是某质数平方的情况： 

<UL>
  <LI>一个猫老大数分解质因数后的形式为n=p*q(p&lt;q)，那么一定有p在2至sqrt(n)的范围内，而q在此范围外； 
  <LI>若n不是猫老大数，则： 
  <UL>
    <LI>n可能等于1，这时n在2至sqrt(n)范围内无质因数； 
    <LI>n可能本身就是质数，这时n在2至sqrt(n)范围内亦无质因数； 
    <LI>n有多于2个（不是2种）质因数，这时n在2至sqrt(n)范围内的质因数必然多于1个（不是1种）。这点可由反证法证明：假设n在2至sqrt(n)范围内的质因数只有1个，那么其余的2个或2个以上质因数就都大于sqrt(n)，其积必大于n，而是这不可能的。</LI></UL></LI></UL>　　由上可以得出不是质数平方的n是猫老大数的充要条件：对所有2至sqrt(n)的质数p，累加n中因数p的个数。若累加和恰为1，那么n是猫老大数，否则不是。
<SCRIPT>detail 1082,"最远距离点对"</SCRIPT>
 
　　首先，距离最远的两个点一定都在输入的点的凸包上。简证如下：设距离最远的两个点为A和B，旋转图形使B点位于A点正上方。如果还有比B点更高的点C，那么AC一定大于AB，这与AB距离最远矛盾。所以B点一定是最高点，也就一定在凸包上。同理可证A点也一定在凸包上。<BR>　　TJU上的数据很弱，所以求出凸包以后，枚举凸包上的点对就可以AC了。但是，当输入的点全部分布在凸包上时，用枚举法就会超时了。下面介绍一种“对踵点法”，求凸包以后的步骤的时间复杂度仅为O(n)。<BR>　　先给出“<B>对踵点</B>”的定义：如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。下面将证明最远距离点对一定是一对对踵点。<BR><IMG 
src="vol1.files/1082_1.gif" align=right> 
　　观察图1，设∠1+∠2≤180°，∠3+∠4≤180°。那么如果∠1≥∠4，则由于∠1+∠2≤180°，一定可过B、E作两条平行线使边AB落在其中一条上；反之，则可过B、E作两条平行线使DE落在其中一条上。也就是说，当一条线段截凸包所成的两组“同旁内角”之和均不超过180°时，这条线段的两个端点是一对对踵点。因此，若一条线段的两个端点不是对踵点，则必有一组同旁内角之和大于180°。<BR><IMG 
src="vol1.files/1082_2.gif" align=right> 
　　再观察图2。因为有一组同旁内角之和大于180°，所以这两个角中必有一个角大于90°（不妨设∠ABE&gt;90°）。这种情况下显然有AE&gt;BE，因此BE不是最远距离点对。也就是说，不是对踵点的点对一定不是最远距离点对，所以最远距离点对一定是对踵点。<BR>　　很显然地，过一对对踵点一定可以作两条平行线，使凸包的一条边落在一条直线上。因此，我们设两个指针，一条指向凸包的某条边，另一个指针指向离这条边最远的点。这条边的两个端点与这个点都是对踵点，因此都可能是最远距离点对。按顺序移动边指针并相应地移动点指针，当两个指针绕凸包转了一圈以后，答案就出来了。
<SCRIPT>detail 1084,"n因子最小正整数"</SCRIPT>
 
　　谢谢<B>Waterfish</B>指出我贪心算法的错误。其实这个题的正宗解法还是搜索。<BR>　　把一个数（大于1）分解质因数：a=p<SUB>1</SUB><SUP>k<SUB>1</SUB></SUP>*p<SUB>2</SUB><SUP>k<SUB>2</SUB></SUP>*...*p<SUB>n</SUB><SUP>k<SUB>n</SUB></SUP>，则a的约数个数为(k<SUB>1</SUB>+1)*(k<SUB>2</SUB>+1)...*(k<SUB>n</SUB>+1)。显然，在约数个数相同的情况下，要使a最小，应有k<SUB>1</SUB>&gt;=k<SUB>2</SUB>&gt;=...&gt;=k<SUB>n</SUB>。因此，我们可以搜索每个质因数的指数，把上面的不等式当作剪枝条件。质因数只需用前trunc(log<SUB>2</SUB>100000)=16个即可。<BR>　　搜索出n因子最小正整数的质因数分解式后，剩下的就是高精度乘方和乘法了。计算乘方时，不要一个一个地把指数个底数相乘，这样做太慢。比较快的方法是二分递归，比如计算2<SUP>9</SUP>，可以这样：2<SUP>9</SUP>=(2<SUP>4</SUP>)<SUP>2</SUP>*2，其中2<SUP>4</SUP>=(2<SUP>2</SUP>)<SUP>2</SUP>，而2<SUP>2</SUP>=(2<SUP>1</SUP>)<SUP>2</SUP>，2<SUP>1</SUP>为已知。<BR>
<SCRIPT>detail 1085,"递增序列"</SCRIPT>
　　记输入序列为s，其长度为l。用nonzero[i]表示s[i..l]中第一个非零数的位置，规定s[l]=l。<BR>　　既然要求最后一个数最小，那么就从l 
downto 1枚举最后一个数开始的位置，设当前枚举到k。左边的序列用DP解决。next[i]的含义如下：
<UL>
  <LI>如果在第i个数字处开始不是最后一个数，那么next[i]表示下一个数开始的位置；
  <LI>如果在第i个数字处开始的数是最后一个数，则next[i]=l+1；
  <LI>如果自第i个数字起的序列无法划分，则next[i]=0。</LI></UL>从k-1 downto 
1枚举i，依次计算next[i]。next[i]应满足的条件是：
<OL>
  <LI>next[next[i]]&gt;0，即从next[i]开始的序列可以划分；
  <LI>s[i..next[i]-1]表示的数小于s[next[i]..next[next[i]]-1]表示的数，即严格递增；
  <LI>next[i]尽可能大。</LI></OL>因此可从k downto 
i+1依次枚举next[i]，一旦有某个next[i]满足前两个条件，则next[i]就已算出；若k downto 
i+1的所有值都不满足前两个条件，则next[i]=0。若最后next[1]不为0，说明有解，按图索骥地输出，否则dec(k)，继续循环。<BR>　　但若完全按照上述方法来做，程序在遇到3203400999这个数据时会输出3,203,400,999，而显然最优解应是320,340,0999。也就是说，此程序在枚举k时并没有考虑到前导的0。为解决这个问题，我们在枚举i时加上一点判断：如果从s[i]到s[k-1]的序列全为数字0，即nonzero[i]=k，那么直接令next[i]=l+1，否则再按上文所述计算next[i]。而在s[k]='0'时，直接跳过此次循环即可。<BR>　　枚举计算next[i]时还有一点优化：初值不必一律取k。因为第一个数的位数无论如何不会超过最后一个数的位数，因此初值取k与nonzero[i]+l+1-k的较小值即可。<BR>　　经过这两点改进，发现对于全0序列程序不会给出任何输出。这是因为任一s[k]均等于0，循环均被跳过。因此对于全0序列要特殊处理。
<SCRIPT>detail 1087,"垃圾陷阱"</SCRIPT>
 
　　在以下的叙述中，g[i].time、g[i].life、g[i].height分别表示第i个垃圾下落的时间、吃下后可以增加的寿命、垫高的高度；update(a,b)表示if 
b&gt;a then 
a:=b。<BR>　　这道题可以用DP解决。用l[i,j]表示掉下来i个垃圾后，卡门爬上的高度为j时她最长的寿命。显然l[0,0]=10。对于任一个状态l[i-1,j]，若l[i-1,j]&gt;=g[i].time，说明这个状态的卡门能够坚持到下一个垃圾下落。在这种情况下，按以下两种方法处理第i个垃圾，即进行状态转移：
<OL>
  <LI><B>吃掉第i个垃圾</B>，即update(l[i,j],l[i-1,j]+g[i].life)；
  <LI><B>用第i个垃圾来垫高</B>。令t=j+g[i].height，即把第i个垃圾用来垫高后卡门爬上的总高度。如果t&gt;=d，则卡门于g[i].time时爬了出来，否则update(l[i,t],l[i-1,j])。</LI></OL>　　若首次遇到某一个l[i,0]一次也没有赋值，说明卡门不可能坚持到第i个垃圾下落，则她最多可以存活的时间为l[i-1,0]（即把前i-1个垃圾全吃掉后的寿命）。<BR>　　注意到在计算l数组的第i行时只用到了第i-1行，因此l数组可用滚动数组来实现。
<SCRIPT>detail 1090,"Symbol树"</SCRIPT>
 　　首先澄清一下多叉树的概念：多叉树的子树是有顺序的。<BR>　　用f[n]表示有n个结点的多叉树的数目，规定f[0]=1，则<IMG 
src="vol1.files/1090_1.gif" align=absMiddle>，其中i表示第一棵子树中结点的数目。
<SCRIPT>detail 1094,"统计三角形个数"</SCRIPT>
 
　　首先看到题目中顶点的编号方式不利于解题，故将其转换为坐标表示法，如原来的顶点8转换为第4行第2列，即(4,2)。转换方法如下：设顶点x的上方有t行，则t是方程t*(t+1)/2=x-1的正数解的整数部分（体会一下方程右边-1的巧妙性）。于是，顶点x便转换为(t+1,x-t*(t+1) 
div 
2)。<BR>　　下面进入正题。读入被删边的时候，把这些边分为两类：水平的和斜的。在以下的叙述中，把朝上的三角形的上顶点及朝下的三角形的下顶点叫做三角形的<B>顶点</B>。依次统计顶点为(x,y)(1&lt;=y&lt;=x&lt;=n)的三角形。<BR>　　在统计顶点为(x,y)的三角形时，设两个变量u、d，分别表示三角形顶点的对边所在行号的最小值和最大值，初始时u=min{y-1,x-y}，d=n。然后根据被删边来确定以(x,y)为顶点的三角形中哪些仍然完整： 

<OL>
  <LI>假若某一条斜的被删边正好处于从(x,y)出发的两条斜直线上，那么顶点的对边在这条被删边以上（如果它在(x,y)的上方）或以下（如果它在(x,y)的下方）的三角形都不复存在了。因此，使用斜的被删边来缩小u~d的范围。 

  <LI>现在，u~x-1和x+1~d的每一个值都对应着一个以(x,y)为顶点的三角形。下面就检查一下这些三角形是否被水平的被删边破坏掉。最后剩下的三角形就是图中存在的三角形，累计即可。
  <UL></UL>
  <SCRIPT>detail 1095,"Feli的生日礼物"</SCRIPT>
  　　再用一遍<A 
  href="http://purety.jp/akisame/oi/TJU/vol1.htm#1014">1014</A>中的化学术语：“一个2跟一个5反应生成一个0，因为2过量，所以照5算”。也就是说，因数5应是我们关注的对象。<BR>　　举个例子来说明我的算法：假设要计算33!，首先把1至33的不是5的倍数的数的末位数相乘，取末位数。而剩下没有乘的就是5,10,15,20,25,30，共6个（33 
  div 
  5=6）。把6个约数5提出来留到最后一起乘，剩下的又是计算6!，于是便看出这是一个递归过程，这也就是算法的框架。<BR>　　具体实现中有以下几个小窍门： 
  <UL>
    <LI>计算1至n的不是5的倍数的数之积的末位数可以const，因为n的末位数与积的末位数之间存在对应关系。当然，n=0和n=1的情况例外。 
    <LI>因为乘以5之前和之后的末位数都是偶数，所以乘以5的效果与乘以8相同，即：2*5-&gt;6，4*5-&gt;2，6*5-&gt;8，8*5-&gt;4。 

    <LI>显然这道题需要用高精度。不要图省事而用字符串，因为字符串与数组相比，delete(s,1,1)这个操作太费时间。而且，我的经验表明，用字符串会莫名其妙地WA掉。</LI></UL>
  <SCRIPT>detail 1099,"破解平方数"</SCRIPT>
  　　子集中元素之积为平方数，也就是对于任一质数p，子集中每一个数包含p的个数之和为偶数。用布尔变量b[i]表示子集是否包含第i个数，布尔变量a[x,i]表示第i个数是否含有奇数个第x个质数。可以列出以下布尔方程组： 

  <BLOCKQUOTE>a[1,1] and b[1] xor a[1,2] and b[2] xor ... xor a[1,m] and b[m] 
    = false<BR>a[2,1] and b[1] xor a[2,2] and b[2] xor ... xor a[2,m] and b[m] = 
    false<BR>... ...<BR>a[t,1] and b[1] xor a[t,2] and b[2] xor ... xor a[t,m] 
    and b[m] = false 
  </BLOCKQUOTE>其中b[i]是未知数。本题的答案，就是上述方程组的解的组数减1（空集不符合题意）。注意到所有方程的右边均为false，因此这个方程组不会无解。<BR>　　那么如何求得这个方程组的解的组数呢？可以用高斯消元法。依次消去每一个未知数。消未知数b[i]时，若它的所有系数均为false，那么它是一个<B>自由变量</B>，也就是说，它是取true还是取false都可以，同时它已经不存在了，不必消去；否则找一个b[i]的系数不为false的方程，用它与其它每一个方程进行异或运算，再把这个方程本身删除，这样就消去了b[i]。因为当自由变量取特定值时，每个非自由变量都可由自由变量根据消去这个非自由变量时与其它方程异或的方程算出，所以方程组的解的组数就是2^自由变量个数。 
<!-- START HOME FREE FOOTER CODE --></OBJECT></LAYER>
  <DIV></DIV></SPAN></STYLE></NOSCRIPT></TABLE></SCRIPT></APPLET>
  <CENTER></CENTER>
  <DIV class=ad_text align=center>
  <SCRIPT type=text/javascript><!--
google_ad_client = "pub-7093259457636557";
google_ad_width = 234;
google_ad_height = 60;
google_ad_format = "234x60_as";
google_ad_type = "text_image";
//2007-10-01: 2style(2style.net)
google_ad_channel = "5598176498";
google_color_border = "191919";
google_color_bg = "FFFFFF";
google_color_link = "0000FF";
google_color_text = "000000";
google_color_url = "008000";
google_ui_features = "rc:6";
//-->
</SCRIPT>

  <SCRIPT src="vol1.files/show_ads.js" type=text/javascript>
</SCRIPT>
  <A href="http://2style.net/" target=_blank><IMG height=1 alt=2style.net 
  src="vol1.files/fstats.htm" width=1 border=0></A> </DIV><!-- END HOME FREE FOOTER CODE --></LI></OL></BODY></HTML>