vol1.htm

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

    <TD>9
    <TD>13
    <TD>17
    <TD>25
    <TD>33
    <TD>41
    <TD>49
    <TD>65 
</TR></TBODY></TABLE>　　观察这个表，我们可以大胆地猜想g[i]的规律：<B>从1开始，加2次2，再加3次4，再加4次8，再加5次16……</B>这个猜想的证明过程过于琐碎，详细、严谨的步骤反而会妨碍理解，我只说一下大概思路：显然g[2]是用g[1]和f[1]算出来的。假设g[i]=g[j]*2+f[i-j]，那么g[i+1]=min{g[j+1]*2+f[i-j],g[j]*2+f[i-j+1]}，即把f或g的下标增加1。为什么呢？因为f和g两个数列都是增长的，而且增长得越来越快。如果在最优解的基础上让f的下标变大、g的下标变小，或是相反，结果不是不变就是变大。亲手模拟一下g的计算过程，就会发现，<B>g数列加2<SUP>k</SUP>的次数等于g数列加2<SUP>k-1</SUP>的次数与f数列加2<SUP>k</SUP>的次数之和。</B>由此可以得出上面的猜想。<BR>　　这个问题可以推广到m塔的情况。用a[i]表示m柱i盘时所需的移动次数，则a数列有这样一个规律：a[1]=1，以后依次有<IMG 
src="vol1.files/1034_1.gif">项比前一项大2<SUP>k</SUP>，其中k从1开始取整数值。
<SCRIPT>detail 1035,"撕邮票"</SCRIPT>
 
　　搜索、判重。判重时若保存整个图象比较每个格子则嫌慢，其实有一点小技巧：把每个图象看作一串二进制数，用一个数来存储这个图象每个格子的信息，再加上一个宽度就可以唯一地表示一个图象了。由于一个图象经翻转、旋转可得到8种形态，我们需要按某种规则只存储一个（如宽度取较长边，宽度一定时使二进制数最小）。这样既节省了时间，又节省了空间。
<SCRIPT>detail 1036,"序列函数"</SCRIPT>
 
　　用一个队列q来存储序列，初始时设q[0]=1。设三个头指针f1,f2,f3，分别对应于三个质数p1,p2,p3（假设p1&lt;p2&lt;p3）。头指针的初值均为0。每次取q[f1]*p1,q[f2]*p2,q[f3]*p3中的最小值，如果当前队列为空或它与当前队尾元素不同，则将其放进队列。无论是否放进队列，都将产生最小值的头指针加1。当队列达到所需的长度时，输出队尾元素。
<SCRIPT>detail 1037,"最短网络"</SCRIPT>
 　　赤裸裸的最小生成树模型。
<SCRIPT>detail 1038,"化学方程式"</SCRIPT>
 
　　思路极清晰：列多元一次方程组，用高斯消元法解。所谓高斯消元法，就是用一个含x<SUB>i</SUB>的方程（记为E<SUB>i</SUB>）与其它所有方程加减，消去其它方程中的x<SUB>i</SUB>，待解出x<SUB>1</SUB>至x<SUB>i-1</SUB>后，代入E<SUB>i</SUB>求x<SUB>i</SUB>。但编程极麻烦，具体来说，有下面几点提示或注意事项： 

<UL>
  <LI>跟<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1117">1117</A>一样，列方程时最好在整个反应式最左边加个'+'，倒着进行。 

  <LI>消元时若待消的未知数已不存在，则No solution。 
  <LI>消元时若未知数比方程多两个或两个以上，即方程过少，则No solution。 
  <LI>消到只剩一个未知数时，方程应当一个也不剩，否则，剩下的方程中均只含最后一个未知数，它只能等于0，这是不合题意的。简言之，方程过多时也是No 
  solution。 
  <LI>两个方程加减后不要忘了及时约掉各系数的最大公约数，以免过程中系数过大。 
  <LI>消元结束后，令x<SUB>1</SUB>=1，利用各E<SUB>i</SUB>依次推出各x<SUB>i</SUB>。若碰到某个x<SUB>i</SUB>为分数，则将x<SUB>1</SUB>至x<SUB>i-1</SUB>均乘以x<SUB>i</SUB>的分母。若碰到某个x<SUB>i</SUB>&lt;=0，则No 
  solution。</LI></UL>
