Pascal基本程序题集解题报告【看看不后悔】

基本程序题集解题报告贪心算法删数问题首先考虑s=1时的情况，很容易知道如果只删一个数，那么若各位数字递增则删除最后一个数，否则删除第一个递减区间的首字符，这样删除便可以得到最小的数。而对于s>1时，我们只需要重复这种操作s次，得到的操作就是所求的最小数。旅行家的预算假设现在在第i站，那么在这站加满油可以到达的最远距离是dis[i]+c*d2，如果在这个范围内存在一个加油站j，它的价格pri[j]<pri[i]，那么只要把油加到刚好能到达j就可以了；如果在这个范围内不存在这样的加油站，那么就在i加满油，然后走到尽量远的加油站j，如果无法走到j，即最近的加油站dis[j]>dis[i]+c*d2，此时无解。线段覆盖贪心策略为：每次选取线段右端点最小的线段，保留这条线段，并把和这条线段有公共部分的所有线段删除。重复这个过程，直到任两条线段之间都没有公共部分。由于右端点最小，所以保证了所有与这条线段没有公共部分的线段都在这条线段的右边，且所有与这条线段有公共部分的线段两两之间都有公共部分。由于有公共部分的线段中，最后只能保存一条，显然右端点越小，对后面的影响越小，这条线段应该保留。背包问题由于每一物品是按重量拿，所以我们每次选取当前单位重量价值最高的放入背包，直到物品取完，或背包装满。任务调度迟任务──调度中在规定期限后完成的任务，试题要求解出最小化迟任务的罚款总和;早任务──调度中在规定期限前完成的任务，最大化早任务的罚款总和正好对应问题的解;任意一个调度可通过下述方式安排成规范形式:1.按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间K和K+1的早任务i、j且dj<di，我们就互换i和j的位置，使得任务i在交换后仍然是早的，而任务j被移到更前的位置;2.如果某个早任务X跟在迟任务Y之后，我们可以交换X和Y的位置，使得早任务先于迟任务;任一调度中早任务的集合构成了一个独立的任务集A，因为A中任务按期限单调递增的顺序进行调度后，没有一个任务是迟的、且A中期限为t或更早的任务个数小于等于t。显然A集合为满足传递性质的独立子集,而问题的解为其中罚款总和最大的一个子集。果子合并很明显，为了让总和最小，我们每次应该选取最小的两对果子将它们搬到一起。射击竞赛统计所有行包含的白格数从还没有射击格的行中选出一个白格数最少的检查所选的行若所选行的白格数为0，则输出无解；否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1返回到第2步，直到所有的行都有射击格。若还有列没有选射击格，则在该列任选一白格作为射击格即可任务安排分为两步，既是先完成对A机器的安排，然后再对B机器进行安排。我们可以很容易的用贪心法安排对A的操作。应为每一个零件对于A机器来说都是公平的，因此记录完成当前分配的所有工作后每个机器的完成时间(显然初始值所有机器为0)，接下来依次加入需要完成的工作，找完成时间最小的机器完成当前的工作。而对于B机器的安排就有点麻烦了，因为每台A机器完成操作的时间不同，不好用贪心。其实可以这样做，首先我们把它看作是平等的。这样对于每一个工件，它的B操作会有自己的完成时间，同样对于每个工件的A操作也会有。于是，我们可以这样贪心来求得最短时间，A操作中最快完成的与B操作中最慢完成的加起来，A中第二完成的与B中倒数第二完成的加起来，A中第三完成的与B中倒数第三完成的加起来，……最后取最大的就是最短时间。原因很简单，以最小的配对为例，最小的配最大的才能使其他的配对尽量的短……最小差距首先考虑n为奇数时，显然我们首先应该让他们的位数尽量接近，即一个为ndiv2,另一个为ndiv2+1，为了让差尽量小，所以较大的数我们我们应该取最小的ndiv2+1个数，并以升序排列，较大的数我们应该取剩下的ndiv2个数，并按降序排列。而偶数就不能这样做，一个显然的反例就是对于1234,如果按照奇数的方法就应该是43-12=21，显然31-24=7<21，所以不成立。我们将算法改改，首先枚举两个数的最高为，最高位定下来后，再按照奇数的方法来贪心处理剩下的数字，从中取最小的值即可。分治法一元三次方程的解这一题的方法很多，因为精度要求不高的缘故，所以无论二分还是枚举都可以过，不过在硬枚举时，步进的精度最好选为0.001，这样如果出现f(x)f(x+0.001)<=0时，无论解是什么，再取两位后结果不会变。如果是二分法的话，需要注意的问题就是二分过程中要加修正值、计算时判断相等关系，然后就是需要考虑精度问题。查找第k大元素利用快排的思想，我们首先将数列以某一个标准值为基准将数分为两堆，那么根据这个标准值的位置，我们可以确定我们想要的第k大数是在哪一堆中，由此我们可以，递归下去，在那一堆中继续分治找。其实快排之后直接找第k大元素也可以。麦森数对于2^m-1的位数我们显然可以利用对数的性质很方便的求出，即为=[lg(2^m)]+1=[m*lg(2)]+1=[m*ln(2)/ln(10)]+1，对于他的末500位可以使用快速乘方实现，即使用二分的思想，即如果求2^n，那么应先求2^(ndiv2)，于是最后我们就等效成从2不断平方(平方过程中不断调整——乘以2，是否乘以2根据m转换成2进制后的序列决定)，最后的到2^m，减去1即可。逆序对个数首先有一个O(n^2)的算法，即枚举所有数对，显然是会超时的。我们可以利用归并排序的过程，顺带的统计逆序队的个数。归并过程中，首先我们将数组分治，分别将他们排序，并统计他们之中的逆序队的个数，于是剩下要统计的即是一个数在某个数组中，另一个数在另一个数组中的逆序对，这样由于分治的两个数组都是有序的，于是如果当前合并两数组时a[i]>a[j]（i为1-mid数组中的元素，j为mid-n数组中的元素），显然a[i],a[j]为一逆序对，并且a[j]与a[i]后面的所有元素都为逆序对，于是在合并过程中，我们就可以通过O(n)的合并时间，统计跨组的逆序对，于是总算时间为O(nlogn)，可以承受。寻找最近点对使用分治思想，我们将平面上的点用一条竖线分为左边的与右边的点，分别求出两点同时在左边或右边的最近点对(设他们的最小值为s)，然后合并，求两点分别在左右的最近点对，这两点一定在离竖线的s范围之内，将这些点列出来，按y坐标排序，可以证明如果在这些点中存在s’<s，那么其中一个点必至另一个点的临近7个点中的一个。另外注意的就是，如果分治了只剩45个点了，其实就可以直接O(n^2)枚举了，这样其实更快。剔出多于括号四则运算表达式含运算符+-*/（），其优先顺序由低至高为：+-→*/→()一个括号是否作为多于括号剔出，关键是在于括号内优先级最低的运算符与左邻括号或右邻括号的运算符之间的运算优先关系。在处理表达式时我们可以从最低运算符处将表达式分开，分别处理，同时对相应的层进行括号整理，直到处理了最外层的括号为止。剔出多于括号当且仅当N为2的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组：1,2,…,N／2和N／2＋1,N／2＋2,…,N。给第一组运动员安排一个比赛日程，得到一个N／2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样会得到一个N／2阶的一个方阵A2。考虑到比赛的性质，设定第I个运动员在某一天的比赛对手为第K个运动员，则第K个运动员在同一天的比赛对手必然是第I个运动员，即若有A[I,J]=K，则A[K，J]=I。因此原问题的解(一个N阶方阵)可以由分解后的两个子问题的解，合并起来。同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有2个运动员时为止。搜索算法皇后问题极为基本的问题，深度优先搜索，当n=13时一般的搜是不行的,需要加上对称性剪枝。八数码问题同样极为简单，广度优先搜索，必要的话，需要加上hash判重以提高速度。拼图由于不用旋转，可以直接往上放，所以直接搜索即可。有两种搜索策略，一个是对于当前的map搜索第i块放在哪，另一个是对于当前第一个为方的格子，应该放那一块；这两种在事先都应该判断当前搜索是否可行。另外，后一种搜索方法好像更快。质数方阵首先生成所有5位质数的布尔表(显然末尾只可能是1379)，然后循环，循环次序如下最后一行，与最后一列(显然每一个只有4种情况)两个斜行循环21，23，31，41，算出43循环12，算出剩下的埃及分数没有下界，数的上界也没有，并且广搜也行不通，所以就毫不犹豫地使用了DFSID——可变下界深搜。然后就是深搜中的实质性优化，关键的一点就是确定当前可以填入的分母的最大值，很容易就可以算出，他应该取剩下的分数值的倒数的num-t+1倍（num为当前下界，t为当前搜到的位置）。由于不存在下界问题，再加上一些最优性的小剪枝，这一题可以很轻松的解决。字符串变换这题大体上需要用广搜解决，由于节点数太多，需要考虑用双向广搜，然后就是要注意字符串的处理。有点难度，不过不是思维上的。聪明的打字员这一题是典型的广搜，只不过可以肯定的是，一般的广搜肯定是不行的。考虑对规则的优化，总共有6个规则，首先想到的优化就是对于同一位up后不能down、down后不能up，并且left、right不能同时成对出现。这样一来，我们发现程序的确快了一点，然而离AC还是差远了，怎么办？——考虑对up与down的优化：我们发现，一旦一个数的位置一确定，那么对他的up或者down的操作无论在何时进行都可以（只要在操作过程中光标经过了这个位置）。所以，我们可以先撇开up与down不管，先广搜一遍，对于每一个节点的操作只进行另外4种操作，同时只记录光标经过了那么些位置、每个数的当前位置在那里、以进行的操作数与光标当前位置。最后对于所有可能的节点加上所需up或down的操作数，取最优解即可。这样做有一个好处，就是广搜时可用hash标进行判重，我们开始可以用123456代替每一个位置上的数，并且光标经过的位置只会有10种情况（注意它是从1开始移动，根据规则它只可能有10种情况），于是判重时hash表的size只有6*6！*10=43200，完全可以承受。实际操作时，最后可能到达的节点总数只有8000多。01序列现在我没有什么好方法，所以只有搜索。使用深度优先搜索，边搜边判断是否满足要求，为加快速度，可以考虑在判断长度比较小的序列时将它们对应的01序列转换为十进制数，以便hash判重。、另外的一个注意之处就是，第一位添1与添0方案数是一样的。生日蛋糕这一题可以用DP做，不过我认为是一个不明智的做法，因为此举浪费空间大，而重叠的子问题很少，因该用搜索加以适当的优化来解决。首先我们就有两个直观的优化：切到当前层时表面积比最小的面积大，可以剪枝；如果剩下的体积，比可能切出的最小体积小，最大体积大，剪枝。其实这些就够了，但是还可以进一步优化：对于当前的lefts（剩下的需加上的面积），有Lefts=∑（k=i+1tom）2*Rk*hk>=∑（k=i+1tom）2*Rk^2*hk/Ri=2/Ri*(N-T)=PT为已经是已经使用的体积，W为已经用的面积，S为当前最小的面积，如果P>=S-W那么可以剪枝。图论算法一笔画问题判断依据为：（1）当且仅当一幅图是相连的(只要你去掉所有度数为0的点)且每个点的度都是偶数,这幅图有欧拉回路.（2）当且仅当一幅图是相连的且除两点外所有的点的度都是偶数.（3）在第二种情况中,那两个度为奇数的节点一个为起点,剩下的一个是终点.求路径时，任取一个起点（本题应该是取编号最小的合法起点）,开始下面的步骤如果该点没有相连的点，就将该点加进路径中然后返回。如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）处理当前的点,删除和这个点相连的边,在它相邻的点上重复上面的步骤,把当前这个点加入路径中。Car的旅行路线主思想就是dijkstra，因为总共最多有100个城市，所以我们就可以建400个点，然后建一个源点与A中点相连，一个汇点与B中点相连，相连的边权值为0，然后dijkstra求解即可。只不过需要注意的是知道矩形的三个顶点如何求第四个点的问题，这其实很简单，找到三个点中处于中间的那个点，然后用旁边两点的横纵座标的和减去他的横纵坐标即可。求割点与桥DFS,NUM[I]记录访问到I的时间戳,LOW[I]=MIN{NUM[I],LOW[Q]}存在I-Q的边且Q不是I的父节点。然后就可以判断了，i是割点当i是根节点且它有2个以上的儿子，或者它不是根节点且low[q]>=num[q]；(i,q)是桥当且仅当low[q]>num[i]。十字绣将正面的边视为正边，反面的则视为负边。用floodfill将由正边和负边交替连接的结点组成一个块。对于每一个块，其中的所有结点的正边数目和负边数目之差的绝对值（定为dep）之后div2后就为这个块的所需针数。在一个块中只用一针就可完成，假设该针由v1出发，到vn结束，那么v1到vn中间的点的dep为0，而v1和vn则为1。也就是说块中的那一针在v1有一个入口，在vn有一个出口，而每一对入口和出口就代表了一针，那么就可以通过dep之和除以2得到所需针数。由此可以拓宽到多针。舞会显然，这一体应该是求有向图的强连同分量的个数。求一个有向图的强连同分量是DFS的经典应用，一般步骤如下：对于图G，首先进行一次DFS，记下每个节点搜索过程中的完成时刻；将G中的所有边反向，得到图G的转置，记为Gt；按照第一次DFS中节点完成时刻的递减顺序考虑图Gt，对其进行搜索；对于第二次深搜得到的森林，每棵树各自独立的成为一强连通分量。休息中的小呆这一题有两问，第一问即是求图的最长路径，不能使用类似dijkstra的算法解决，因为最长路径不符合dijkstra那种最优子结构，应该使用bellman-ford(即对每条边松弛n轮)。第二问其实就是求所有最长路径上的所有点，可以考虑以剧情终点为起点做一次最长路径，只不过起点一开始的dis[s]=-maxlen(maxlen即为第一问的结果)，这样，所有点对应都有两个值，如果这两个值加起来=0，那么这个点就应该在第二问中输出。最有布线问题显然是求一个图的最小生成树，由于每两点都有一个距离，为一稠密图，这里最好使用Prime，krukal在此可能效率不高。磁盘碎片整理每个碎片都有一个起始位置与目标位置，从一个不在目标位置上的磁盘碎片开始，一直找下去，可以找到一个环，那么将他们归位的操作次数应该是环中节点数+1。找到所有环，并逐个累加即可。说谎岛注意到有可能在所有的话中，一旦某一句话的真假已经确定，那么另一些话就已经确定了。考虑到这种关系，我们发现其实这是一个图，对于这一个图，边有如下定义：对于两个问题必须同是同否，那么他们的边权值就为1；若必须相对立，则为-1；若没关系则为0。那么我们发现，对于这个图，如果他有解，那么设其连通分量数为t，则结果的中数应为2^t，于是剩下的事情就只剩下如何判断无解了。考虑对这个图深搜，那么每次从一个未标记的点开始，那么这一次搜得的结果应该为一个两通分量，并且同时我们可以将它里面所有的点分为两类。这两类应该相互对立：一类如果为是，则另一类必为否。所以搜完一遍后，我们要进行检查，首先检查两类是否有交集，然后检查属于同一类却应该相互矛盾的或属于不同类的却应该相互关联的情况。检查完后，我们就可以计算，不过考虑到t较大，所以应该用高精度。01串问题对于满足要求的串而言，若num[i]表示串的长度为i的前缀中包含1的个数，那么有0<=num[i+1]-num[i]<=1A1<=num[i+L1]-num[i]<=B1A0<=(i+L0-num[i+L0])-(i-num[i])<=B0有如上关系，我们很快发现，他就等同于一个差分约束系统，对于此图，如果存在负权回路，那么他就无解，如果不存在，那么求出最短路径，根据路径直接构出一组解。具体实现时，用bellman-ford就可以了。海岛地图这是一个典型的flood-fill(即种子填充算法)问题，既可以使用DFS，又可以使用BFS实现，但为了保证不堆栈溢出，我们最好使用BFS。数学问题数的划分据经典的Ferrers图像可以知道n拆分为k个整数的拆分数，与n拆分成最大数为k的拆分数相等，于是用递推的方法：用表示把b做任意剖分，其中最大的一个部分恰好是a的方案总数。用表示把b做任意剖分，其中最大的一个部分不大于a的方案总数。那么，有：。消去，有：。我们可以按照a、b递增的顺序计算的值，这样在在计算的时候，和都已经得到，故我们只用进行一次简单的加法运算即可。最后的即为所求。最优分解方案为了使最后分解的数的乘积最大，首先我们应该确定n应该分解为几个数(其实就是n可以分出的最多个数)，确定过程就是从2开始以步差为1累加，直到恰好小于n位置(就是找最大数为k，使2+3+…+k=t<n，划分成的个数应该为k+1)；确定下来后，由于n剩下来了一些，所以将这些平均的加到k-2上，由于不能平分，所以应该是先所有数加上(n-t)divk，然后较大的(n-t)modk个数多加一个1。这样就确定下来了所有的数。我们最后使用单精度将他们乘起来即可。出栈序列统计每一次操作仅有两种，即压栈与退栈，这种操作可以对应于一个数的中序遍历(即向下更深层遍历与回溯)。显然对于答案，其实就是一个Cartlan数列，F(n)=C(2n,n)/(n+1)百事世界杯之旅对于要在剩下的i种瓶盖中收集到一种，买一瓶饮料收集到的概率为(i/n)，所以平均应该买(n/i)瓶，所以平均总共要买n(1/1+1/2+1/3+….+1/n)瓶。电子锁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)的组合生成。堆塔问题对于这一题我们采用分类计数法，当列数为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)=2^n取数游戏首先模拟取数，我们要做的就是判断无解的情况。假设某一趟共取m次，那么把每一堂取数中每一次所取的数加起来所对应的二进制数为(11…11)2，其中1的个数为m，而取得的余数一定不大于二进制数(11…11)2，其中1的个数为m，否则可以继续取下去。所以一个数经过一趟取数后余下的数最多只能达到他的一半。即第i趟取数后，余下的数不超过k+n/p-k/q，这里的p等于2的i次方，q等于2的i-1次方。显然所有的余数不会超过k+n/2，所以在取了k+n/2+1趟后尚未取完，那么必有两趟余数相同，即永远也取不完了。球迷购票其实这一与出栈序列统计类似，其实就是一个从(0,0)走到(m,n)，每次只能向右或上走单位1距离，其中向上走的布数应非严格大于向右走的步数的总路径数。这个数是一个很经典的组合数，即为C(m+n,n)-C(m+n,n-1)。Fibonacci公约数可以证明GCD(Fn,Fm)=Fgcd(m,n)(只用证F(n)整除F(k*n))。传球问题与磁盘碎片整理相似，我们首先找环，每个环所需的归位次数为环所包含节点数-1。对于总时间，我们单独的考虑每个环，最后取最大值即可。若包含节点数为1，那么需时间0；若包含节点数2，那么需时间1；若包含节点数大于2，我们可以花时间1，将此环拆成多个长度为1与2的环，然后再交换，所以用时为2。约瑟夫问题显然答案为2*(n-2^a)+1，a为使2^a不大于n的最大整数。青蛙过河有f[i,j]表示i片叶子，j块石头最多将青蛙送到对岸的个数，那么有f[i,j]=2*f[i-1,j]，其原因与汉诺塔的原理相类似（将第i个石头看作是对岸就可以了）。而f[0,j]=j+1，应为只有将j个石头占满，然后将第j+1个青蛙放到对岸，那么所有的j+1个青蛙就可以过河了。于是又f[i,j]:=(j+1)*2^n，答案即为(m+1)*2^n。棋盘游戏通过找规律我们发现：1．无论移动什么棋子，以每一次换颜色为界，每次移动数目为1,2,3……n,n,n……,3,2,12．第一次移动白色棋子，最后一次也是的。数据结构火车栈有一个最基本的方法，即使如果存在进栈时为i<j<k的三元组，其出栈序列为k<i<j，那么肯定它是无解的，其他情况时有解的。于是我们很快就可以得到一个O(n^3)的算法，但是很显然——TLE。想到Cartlan树中进栈出栈的对应方法，我们可以按照这棵树的生成法来检测出栈序列。——相当于已知一棵树的中序遍历，判断一个序列是否为这棵树的前序遍历。这是用分治法解决。——这样就可以解决这一题了。然而，其实有更好更简单的方法。模拟进栈出栈，在栈顶元素与当前要求出栈的元素相同时我就进行弹栈操作，否则就压栈。如果无法压栈，而且无法弹栈，那么就是无解的。如此进行硬性的扫描模拟就够了，复杂的为O(n)。括号表达式建立一个栈，然后往里面放括号——碰见左括号就进栈，右括号就退栈，如果碰见括号不匹配，或者无法退栈的情况就是无解的。银河英雄传说用并查集来解决这一道问题，然而考虑到此题的特殊情况，我们要对并查集的结构进行一定的改进然后再运用到程序中。定义以下几个量：father[i]表示i现在从属于哪一舰队behind[i]表示i现在离舰首的距离dep[i]表示i后面有多少只军舰于是，我们可以利用路径压缩（findfather）的过程同时进行更新dep与behind，对于路径压缩我们采用以下过程：functionfind(x:longint):longint;vari,j,f,temp:longint;beginf:=x;whilefather[f]<>fdof:=father[f];i:=x;whilei<>fdobegintemp:=father[i];father[i]:=f;j:=temp;repeatbehind[i]:=behind[i]+behind[j];j:=father[j];untilfather[j]=j;i:=temp;end;find:=f;end;而对于merge操作，我们要做的就是把一方的father指向另一方，同时变更behind与dep：proceduremerge(x,y:longint);varfx,fy:longint;beginfx:=find(x);fy:=find(y);father[father[fx]]:=fy;behind[fx]:=behind[fx]+dep[fy];dep[fy]:=dep[fy]+dep[fx];end;相对于find与merge，count就简单得多，因为它只需要判断两舰是否属于同一队，然后两个behind相减即可：procedurecheck(x,y:longint);varfx,fy:longint;beginfx:=find(x);fy:=find(y);iffx<>fythenwriteln(-1)elsewriteln(abs(behind[x]-behind[y])-1);end;矩形覆盖