《NOIP基本程序题集解题报告》由会员分享，可在线阅读，更多相关《NOIP基本程序题集解题报告（21页珍藏版）》请在金锄头文库上搜索。
1、一、 贪心算法Problem1. 删数问题首先考虑 s=1 时的情况，很容易知道如果只删一个数，那么若各位数字递增则删除最后一个数，否则删除第一个递减区间的首字符，这样删除便可以得到最小的数。而对于 s1 时，我们只需要重复这种操作 s 次，得到的操作就是所求的最小数。Problem2. 旅行家的预算假设现在在第 i 站，那么在这站加满油可以到达的最远距离是 disi+c*d2，如果在这个范围内存在一个加油站 j，它的价格 prijdisi+c*d2，此时无解。Problem3. 线段覆盖贪心策略为：每次选取线段右端点最小的线段，保留这条线段，并把和这条线段有公共部分的所有线段删除。重复这个过
2、程，直到任两条线段之间都没有公共部分。由于右端点最小，所以保证了所有与这条线段没有公共部分的线段都在这条线段的右边，且所有与这条线段有公共部分的线段两两之间都有公共部分。由于有公共部分的线段中，最后只能保存一条，显然右端点越小，对后面的影响越小，这条线段应该保留。Problem4. 背包问题 由于每一物品是按重量拿，所以我们每次选取当前单位重量价值最高的放入背包，直到物品取完，或背包装满。Problem5. 任务调度迟任务调度中在规定期限后完成的任务，试题要求解出最小化迟任务的罚款总和;早任务调度中在规定期限前完成的任务，最大化早任务的罚款总和正好对应问题的解;任意一个调度可通过下述方式安排成
3、规范形式:1.按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间 K 和 K+1 的早任务 i、j 且 djaj（i 为 1-mid 数组中的元素，j 为 mid-n 数组中的元素），显然ai,aj为一逆序对，并且 aj与 ai后面的所有元素都为逆序对，于是在合并过程中，我们就可以通过 O(n)的合并时间，统计跨组的逆序对，于是总算时间为O(nlogn)，可以承受。Problem5. 寻找最近点对使用分治思想，我们将平面上的点用一条竖线分为左边的与右边的点，分别求出两点同时在左边或右边的最近点对(设他们的最小值为 s)，然后合并，求两点分别在左右的最近点对，这两点一定在离竖线
4、的 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 ）在第二种情况中, 那两个度为奇数的节点一个为起点,剩下的一个是终点. 求路径时，任取一个起点（本题应该是取编
5、号最小的合法起点）,开始下面的步骤 （1） 如果该点没有相连的点，就将该点加进路径中然后返回。 （2） 如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）（3） 处理当前的点 ,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中。Problem2. Car 的旅行路线主思想就是 dijkstra，因为总共最多有 100 个城市，所以我们就可以建 400个点，然后建一个源点与 A 中点相连，一个汇点与 B 中点相连，相连的边权值为 0，然后 dijkstra 求解即可。只不过需要注意的是知道矩形的三个顶点如何求第四个点的问
6、题，这其实很简单，找到三个点中处于中间的那个点，然后用旁边两点的横纵座标的和减去他的横纵坐标即可。Problem3. 求割点与桥DFS,NUMI记录访问到 I 的时间戳,LOWI=MINNUMI,LOWQ存在 I-Q 的边且Q 不是 I 的父节点。然后就可以判断了，i 是割点当 i 是根节点且它有 2 个以上的儿子，或者它不是根节点且 lowq=numq；(i,q) 是桥当且仅当 lowqnumi。Problem4. 十字绣将正面的边视为正边，反面的则视为负边。用 floodfill 将由正边和负边交替连接的结点组成一个块。对于每一个块，其中的所有结点的正边数目和负边数目之差的绝对值（定为 d
7、ep）之后 div 2 后就为这个块的所需针数。在一个块中只用一针就可完成，假设该针由 v1 出发，到 vn 结束，那么 v1到 vn 中间的点的 dep 为 0，而 v1 和 vn 则为 1。也就是说块中的那一针在 v1 有一个入口，在 vn 有一个出口，而每一对入口和出口就代表了一针，那么就可以通过 dep 之和除以 2 得到所需针数。由此可以拓宽到多针。Problem5. 舞会显然，这一体应该是求有向图的强连同分量的个数。求一个有向图的强连同分量是 DFS 的经典应用，一般步骤如下：1 对于图 G，首先进行一次 DFS，记下每个节点搜索过程中的完成时刻；2 将 G 中的所有边反向，得到图
8、 G 的转置，记为 Gt；3 按照第一次 DFS 中节点完成时刻的递减顺序考虑图 Gt，对其进行搜索；4 对于第二次深搜得到的森林，每棵树各自独立的成为一强连通分量。Problem6. 休息中的小呆这一题有两问，第一问即是求图的最长路径，不能使用类似 dijkstra 的算法解决，因为最长路径不符合 dijkstra 那种最优子结构，应该使用 bellman-ford(即对每条边松弛 n 轮)。第二问其实就是求所有最长路径上的所有点，可以考虑以剧情终点为起点做一次最长路径，只不过起点一开始的 diss=-maxlen(maxlen 即为第一问的结果)，这样，所有点对应都有两个值，如果这两个值加
9、起来=0，那么这个点就应该在第二问中输出。Problem7. 最有布线问题显然是求一个图的最小生成树，由于每两点都有一个距离，为一稠密图，这里最好使用 Prime，krukal 在此可能效率不高。Problem8. 磁盘碎片整理每个碎片都有一个起始位置与目标位置，从一个不在目标位置上的磁盘碎片开始，一直找下去，可以找到一个环，那么将他们归位的操作次数应该是环中节点数+1。找到所有环，并逐个累加即可。Problem9. 说谎岛注意到有可能在所有的话中，一旦某一句话的真假已经确定，那么另一些话就已经确定了。考虑到这种关系，我们发现其实这是一个图，对于这一个图，边有如下定义：对于两个问题必须同是同否
10、，那么他们的边权值就为 1；若必须相对立，则为-1 ；若没关系则为 0。那么我们发现，对于这个图，如果他有解，那么设其连通分量数为 t，则结果的中数应为 2t，于是剩下的事情就只剩下如何判断无解了。考虑对这个图深搜，那么每次从一个未标记的点开始，那么这一次搜得的结果应该为一个两通分量，并且同时我们可以将它里面所有的点分为两类。这两类应该相互对立：一类如果为是，则另一类必为否。所以搜完一遍后，我们要进行检查，首先检查两类是否有交集，然后检查属于同一类却应该相互矛盾的或属于不同类的却应该相互关联的情况。检查完后，我们就可以计算，不过考虑到 t 较大，所以应该用高精度。Problem10. 01 串
11、问题对于满足要求的串而言，若 numi表示串的长度为 i 的前缀中包含 1 的个数，那么有1 0f do f:=fatherf; i:=x;while ify then writeln(-1)else writeln(abs(behindx-behindy)-1);end;Problem4. 矩形覆盖考虑到不能线性扫描，我们使用线段树以加快统计速度。第首先建树、对每个 Event 排序，然后逐个插入，每次统计横向边的长度为上次的连续段数*2*（两次事件的 x 坐标之差），每次统计纵向边的长度：上次的“测度”与这次“测度”的差的绝对值。而每次统计的面积则是上次的测度乘以两件 Event 间的距离
12、。Problem5. 最短路径问题由于数据范围有点大，所以就应该改进一下算法，具体改进就是在储存每个点的当前最短路径方面，使用堆储存，于是每次去未标记的最近点的复杂度为 O(1)，然后更新每个距离的复杂度为 O(logn)，所以总的复杂度算下来只有O(n+Elogn)Problem6. 果子合并由于 n 比较大，所以在每次找最小的两堆果子时不能使用线性的扫描算法。首先可以考虑使用堆，通过堆来储存所有的果子的状态，这样复杂度降到O(nlogn)，可以承受。其实有更易于实现的方法，我们发现一个性质，即所有合并的过程中所得到的果子的重量是递增的。利用这一性质，我们可以建立一个队列，专门存储合并后的堆
13、，然后对原堆进行排序，每次取两组中最小的两个，删除后合并，加在队尾，如此循环即可。复杂度为排序复杂度 O(nlogn)七、 字符串处理Problem1. 相对分子质量首先读入文件 dic.txt，然后使用映射将元素符号转为数字放入数组，接下来读入化学式，建立一个栈，计算规则如下：1 读到化学元素，首先将它相对质量找出来，然后判断他后面是否有数字，有就乘起来，然后加入到栈的当前一层的数中2 读到左括号，就压栈，为括号内的计算腾出空间3 读到右括号，先判断右括号后是否有数字，有就乘以当前栈中的顶层数字，将得到的结果加到他的下一层中，然后退栈最后结果即为栈中剩下的元素。Problem2. 表达式求值
14、栈的一个基本应用，可以直接用栈扫描一遍，也可以先转换为后缀表达式，然后求值。Problem3. 侦探推理需要考虑很多条件，因此在解决问题时将所有人说的话统一起来是很有必要的。因此我们读入每一条信息，首先判断他是谁说的，然后判断第一个单词，如果是Today就可以判断一下是否为星期几，不过千万不要因为判断出不是描述日期的就默认这句话为废话，其实它还是有可能是有用的话的。接下来判断是否是说犯罪问题的，对于说谁谁是罪犯的一律标记为类型 0，不是的标记为1；相应的说日期的标记为 2。处理完每一句话后，就可以枚举罪犯了，整个过程就这样完了，只不过说起来容易，做起来难罢了。Problem4. 最长公共子串枚举第一个字串的子串，然后判断他是否为其他字串的子串。Problem5. 一元一次方程的求解将方程化为 ax+b=0 的形式( 用累计器 a，b 累计，从头到尾扫一遍即可)Problem6. 多项式乘法使用两个累加器分别记录两个多项式对应次幂的系数，然后相乘输出。输出是注意不要输出以下几种情况：1x,x1,x0,0x