<SCRIPT>detail 1039,"核电站问题"</SCRIPT>
　　DP。用f[n]表示n个坑时的放法数，则有<BR>　　f[0]=1<BR>　　f[n]=f[n-1]*2 
(1&lt;=n&lt;m)<BR>　　f[n]=<IMG src="vol1.files/1039_1.gif" align=absMiddle> 
(n&gt;=m)<BR>　　注意到f[n-1]=<IMG src="vol1.files/1039_2.gif" align=absMiddle> 
(n&gt;m)，两式相减得f[n]-f[n-1]=f[n-1]-f[n-m-1] 
(n&gt;m)。于是可以化简最后一个方程：<BR>　　f[m]=f[n-1]*2-1<BR>　　f[n]=f[n-1]*2-f[n-m-1] (n&gt;m)
<SCRIPT>detail 1040,"N的倍数"</SCRIPT>
 
　　妙极了的算法：最短路。<BR>　　把自然数除以N的每个可能余数，即0~N-1，分别看成一个结点。若一个数字d是可用的，那么对任一顶点x，连一条从x到(x*10+d) 
mod 
N的有向边，边上标有数字d。然后把结点0看成两个结点0和0'，用简单的BFS找一条从0到0'的最短路，路径上所有边上标的数字连起来就是答案。<BR>　　用BFS似乎只能保证答案的位数最少而不能保证值最小，其实不然。只要在扩展结点时按边上所标数字从小到大的顺序进行，答案的值也一定是最小的。
<SCRIPT>detail 1041,"战略游戏"</SCRIPT>
 
<UL>
  <LI><FONT 
  color=blue><B>树型DP</B></FONT>（我的算法）：首先建树，任选一个结点为根。设要看守住以x为根的子树中所有边，x处有士兵时需要的最少士兵数为yes[x]，x处无士兵时需要的最少士兵数为no[x]。自下而上地计算每个结点的yes值和no值：一个结点的yes值等于它所有子树的yes值与no值的较小值之和再加1；no值等于它所有子树的yes值之和。根结点的yes值和no值中的较小值即为答案。 

  <LI><FONT 
  color=blue><B>贪心</B></FONT>：找出所有度为1的结点，把与它们相连的结点上都放上士兵，然后把这些度为1的结点及已放上士兵的结点都去掉。重复上述过程直至树空为止。 

  <LI><FONT color=blue><B>二分图最小覆盖</B></FONT>（by 
  HybridTheory）：把树看成一个二分图，奇数层的结点放到一边，偶数层的结点放到一边，然后求这个二分图的最小覆盖数（等于最大匹配数）。</LI></UL>
<SCRIPT>detail 1042,"替换问题"</SCRIPT>
　　好奇异的算法，不知<B>Cocoran</B>大牛是怎么想出来的。<BR>　　用S<SUB>i</SUB>表示a<SUB>1</SUB>至a<SUB>i</SUB>的和，S'<SUB>i</SUB>表示b<SUB>1</SUB>至b<SUB>i</SUB>的和。下面研究三种操作对各S<SUB>i</SUB>的影响： 

<UL>
  <LI>对a<SUB>i-1</SUB>、a<SUB>i</SUB>、a<SUB>i+1</SUB>(1&lt;i&lt;n)进行操作，相当于交换了S<SUB>i-1</SUB>和S<SUB>i</SUB>。 

  <LI>对a<SUB>n</SUB>、a<SUB>1</SUB>、a<SUB>2</SUB>进行操作，相当于把所有的S<SUB>i</SUB>都减去a<SUB>1</SUB>，再交换S<SUB>1</SUB>与S<SUB>n</SUB>。 

  <LI>对a<SUB>n-1</SUB>、a<SUB>n</SUB>、a<SUB>1</SUB>进行操作，相当于把所有的S<SUB>i</SUB>都加上a<SUB>n</SUB>，再交换S<SUB>n-1</SUB>与S<SUB>n</SUB>。</LI></UL>　　于是我们看出，无论进行多少次怎样的操作，结果只是把所有的S<SUB>i</SUB>都加上或减去了某一数值，然后进行了若干次交换。于是把a<SUB>1</SUB>至a<SUB>n</SUB>、b<SUB>1</SUB>至b<SUB>n</SUB>分别排序，若所有的S<SUB>i</SUB>-S'<SUB>i</SUB>均相等，则YES，否则NO。
