NOIP基本程序题集解题报告.doc

一、 贪心算法Problem1. 删数问题首先考虑s=1时的情况，很容易知道如果只删一个数，那么若各位数字递增则删除最后一个数，否则删除第一个递减区间的首字符，这样删除便可以得到最小的数。而对于s1时，我们只需要重复这种操作s次，得到的操作就是所求的最小数。Problem2. 旅行家的预算 假设现在在第i站，那么在这站加满油可以到达的最远距离是disi+c*d2， 如果在这个范围内存在一个加油站j，它的价格prijdisi+c*d2，此时无解。Problem3. 线段覆盖贪心策略为：每次选取线段右端点最小的线段，保留这条线段，并把和这条线段有公共部分的所有线段删除。重复这个过程，直到任两条线段之间都没有公共部分。由于右端点最小，所以保证了所有与这条线段没有公共部分的线段都在这条线段的右边，且所有与这条线段有公共部分的线段两两之间都有公共部分。由于有公共部分的线段中，最后只能保存一条，显然右端点越小，对后面的影响越小，这条线段应该保留。Problem4. 背包问题 由于每一物品是按重量拿，所以我们每次选取当前单位重量价值最高的放入背包，直到物品取完，或背包装满。Problem5. 任务调度迟任务调度中在规定期限后完成的任务，试题要求解出最小化迟任务的罚款总和;早任务调度中在规定期限前完成的任务，最大化早任务的罚款总和正好对应问题的解;任意一个调度可通过下述方式安排成规范形式: 1.按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间K和K+1的早任务i、j且djdi，我们就互换i和j的位置，使得任务i在交换后仍然是早的，而任务j被移到更前的位置; 2.如果某个早任务X跟在迟任务Y之后，我们可以交换X和Y的位置，使得早任务先于迟任务;任一调度中早任务的集合构成了一个独立的任务集A，因为A中任务按期限单调递增的顺序进行调度后，没有一个任务是迟的、且A中期限为t或更早的任务个数小于等于t。显然A集合为满足传递性质的独立子集,而问题的解为其中罚款总和最大的一个子集。Problem6. 果子合并很明显，为了让总和最小，我们每次应该选取最小的两对果子将它们搬到一起。Problem7. 射击竞赛1 统计所有行包含的白格数2 从还没有射击格的行中选出一个白格数最少的3 检查所选的行1) 若所选行的白格数为0，则输出无解；2) 否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减14 返回到第2步，直到所有的行都有射击格。5 若还有列没有选射击格，则在该列任选一白格作为射击格即可Problem8. 任务安排分为两步，既是先完成对A机器的安排，然后再对B机器进行安排。我们可以很容易的用贪心法安排对A的操作。应为每一个零件对于A机器来说都是公平的，因此记录完成当前分配的所有工作后每个机器的完成时间(显然初始值所有机器为0)，接下来依次加入需要完成的工作，找完成时间最小的机器完成当前的工作。而对于B机器的安排就有点麻烦了，因为每台A机器完成操作的时间不同，不好用贪心。其实可以这样做，首先我们把它看作是平等的。这样对于每一个工件，它的B操作会有自己的完成时间，同样对于每个工件的A操作也会有。于是，我们可以这样贪心来求得最短时间，A操作中最快完成的与B操作中最慢完成的加起来，A中第二完成的与B中倒数第二完成的加起来，A中第三完成的与B中倒数第三完成的加起来，最后取最大的就是最短时间。原因很简单，以最小的配对为例，最小的配最大的才能使其他的配对尽量的短Problem9. 最小差距首先考虑n为奇数时，显然我们首先应该让他们的位数尽量接近，即一个为ndiv2,另一个为ndiv2+1，为了让差尽量小，所以较大的数我们我们应该取最小的ndiv2+1个数，并以升序排列，较大的数我们应该取剩下的ndiv2个数，并按降序排列。而偶数就不能这样做，一个显然的反例就是对于1234,如果按照奇数的方法就应该是43-12=21，显然31-24=721，所以不成立。我们将算法改改，首先枚举两个数的最高为，最高位定下来后，再按照奇数的方法来贪心处理剩下的数字，从中取最小的值即可。二、 分治法Problem1. 一元三次方程的解这一题的方法很多，因为精度要求不高的缘故，所以无论二分还是枚举都可以过，不过在硬枚举时，步进的精度最好选为0.001，这样如果出现f(x)f(x+0.001)aj（i为1-mid数组中的元素，j为mid-n数组中的元素），显然ai,aj为一逆序对，并且aj与ai后面的所有元素都为逆序对，于是在合并过程中，我们就可以通过O(n)的合并时间，统计跨组的逆序对，于是总算时间为O(nlogn)，可以承受。Problem5. 寻找最近点对使用分治思想，我们将平面上的点用一条竖线分为左边的与右边的点，分别求出两点同时在左边或右边的最近点对(设他们的最小值为s)，然后合并，求两点分别在左右的最近点对，这两点一定在离竖线的s范围之内，将这些点列出来，按y坐标排序，可以证明如果在这些点中存在s=（k=i+1 to m）2*Rk2*hk/Ri=2/Ri*(N-T)=PT为已经是已经使用的体积，W为已经用的面积，S为当前最小的面积，如果P=S-W那么可以剪枝。四、 图论算法Problem1. 一笔画问题判断依据为：（1）当且仅当一幅图是相连的(只要你去掉所有度数为0的点)且每个点的度都是偶数,这幅图有欧拉回路. （2）当且仅当一幅图是相连的且除两点外所有的点的度都是偶数. （3）在第二种情况中,那两个度为奇数的节点一个为起点,剩下的一个是终点. 求路径时，任取一个起点（本题应该是取编号最小的合法起点）,开始下面的步骤 （1） 如果该点没有相连的点，就将该点加进路径中然后返回。 （2） 如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）（3） 处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中。Problem2. Car的旅行路线 主思想就是dijkstra，因为总共最多有100个城市，所以我们就可以建400个点，然后建一个源点与A中点相连，一个汇点与B中点相连，相连的边权值为0，然后dijkstra求解即可。只不过需要注意的是知道矩形的三个顶点如何求第四个点的问题，这其实很简单，找到三个点中处于中间的那个点，然后用旁边两点的横纵座标的和减去他的横纵坐标即可。Problem3. 求割点与桥DFS,NUMI记录访问到 I的时间戳,LOWI=MINNUMI,LOWQ存在I-Q的边且Q不是I的父节点。然后就可以判断了，i是割点当i是根节点且它有2个以上的儿子，或者它不是根节点且lowq=numq；(i,q)是桥当且仅当lowqnumi。Problem4. 十字绣将正面的边视为正边，反面的则视为负边。用floodfill将由正边和负边交替连接的结点组成一个块。对于每一个块，其中的所有结点的正边数目和负边数目之差的绝对值（定为dep）之后div 2后就为这个块的所需针数。在一个块中只用一针就可完成，假设该针由v1出发，到vn结束，那么v1到vn中间的点的dep为0，而v1和vn则为1。也就是说块中的那一针在v1有一个入口，在vn有一个出口，而每一对入口和出口就代表了一针，那么就可以通过dep之和除以2得到所需针数。由此可以拓宽到多针。Problem5. 舞会显然，这一体应该是求有向图的强连同分量的个数。求一个有向图的强连同分量是DFS的经典应用，一般步骤如下：1 对于图G，首先进行一次DFS，记下每个节点搜索过程中的完成时刻；2 将G中的所有边反向，得到图G的转置，记为Gt；3 按照第一次DFS中节点完成时刻的递减顺序考虑图Gt，对其进行搜索；4 对于第二次深搜得到的森林，每棵树各自独立的成为一强连通分量。Problem6. 休息中的小呆这一题有两问，第一问即是求图的最长路径，不能使用类似dijkstra的算法解决，因为最长路径不符合dijkstra那种最优子结构，应该使用bellman-ford(即对每条边松弛n轮)。第二问其实就是求所有最长路径上的所有点，可以考虑以剧情终点为起点做一次最长路径，只不过起点一开始的diss=-maxlen(maxlen即为第一问的结果)，这样，所有点对应都有两个值，如果这两个值加起来=0，那么这个点就应该在第二问中输出。Problem7. 最有布线问题显然是求一个图的最小生成树，由于每两点都有一个距离，为一稠密图，这里最好使用Prime，krukal在此可能效率不高。Problem8. 磁盘碎片整理每个碎片都有一个起始位置与目标位置，从一个不在目标位置上的磁盘碎片开始，一直找下去，可以找到一个环，那么将他们归位的操作次数应该是环中节点数+1。找到所有环，并逐个累加即可。Problem9. 说谎岛注意到有可能在所有的话中，一旦某一句话的真假已经确定，那么另一些话就已经确定了。考虑到这种关系，我们发现其实这是一个图，对于这一个图，边有如下定义：对于两个问题必须同是同否，那么他们的边权值就为1；若必须相对立，则为-1；若没关系则为0。那么我们发现，对于这个图，如果他有解，那么设其连通分量数为t，则结果的中数应为2t，于是剩下的事情就只剩下如何判断无解了。考虑对这个图深搜，那么每次从一个未标记的点开始，那么这一次搜得的结果应该为一个两通分量，并且同时我们可以将它里面所有的点分为两类。这两类应该相互对立：一类如果为是，则另一类必为否。所以搜完一遍后，我们要进行检查，首先检查两类是否有交集，然后检查属于同一类却应该相互矛盾的或属于不同类的却应该相互关联的情况。检查完后，我们就可以计算，不过考虑到t较大，所以应该用高精度。Problem10. 01串问题对于满足要求的串而言，若numi表示串的长度为i的前缀中包含1的个数，那么有1 0=numi+1-numi=12 A1=numi+L1-numi=B13 A0=(i+L0-numi+L0)-(i-numi)=B0有如上关系，我们很快发现，他就等同于一个差分约束系统，对于此图，如果存在负权回路，那么他就无解，如果不存在，那么求出最短路径，根据路径直接构出一组解。具体实现时，用bellman-ford就可以了。Problem11. 海岛地图 这是一个典型的flood-fill(即种子填充算法)问题，既可以使用DFS，又可以使用BFS实现，但为了保证不堆栈溢出，我们最好使用BFS。五、 数学问题Problem1. 数的划分据经典的Ferrers图像可以知道n拆分为k个整数的拆分数，与n拆分成最大数为k的拆分数相等，于是用递推的方法：用表示把b做任意剖分，其中最大的一个部分恰好是a的方案总数。用 表示把b做任意剖分，其中最大的一个部分不大于a的方案总数。那么，有： 。消去 ，有： 。我们可以按照a、b递增的顺序计算 的值，这样在在计算 的时候， 和 都已经得到，故我们只用进行一次简单的加法运算即可。最后的 即为所求。Problem2. 最优分解方案为了使最后分解的数的乘积最大，首先我们应该确定n应该分解为几个数(其实就是n可以分出的最多个数)，确定过程就是从2开始以步差为1累加，直到恰好小于n位置(就是找最大数为k，使2+3+k=tn，划分成的个数应该为k+1)；确定下来后，由于n剩下来了一些，所以将这些平均的加到k-2上，由于不能平分，所以应该是先所有数加上(n-t)divk，然后较大的(n-t)modk个数多加一个1。这样就确定下来了所有的数。我们最后使用单精度将他们乘起来即可。Problem3. 出栈序列统计每一次操作仅有两种，即压栈与退栈，这种操作可以对应于一个数的中序遍历(即向下更深层遍历与回溯)。显然对于答案，其实就是一个Cartlan数列，F(n)=C(2n,n)/(n+1)Problem4. 百事世界杯之旅 对于要在剩下的i种瓶盖中收集到一种，买一瓶饮料收集到的概率为(i/n)，所以平均应该买(n/i)瓶，所以平均总共要买n(1/1+1/2+1/3+.+1/n)瓶。Problem5. 电子锁 n-1在一起，至少缺少一种开锁的密码特征，故不能打开电子锁，剩下的m-(n-1)个人中的任意一个人到场即可开锁，所以至少有C(m,m-n+1)种特征。对于任意一个工作人员来说，其余m-1个人中的n-1个人到场，至少缺少一个这个工作人员磁卡上所具有的特征，所以每个人至少有C(m-1,n-1)种开锁的密码特征。 对于每一种特征的分配方案，其实就是一个C(m,m-n+1)个中选择C(m-1,n-1)的组合生成。Problem6. 堆塔问题对于这一题我们采用分类计数法，当列数为i时，每一个堆塔方案对应方程：x1+x2+x3+x4+xi=n的一个组正整数解，所以此时的方案数为C(n-1,i-1)，所以总方案数为：C(n-1,0)+C(n-1,1)+C(n-1,n-1)=2nProblem7. 取数游戏首先模拟取数，我们要做的就是判断无解的情况。 假设某一趟共取m次，那么把每一堂取数中每一次所取的数加起来所对应的二进制数为(1111)2，其中1的个数为m，而取得的余数一定不大于二进制数(1111)2，其中1的个数为m，否则可以继续取下去。所以一个数经过一趟取数后余下的数最多只能达到他的一半。即第i趟取数后，余下的数不超过k+n/p-k/q，这里的p等于2的i次方，q等于2的i-1次方。显然所有的余数不会超过k+n/2，所以在取了k+n/2+1趟后尚未取完，那么必有两趟余数相同，即永远也取不完了。Problem8. 球迷购票其实这一与出栈序列统计类似，其实就是一个从(0,0)走到(m,n)，每次只能向右或上走单位1距离，其中向上走的布数应非严格大于向右走的步数的总路径数。这个数是一个很经典的组合数，即为C(m+n,n)-C(m+n,n-1)。Problem9. Fibonacci公约数可以证明GCD(Fn,Fm)=Fgcd(m,n)(只用证F(n)整除F(k*n)。Problem10. 传球问题与磁盘碎片整理相似，我们首先找环，每个环所需的归位次数为环所包含节点数-1。对于总时间，我们单独的考虑每个环，最后取最大值即可。若包含节点数为1，那么需时间0；若包含节点数2，那么需时间1；若包含节点数大于2，我们可以花时间1，将此环拆成多个长度为1与2的环，然后再交换，所以用时为2。Problem11. 约瑟夫问题显然答案为2*(n-2a)+1，a为使2a不大于n的最大整数。Problem12. 青蛙过河 有fi,j表示i片叶子，j块石头最多将青蛙送到对岸的个数，那么有fi,j=2*fi-1,j，其原因与汉诺塔的原理相类似（将第i个石头看作是对岸就可以了）。而f0,j=j+1，应为只有将j个石头占满，然后将第j+1个青蛙放到对岸，那么所有的j+1个青蛙就可以过河了。于是又fi,j:=(j+1)*2n，答案即为(m+1)*2n。Problem13. 棋盘游戏 通过找规律我们发现： 1无论移动什么棋子，以每一次换颜色为界，每次移动数目为1,2,3n,n,n,3,2,1 2第一次移动白色棋子，最后一次也是的。六、 数据结构Problem1. 火车栈有一个最基本的方法，即使如果存在进栈时为ijk的三元组，其出栈序列为kij，那么肯定它是无解的，其他情况时有解的。于是我们很快就可以得到一个O(n3)的算法，但是很显然TLE。想到Cartlan树中进栈出栈的对应方法，我们可以按照这棵树的生成法来检测出栈序列。相当于已知一棵树的中序遍历，判断一个序列是否为这棵树的前序遍历。这是用分治法解决。这样就可以解决这一题了。然而，其实有更好更简单的方法。模拟进栈出栈，在栈顶元素与当前要求出栈的元素相同时我就进行弹栈操作，否则就压栈。如果无法压栈，而且无法弹栈，那么就是无解的。如此进行硬性的扫描模拟就够了，复杂的为O(n)。Problem2. 括号表达式建立一个栈，然后往里面放括号碰见左括号就进栈，右括号就退栈，如果碰见括号不匹配，或者无法退栈的情况就是无解的。Problem3. 银河英雄传说用并查集来解决这一道问题，然而考虑到此题的特殊情况，我们要对并查集的结构进行一定的改进然后再运用到程序中。定义以下几个量：fatheri表示i现在从属于哪一舰队behindi表示i现在离舰首的距离depi表示i后面有多少只军舰于是，我们可以利用路径压缩（findfather）的过程同时进行更新dep与behind，对于路径压缩我们采用以下过程：function find(x:longint):longint; var i,j,f,temp:longint; begin f:=x;while fatherff do f:=fatherf; i:=x; while if do begin temp:=fatheri; fatheri:=f; j:=temp; repeat behindi:=behindi+behindj; j:=fatherj; until fatherj=j; i:=temp; end; find:=f; end;而对于merge操作，我们要做的就是把一方的father指向另一方，同时变更behind与dep：procedure merge(x,y:longint); var fx,fy:longint; begin fx:=find(x);fy:=find(y); fatherfatherfx:=fy; behindfx:=behindfx+depfy; depfy:=depfy+depfx; end;相对于find与merge，count就简单得多，因为它只需要判断两舰是否属于同一队，然后两个behind相减即可：procedure check(x,y:longint); var fx,fy:longint; begin fx:=find(x);fy:=find(y); if fxfy then writeln(-1) else writeln(abs(behindx-behindy)-1); end;Problem4. 矩形覆盖 考虑到不能线性扫描，我们使用线段树以加快统计速度。第首先建树、对每个Event排序，然后逐个插入，每次统计横向边的长度为上次的连续段数*2*（两次事件的x坐标之差），每次统计纵向边的长度：上次的“测度”与这次“测度”的差的绝对值。而每次统计的面积则是上次的测度乘以两件Event间的距离。Problem5. 最短路径问题由于数据范围有点大，所以就应该改进一下算法，具体改进就是在储存每个点的当前最短路径方面，使用堆储存，于是每次去未标记的最近点的复杂度为O(1)，然后更新每个距离的复杂度为O(logn)，所以总的复杂度算下来只有O(n+Elogn)Problem6. 果子合并由于n比较大，所以在每次找最小的两堆果子时不能使用线性的扫描