<SCRIPT>detail 1043,"黑白棋"</SCRIPT>
 　　简单深搜。只是面对某一个棋局时，若轮到的一方无处下子，要妥善处理pass的情况。
<SCRIPT>detail 1046,"立方馅饼"</SCRIPT>
 
　　把x+y+z的为奇数的格子染成黑色，x+y+z为偶数的格子染成白色。若n为奇数，则Yes的充要条件是起点与终点均为黑色；若n为偶数，则Yes的充要条件是起点与终点异色。
<SCRIPT>detail 1047,"自然数序列"</SCRIPT>
 
　　每次取数列的后四项，让两头两项为正，中间两项为负（当然反过来也行），这样这四项的和就是0了，将这四项删去。这样做到最后最多只剩3项。若剩3项或一项也不剩（即n 
mod 4=3或0），则答案为0，否则答案为1（因为添加负号不改变和的奇偶性，而这时所有数的和为奇数，故答案无法达到0）。
<SCRIPT>detail 1048,"Tom的烦恼"</SCRIPT>
 
　　用best[t]表示在时间t以前Tom得到的最大加工费。按时间递增的顺序计算best数组。对每个best[t]，首先令其为上一个时间的best值，然后对于每一个在时间t结束的工作（设其开始时间为s，加工费为m），比较best[s]+m与best[t]的值，取大者。<BR>　　由于时间的数值可能远远大于工作的数量，因此最好首先对时间进行离散化。
<SCRIPT>detail 1049,"砝码问题"</SCRIPT>
 　　思路参看<A href="http://purety.jp/akisame/oi/TJU/vol1.htm#1017">1017 
石子归并</A>问题。本题的大数据规模版本就是<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#1166">1166 背包问题</A>。
<SCRIPT>detail 1057,"办公室失窃案"</SCRIPT>
 　　把每个时间段看成一条线段，用扫描线法找到被n条线段同时覆盖的区间，输出。当然要注意输入输出的细节。
<SCRIPT>detail 1058,"地板覆盖问题"</SCRIPT>
 
　　老老实实地按题目说的顺序判断，即先判断所有砖中是否有交叉，再判断所有砖中是否有越界情况，最后判断地板是否全被覆盖。切不可看到第一块砖越界了就下结论，因为第二块和第三块可能交叉。两块砖(x1,y1)-(x2,y2)与(x3,y3)-(x4,y4)交叉的充要条件是(x1&lt;x4) 
and (x3&lt;x2) and (y1&lt;y4) and 
(y3&lt;y2)。第三步判断砖是否盖满地板时，可以累加所有砖的面积，若这个和与地板的面积相等，则盖满。
<SCRIPT>detail 1059,"数的计数"</SCRIPT>
 　　用f[n]表示最后一个数是n时，可以构造出的数的总数。规定f[0]=1，则显然有f[n]=f[0]+f[1]+...+f[n div 
2]。<BR>　　但若直接使用这个方程，则会既TLE又MLE。注意到右边其实是f数组开头若干个元素的和，因此可开一个s数组，用s[n]来存储f[0]至f[n]的和。这样时间上显然没有问题。实际上，现在f数组已经不必要了，因为用s数组可写出如下状态转移方程：s[n]=s[n-1]+f[n]=s[n-1]+s[n 
div 2]。当读入n时，输出s[n div 
2]即可。<BR>　　结果很大，高精度是当然的。可以用3个int64来存储一个数。这里我们看到用s数组代替f数组同样解决了MLE的问题，因为s数组的大小只有f数组的一半，题目允许的内存不能容纳f数组，却恰好可以容纳s数组。
<SCRIPT>detail 1060,"方程的解数"</SCRIPT>
 　　查了一下NOI的原题，发现有一个重要条件，题目中落掉了：<B><FONT 
size=4>Σ</FONT>Ki*M<SUP>Pi</SUP>&lt;=maxlongint</B>。这个条件告诉我们，无论每个x取什么值，结果不会超过longint范围，因此不必考虑int64或是高精度之类的问题。另外，由于150<SUP>5</SUP>&gt;maxlongint，所以P不会超过4。<BR>　　这道题只能用枚举法，其瓶颈显然在于计算速度。注意到乘幂运算需屡次进行，因此很自然地想到用预处理先计算出所有的乘幂值（只有150*4=600个而已）。然而这毕竟只是细节上的优化，本质的还在于找一个高效的算法。<BR>　　把方程的半数项移到右边。得到的新方程与原方程是相似的，只是右边不再为0。但是，每一边的项数不超过3，也就是说枚举量不超过150<SUP>3</SUP>=3375000，这个复杂度是完全可以承受的。我们可以枚举左边，用一个表将所有可能的结果及其出现次数存储起来，然后枚举右边，在表中查找右边结果的相反数，累加表中存储的出现次数即得到答案。现在的问题是：用什么表来存储结果呢？<BR>　　如果用有序表和二分查找的话，那么对300多万个数进行排序就需要好几秒，对同样多的数进行二分查找又需要同样多的时间，显然不可取。本题适用的数据结构是：<B>哈希表</B>。哈希函数很好找：设x为结果，那么hash(x)=abs(x) 
mod 
bigprime，其中bigprime为一个取定的大质数。这样，存储和查找就几乎都是线性的了。这样处理以后，算法的时间复杂度为O(M<SUP>3</SUP>)，带一个适中的常数系数。<BR>　　然而本题的内存限制是很紧的，哈希表这种耗内存的数据结构一不小心就会MLE。我的经验是： 

<UL>
  <LI>不要用指针，而用数组来模拟，因为指针本身就耗内存，而且分配、回收操作也浪费不少时间。至于处理冲突的问题，可以建立公共溢出区，即把冲突的元素统统放到公共溢出区中。 

  <LI>哈希表中无需存储原始的元素。假设原始元素为x，那么在hash表中只需存储x div 
  bigprime+ord(x&gt;0)。之所以要加入ord(x&gt;0)一项，是因为如果不加，-1和1就会变成同一个数0。经过这一变换，x的范围就由原来的longint变为integer（我的bigprime取的是999983），又省了大量内存。</LI></UL>
<SCRIPT>detail 1061,"堆栈计算"</SCRIPT>
　　题目中的表达式是一个树型结构，因此想到用树型DP解决这个问题。<BR>　　把在表达式中位置为i的字符代表的结点称作结点i。首先用递归的方法找到每个B结点的左孩子的位置。结点i的左孩子用child[i]表示，显然结点i的右孩子为i-1。<BR>　　用space[i]表示计算以i为根的子树所需的最少堆栈空间，swap[j,i]表示如果有大小为j的堆栈空间可用，计算以i为根的子树所需的最少交换次数。堆栈大小不同时，这个次数是不同的，例如...BB在堆栈空间为2时需要交换1次，而在堆栈空间为3时则一次也不需要。<BR>　　按堆栈空间的大小j划分阶段，j的初值为1，这时对每个.结点i，有space[i]=1，swap[1,i]=0；对每个B结点i，有space[i]=无穷大，swap[1,i]=无穷大，这里的无穷大表示还没有算出来。<BR>　　设表达式长为l，则当space[l]=无穷大时，j加1，进行下面的状态转移。从左到右依次处理每一个结点的space值和swap值。 

<UL>
  <LI><B>space值的计算</B>：如果一个B结点(i)的space值为无穷大，而它的两个孩子（a、b）的space值都已算出，且有一个小于j（不妨设space[a]&lt;j），那么令space[i]为j。这是因为可先利用大小为j的堆栈空间计算以b为根的子树，1个单位的堆栈空间被用来存储结果，而剩下的j-1个单位的堆栈空间足以计算以a为根的子树。 

  <LI><B>swap值的计算</B>：对于.结点，swap[j,i]显然为0。对于B结点(i，左右孩子分别为a、b)，则swap[j,i]=min{swap[j-1,i],swap[j,a]+swap[j-1,b],swap[j,b]+swap[j-1,a]+1}。注意最后一个元素，若先计算右子树，后计算左子树，则最后需交换两个结果，因此要加1。</LI></UL>　　注意到在计算swap数组的第j行时只用到了第j-1行，因此swap数组可用滚动数组来实现。
<SCRIPT>detail 1068,"商务旅行"</SCRIPT>
 
<TABLE align=right>
  <TBODY>
  <TR>
    <TD><IMG 
      src="vol1.files/1068_1.gif"><BR>处理结点10的时候并查集的情况<BR>（假设结点是按从左到右的顺序处理的）<BR>与10的LCA是10的结点集合：{10}<BR>与10的LCA是8结点集合：{8 
      9 11}<BR>与10的LCA是3的结点集合：{3 7}<BR>与10的LCA是1的结点集合：{1 2 5 6}<BR>不属于任何集合的结点：4 
      12 </TR></TBODY></TABLE>　　<FONT 
color=blue><B>感谢Faint.Wisdom讲解求最近公共祖先(LCA)的Tarjan算法！</B></FONT>下面是算法的详细讲解：<BR>　　首先，Tarjan算法是一种离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。而打乱这个顺序正是这个算法的巧妙之处。看完下文，你便会发现，如果偏要按原来的顺序处理询问，Tarjan算法将无法进行。<BR>　　Tarjan算法是利用并查集来实现的。它按DFS的顺序遍历整棵树。对于每个结点x，它进行以下几步操作： 

<UL>
  <LI>计算当前结点的层号lv[x]，并在并查集中建立仅包含x结点的集合，即root[x]:=x。 
  <LI>依次处理与该结点关联的询问。 
  <LI>递归处理x的所有孩子。 
  <LI>root[x]:=root[father[x]]（对于根结点来说，它的父结点可以任选一个，反正这是最后一步操作了）。</LI></UL>　　现在我们来观察正在处理与x结点关联的询问时并查集的情况。由于一个结点处理完毕后，它就被归到其父结点所在的集合，所以在已经处理过的结点中（包括x本身），x结点本身构成了与x的LCA是x的集合，x结点的父结点及以x的所有已处理的兄弟结点为根的子树构成了与x的LCA是father[x]的集合，x结点的父结点的父结点及以x的父结点的所有已处理的兄弟结点为根的子树构成了与x的LCA是father[father[x]]的集合……（上面这几句话如果看着别扭，就分析一下句子成分，也可参照右面的图）假设有一个询问(x,y)（y是已处理的结点），在并查集中查到y所属集合的根是z，那么z就是x和y的LCA，x到y的路径长度就是lv[x]+lv[y]-lv[z]*2。累加所有经过的路径长度就得到答案。<BR>　　现在还有一个问题：上面提到的询问(x,y)中，y是已处理过的结点。那么，如果y尚未处理怎么办？其实很简单，只要在询问列表中加入两个询问(x,y)、(y,x)，那么就可以保证这两个询问有且仅有一个被处理了（暂时无法处理的那个就pass掉）。而形如(x,x)的询问则根本不必存储。<BR>　　如果在并查集的实现中使用路径压缩等优化措施，一次查询的复杂度将可以认为是常数级的，整个算法也就是线性的了。<BR>　　另外，实现上还有一点技巧：树的边表和询问列表的存储可以用数组模拟的链表来实现。<BR>
<SCRIPT>detail 1071,"一道简单题-版本1"</SCRIPT>
　　用s[i]表示前i个数之和。从1到n枚举累加段的右端j，当j一定时，我们的问题就是找一个i(j-l2&lt;=i&lt;=j-l1)，使s[j]-s[i]最大，即s[i]最小。于是我们想到了堆。维护一个堆，使堆中任一对父子结点x,y（x为父结点），都有s[x]&lt;=s[y]。在右端枚举到j时，若j&gt;=l1，那么就把j-l1放到堆里。这时考察堆顶元素（记作i）：若i&lt;j-l2，那么现在i是不合法的，以后也不会合法，把它从堆中删除。不断删除堆顶元素直至i&gt;=j-l2。这时得到累加段右端为j时的最大和s[j]-s[i]，与当前最优解比较，取最大值。<BR>　　这种算法的时间复杂度为O(nlogn)，需要开两个大小为n的数组。这个空间复杂度对版本2是行不通的。其实，本题还有更优的算法，只是我在做本题时没有想到。详见<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#1175">版本2</A>。