NOIP2000-2009提高组解题报告.doc

NOI分区联赛 - 2000年第六届提高组试题解析注意：解析和源程序均为OIBH站长刘汝佳所写，疏漏在所难免，但至少程序均通过了比赛时使用的测试数据，所以还是可以一看。第一题：大家对正数进制的转换应该比较熟悉吧！（不会的看我的循序渐进）负数进制一样。每次取的余数保证在0-m-1之间。（例如m=-16,则余数应该在015）就可以直接输出。所以用系统的“mod”运算符的时候必须注意检查是不是在该范围（可能在m+10），否则就调整。调整的方法是：if 余数0 thenbegin 余数=余数-m; 商=商+1;end;程序见附件。第二题：很明显的动态规划。令di,j,k为第i个数字到第j个数字加k个乘号所能够达到的最大值。状态转移方程是：di,j,k=maxnumi,t*dt+1,j,k-1 (枚举t, 满足i=t9-9-1第二次是：1和是21但显然可以两次把所有的数拣完(22)。本题是典型的多维动态规划，很象IOI93的第四题,另一个算法是网络流，很象IOI97第一题，这里我只分析前者。这道题目的简单之处是阶段很好划分（对角线），这种方法我就不介绍了，因为很多地方都有介绍。这里讲一种怪一点的动态规划_容易想到的思路是：令dx1,y1,x2,y2表示甲在x1,y1,乙在x2,y2以后（包括取走(x1,y1)）的过程中可以获得的最大和。则d1,1,1,1就是原问题的解。但是是否能取数和另一个人是否事先已经到过该格子有关，我们需要设计一种走的方法，使得只根据x1,y1,x2,y2就能判断一些关键的格子是否已经到达过。这样，问题才具有无后效性。为此，我们把路线作如下处理：1)当两个人路线有交叉的时候，改成等效的，不交叉的。如下图，1代表第一个人，2代表第二个人。X代表相遇点。X1112 1222X2 12 12 1X1 2X变成：X2221 2111X2 12 12 1X2 1X反正让2走右边就行了。2)现在1在第y1列，2在第y2列，让1和2分别向右走,到达yy1和yy2列，然后向下走一格这样如果yy1 = y1, y2 = y2(题目规定), y1 = y2(刚才的分析),递推dy1,y2 d1:=d2; 只记录相邻两个状态end;边界是什么呢？当然是从第n列的值了，就是sumn,y1,n(从y1取到n)说了这么多，真不知道我说清楚了没有（ 好象是没有:-P ），如果有什么不明确的地方，请大家在论坛上提出来。一句话，就是两个人一起，一行一行往下走，每一行可以一次向右走若干步，但是要保证2在1的右边。注意最后输出的是d21,1。如果输出d11,1,n=1会得到0。（为什么？自己想啊）现在程序就不难写了吧。程序见附件：第七届（2001）分区联赛复赛解题报告（提高组）俞玮赵爽第一题：一元三次方程求解给出一个三次方程 ，试求它所有的三个根。这里所有的根都在区间 中，并保证方程具有三个实根，且它们之间的差不小于1。分析：如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。由于题目要求只精确到0.01，故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知，我们可以用一个变量 从-100.000到100.000以步长0.001做循环。若 ，则可知在区间 内存在方程的解。这样无论这个区间内的解是什么，在取两位小数的精度后都与 取两位小数的结果是一样的。故我们就可以把取两位小数精度的 作为问题的解。另外还有可能方程的根在区间端点 的情况，我们可以通过判断 是否为0来获得。但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程 在区间 内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间 内存在一个方程的根，则 这个事实，并重复执行如下的过程：l取当前可能存在解的区间 ；l若 或 ，则可确定根为 并退出过程；l若 ，则由题目给出的定理可知根在区间 中，故对区间 重复该过程；l若 ，则必然有 ，也就是说根在 中，应该对此区间重复该过程。最后，就可以得到精确到0.001的根。再考虑什么样的区间内会有根 。由于题目给出了所有的根都在-100到100之间，且根与根之间差不小于1的限制条件，故我们可知，在 、 、 、 这201个区间内，每个区间内至多只能存在一个根。这样对除去区间 外 的其他的区间 ，要么 ，要么 时这个方程在此区间内才有解。若 ，显然 为解；若 ，则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解。最后是输出的解要求排序。我们既可以在求出来之后排序，也可以从小到大的顺序求解，就可以按照升序求出所有解。数据：输入输出11 -2 -1 2-1.00 1.00 2.0021 -4.65 2.25 1.4-0.35 1.00 4.0031 10 -1 -10-10.00 -1.00 1.0041 -1.8 -8.59 -0.84-2.10 -0.10 4.00第二题：数的划分求把一个整数 无序划分成 份互不相同的正整数之和的方法总数。分析：这是一道整数剖分的问题。这类问题的数学性很强，方法也很多。这里介绍一种较为巧妙的办法。我们不必拘泥于原问题如何求解，而把思维转换一个角度来考虑一个与原问题等价的问题。我们可以形象的把n的k-自然数剖分看作把n块积木堆成k列，且每列的积木个数依次递增，也就是这n块积木被从左到右积木被堆成了“楼梯状”。比如，下图是10的几种4-剖分。 现在，我们不妨把这三个图顺时针旋转90度，成为 ： 不难发现，旋转之后的模型还是10的剖分，不过约束条件有所不同。很明显，由于原来是k剖分，因此新的模型中最大的一个元素必然是k。而其余的元素大小不限，但都不能大于k。因此问题转化成了求n的任意无序剖分，其中最大的元素是k 。当然，我们可以把n减去k，成为 ，剩下的问题就是求 的任意剖分，且其中每个元素都不大于k的方案总数了。求解这个新的模型可以用递推的方法。用 表示把b做任意剖分，其中最大的一个部分恰好是a的方案总数。用 表示把b做任意剖分，其中最大的一个部分不大于a的方案总数。那么，有： 。消去 ，有： 。我们可以按照a、b递增的顺序计算 的值，这样在在计算 的时候， 和 都已经得到，故我们只用进行一次简单的加法运算即可。最后的 即为所求。这种方法的时间复杂度为 。空间复杂度为O(nk)，或者我们可以用滚动数组的方法降到O(n)。该题中模型转化的思想，是很值得借鉴的。数据：给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字符串以每行20个字母的方式输入，且保证每行一定20个）。要求将此字符串分成k份（1k40），且每份中包含的单词个数加起来最大（每份中包含的单词可以重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，但是选用this之后就不能再选th）。分析：这一题应该算是一道比较原创的题目。注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置 的参数 表示以位置 的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词 。这样对于所有的不同 个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的 的值，这一部分的复杂度为O(wl2) 。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下： 这里有初值 为： 这个式子中， 表示把字串前 个字符分成 段时所形成的最多单词的数目， 表示字串的第 个字符开始的 个字符形成的字串中所能形成的单词数。这里 由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有 的 ，如果 存在（也就是有单词可以在位置 匹配上），且 ，则该位置必然可以匹配上一个单词。把所有这样位置的数目加起来就可以得到 的值了。这样算法的复杂度为O(kl3)。但这里计算还有一个技巧，就是我们可以依次按照 增加， 增加， 增加的顺序计算 的值。这样在 由 增加到 的时候，由于在计算 所对应的 值时可以用 这个方程进行复杂度为O(1)的递推计算，故总复杂度可以降到O(kl2+wl2)。这种被称作双重动态规划的方法，请读者自己好好体会。数据：第四题：CAR的旅行路线又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市的两个机场之间有一条笔直的高速铁路，第i个城市高速铁路的单位里程价格为Ti。任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。那么Car应如何安排到B的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。分析：我们换一种对题目描述的方法，就是给出一张地图，求出某人从某点到另一点的最短距离。这是一个图论中的标准问题，就是在一个无向图中求最短路径的问题。首先，这个人在从起点到终点所可能停下的点都是确定的，就是一个城市的四个机场（其他的时候是没有更换交通工具的自由的）。所以我们可以以所有的机场为顶点，而机场与机场之间的交通路线 为边建立一个图。该图的边权值为机场之间相互通行所需的时间。至于求最短路，我们可以使用一个被称为Dijkstra的算法。该算法的主要思想就是模拟液体等速的在管子内流动，先流到的位置就是离起点较近的位置。在使用算法实现的时候，我们可以把顶点划分为已流到的和未流到的两个部分。依次找出液体从已流到的部分最少还需经过多少时间才能流到未流到的部分，并模拟流的过程。有关该算法的具体内容，请读者自行参见有关图论的算法书籍，这里不赘述。最后，还需注意的是题目中对于一个城市只给出了三个机场的坐标。但我们知道这四个机场是成矩形排列的，而矩形的对角线互相平分。故我们可以先找出这三个机场中相对的两个机场，易知这样的机场就是距离最大的两个机场。然后通过对这两个机场求平均数求出该矩形的中心，再把另一个机场按矩形的中心作对称就可以得出第四个机场的坐标。还有题目中最多可能有400个节点，也就是说可能有80000条边。这些边显然是无法事先计算并保存下来的。但由于在求最短路径的过程中，每一条边最多只会访问两遍，故我们可以采用现用现算的办法。其他在计算点与点之间距离时也要注意对整数取平方时的运算有可能引发整数越界的问题，我们应该先转换成实数再进行计算。该算法的时间复杂度为 ，空间复杂度为O(n)。关于 yuwei 和 zhaoshuang 的报告的一点补充第一题：其实最简单的方法是这样子的：让 x 从 100.00 到 100.00 枚举一下，得到20000个 f(x) ， 取跟 0 最接近的三个f(x)，对应的 x 就是答案了。（提示有时候会扰乱别人的思维）第二题：如果时间不是很严格的话，枚举还是能过的。第三题：这跟我在分区赛前出的一道模拟试题方法类似。不过分区这题的数据巨弱，居然只输出”有多少个位置开始至少可以有一个单词”也能对4/5的点！真是佩服出数据的人第四题：标准算法的题目，不过这题算老题目了 算费用的时候，令 A,B 城市内的路费为 0 的话，就可以直接得到结果，而不需要做4遍 Dijkstra。当然，用 Flody 也可以做2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛提高组试题解题报告题一 均分纸牌（存盘名 NOIPG1）分析：如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。程序清单program NOIPG1; const maxn=100; var i,j,n,step:integer;ave:longint; a:array1.maxnof integer; f:text;filename:string; begin write(Input filename:);readln(filename); assign(f,filename);reset(f); readln(f,n);ave:=0;step:=0; for i:=1 to n do begin read(f,ai); inc(ave,ai); end; ave:=ave div i; for i:=1 to n do ai:=ai-ave; i:=1;j:=n; while ai=0 do inc(i);过滤左边的0 while aj=0 do dec(j);过滤右边的0 while (ij) do begin inc(ai+1,ai);将第i堆牌移到第i+1堆中去 ai:=0;第i堆牌移走后变为0 inc(step);移牌步数计数 inc(i);对下一堆牌进行循环操作 while ai=0 do inc(i);过滤移牌过程中产生的0 end; writeln(step); end.点评：基本题（较易） 本题有3点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0（不是所有的0，如-2，3，0，-1中的0是不能过滤的）；三是负数张牌也可以移动，这是辩证法（关键中的关键）。 题二 字串变换 （存盘名: NOIPG2）分析：本题是典型的广度优先搜索的例子，但如果只采用正向搜索，某些情况下计算量过大，速度过慢，故采取双向搜索且判重并适当剪枝，效果较好。程序清单$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-$M 8192,0,655360program NOIPG2; const maxn=2300; type node=record定义节点数据类型 str:string115;dep:byte; end; str表示字串，其长度不会超过115（长度超过115的字串 不可能通过变换成为目标字串，因为题目限定变换10次之内，且串长 不超过20，即起始串最多可经过5次变换时增长，中间串的最大长度 为20+5*19=115，否则经过余下的步数不可能变为长度不超过20的 目标串），dep表示深度 ctype=array1.maxnof node; bin=0.1; var maxk:byte;c:array 0.1of ctype; x0:array0.6,0.1of string20; filename:string; open,closed:array 0.1 of integer; procedure Init;读取数据，初始化 var f:text;temp:string;i,j:integer; begin for i:=0 to 1 do for j:=1 to maxn do new(ci,j); write(Input filename:);readln(filename); assign(f,filename);reset(f);i:=0; while not eof(f) and (i=6) do begin readln(f,temp); x0i,0:=copy(temp,1,pos( ,temp)-1); x0i,1:=copy(temp,pos( ,temp)+1,length(temp); inc(i); end; maxk:=i-1;close(f); end; procedure calc; var i,j,k:integer;st:bin; d:string;f:text; procedure bool(st:bin);判断是否到达目标状态或双向搜索相遇 var i:integer; begin if x00,1-st=cst,closedst.str then begin 如果到达目标状态，则输出结果，退出 writeln(cst,closedst.dep); halt; end; for i:=1 to closed1-st do if cst,closedst.str=c1-st,i.str then begin 如果双向搜索相遇（即得到同一节点）， 则输出结果（2个方向搜索的步数之和），退出 writeln(cst,closedst.dep+c1-st,i.dep); halt; end; end; procedure checkup(st:bin);判断节点是否与前面重复 var i:integer; begin for i:=1 to closedst-1 do if cst,i.str=cst,closedst.str then begin dec(closedst);exit;如果节点重复，则删除本节点 end; bool(st);如果节点不重复，再判断是否到达目标状态 end; procedure expand(st:bin);扩展产生新节点 var i,j,k,lx,ld:integer; begin inc(openst);d:=cst,openst.str;队首节点出队 k:=cst,openst.dep;ld:=length(d); for i:=1 to maxk do begin 从队首节点（父节点）出发产生新节点（子节点） lx:=length(x0i,st); for j:=1 to ld do begin if (copy(d,j,lx)=x0i,st) and (length(copy(d,1,j-1)+x0i,1-st +copy(d,j+lx,ld)=maxn then exit;如果队列已满，只好退出 inc(closedst);新节点入队cst,closedst.str:=copy(d,1,j-1)+x0i,1-st+copy(d,j+lx,ld); cst,closedst.dep:=k+1;子节点深度=父节点深度+1 checkup(st);检查新节点是否重复 end; end; end; end; Begin for st:=0 to 1 do begin正向(st=0)逆向(st=1)搜索节点队列初始化 openst:=0;closedst:=1; cst,closedst.str:=x00,st;cst,closedst.dep:=0; bool(st); end; repeat 选择节点数较少且队列未空、未满、深度未达到10的方向先扩展 if (open0=closed0) or (closed0=maxn) or (c0,closed0.dep10) then expand(0); if (open1=closed1) or (closed1=maxn) or (c1,closed1.dep10) then expand(1); 如果一方搜索终止，继续另一方的搜索，直到两个方向都终止 if not (open0=closed0) or (closed0=maxn) or (c0,closed0.dep10) then expand(0); if not (open1=closed1) or (closed1=maxn) or (c1,closed1.dep10) then expand(1); until (open0=closed0) or (c0,closed0.dep10) or (closed0=maxn) and (closed1=maxn) or (open1=closed1) or (c1,closed1.dep10); 终止条件：任一方队空（无解）或搜索深度超过10（10步内无解） 或双方均溢出（可能有解也可能无解，应尽量避免，要尽量把节 点数组开大一点，采用双向搜索，采取剪枝措施等） End; BEGIN init; calc; writeln(NO ANSWER!) END.点评：基本题（较难） 考察队列、（双向）广度优先搜索算法及字符串的运算，基本上可以考察出参赛者的数据结构和算法水平。 题三 自由落体（存盘名:NOIPG3）问题描述:在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d1/2*g*(t2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。如下图： 小车与所有小球同时开始运动，当小球距小车的距离 = 0.00001 时，即认为小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。输入：键盘输人：H，S1，V，L，K，n （l=H，S1，V，L，K，n =100000）输出：屏幕输出：小车能接受到的小球个数。输入输出样例输入:5.0 9.0 5.0 2.5 1.8 5输出:1分析：显然，小车太慢（即VVmax）时，一个球也接不到。即在VVmax时输出为0。下面分别求Vmin和Vmax。当第n-1个小球落地的瞬间，小车在小球的右端离小球尚有e=0.00001的距离，小车的这个极小速度就是Vmin。小车从天花板落到地面的时间t1= ,这段时间内小车走了S1-（n-1）-e,所以Vmin= 。当第1个小球落到距小车的上表面为e的瞬间，小车在小球的左端离小球距离为e，小车的这个极大速度就是Vmax。小球从天花板落到离小车上表面为e的距离的时间为t2= ,小车移动的距离为S1+L+e,所以Vmax= 。那么，当VminV=Vmax时，就可接到球了。显然，时间段t2,t1是小车接球的时间，在t2时刻，小车的位置为：左表面离原点距离为S1-V*t2,右表面离原点距离为S1-V*t2+L；在t1时刻，小车的位置为：左表面离原点距离为S1-V*t1,右表面离原点距离为S1-V*t1+L；故小车的接球范围(在小车运动范围外扩展e)为S1-V*t1-e，S1-V*t2+L+e,球的个数就等于接球范围内所包含的0n-1之间的整数的个数.程序清单program NOIPG3; const g=10重力加速度;e=1E-5;小车接受小球的极限距离 var H,s1,v,l,k,t1,t2,Vmin,Vmax:real; n2,n1,num,n:integer; begin readln(h,s1,v,l,k,n);num:=-1; t1:=sqrt(2*h/g);小球落地时间 if h=k+e then t2:=0 else t2:=sqrt(2*(h-k-e)/g);小球落到小车上的最短时间 if s1-v*t2+L+en-1 then n2:=n-1;n2取trunc(s1-v*t2+L+e)与n-1的较小值 if s1-v*t1-en-1 then num:=0 else if (s1-v*t1-e)=trunc(s1-v*t1-e) then n1:=trunc(s1-v*t1-e)小车接受的球的最小编号为n1 else n1:=trunc(s1-v*t1-e)+1; if num=-1 then num:=n2-n1+1;小车接受的球的个数为num writeln(num); end.点评：送分题 本题“物理味”有余而“信息味”不足，连循环语句都用不上！难见的“送分题”，可物理较差的人也得不到多少分哦！ 题四 矩形覆盖（存盘名NOIPG4）问题描述:在平面上有 n 个点（n = 50），每个点用一对整数坐标表示。例如：当 n4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。 这些点可以用 k 个矩形（1=k=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。 输入:键盘输人文件名。文件格式为n kxl y1x2 y2. .xn yn （0=xi,yi=500) 输出:输出至屏幕。格式为：一个整数，即满足条件的最小的矩形面积之和。 输入输出样例d.in :4 21 12 23 60 7屏幕显示：4分析1、本题的难度较大。如果你这样认为：即在假定已用i个矩形（面积和满足最小）覆盖所有点的基础上，穷举所有2个矩形合并成1个矩形（条件是：在所有合并方案中使合并后面积最小），从而使矩形个数减少为i-1那就错了，可是却可以通过前4组测试数据！正确的做法是对不同的K值分别进行计算，好在K值较小，否则.讨论：k=1，只要求出n个点坐标的最大、最小值，就可求得矩形的位置与面积；k=2，有2个矩形，它们只有2种分布形式：左右式（flag=0），上下式（flag=1）对于左右式，显然要先将所有点按横坐标升序排列，可将点1点i-1放入矩形1中，将点i点n放入矩形2中，求两矩形的面积之和；如果面积和比上一个值小，记下；让i从2循环到n,就可完成左右式的全部搜索；对于上下式，先将所有点按纵坐标升序排列，依此类推。k=3，有3个矩形，它们有6种分布形式：要用两重循环进行搜索：设i,j为循环变量，将点1i-1放入矩形1中，点ij-1放入矩形2中，点jn放入矩形3中；点必须在放入前排好序（均为升序）：对于flag=0,所有点按横坐标排序；对于flag=1,所有点按纵坐标排序；对于flag=2,所有点先按横坐标排序，然后点in按纵坐标排序；对于flag=3,所有点先按横坐标排序，然后点1j-1按纵坐标排序；对于flag=4,所有点先按纵坐标排序，然后点1j-1按横坐标排序；对于flag=5,所有点先按纵坐标排序，然后点in按横坐标排序；至于k=4,4个矩形有22种分布形式，实在太复杂！幸好测试数据中没有K=4的情形(似乎有意放了一马？)。据说本题全国没有一人全对！（只要求K=1，2，3）程序清单$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+$M 65520,0,655360program NOIPG4; const maxn=50;maxk=3; type rect=record定义矩形数据类型 l,r,t,b:word;矩形的左边，右边，下边，上边距坐标轴的距离 end; vxy=record定义点数据类型 x,y:word;点的横、纵坐标 end; var ju:array1.maxkof rect; v:array1.maxn,0.2 of vxy;v0:vxy; n,k,i,j,ii,jj:byte;f:text;filename:string; Smin,temp:longint; function intersect(jui,juj:rect):boolean;判断两矩形是否有公共点 var b1,b2,t1,t2,l1,l2,r1,r2:word; begin b1:=jui.b;b2:=juj.b;t1:=jui.t;t2:=juj.t; l1:=jui.l;l2:=juj.l;r1:=jui.r;r2:=juj.r; intersect:=(l2=l1) or (r2=l1) or (l2=r1) and (t2=t1) or (b2=t1) or (b2=b1) and (t2=t1); end; function area(ju:rect):longint;求矩形的面积 var temp:longint; begintemp:=ju.b-ju.t;area:=temp*(ju.r-ju.l);不能直接写成area:=(ju.b-ju.t)*(ju.r-ju.l);因为这样可能会溢出！ end; procedure insert(v:vxy;var ju:rect);将点放入矩形 begin if v.xju.r then ju.r:=v.x; if v.yju.b then ju.b:=v.y; end; procedure init;初始化 begin write(Input filename:);readln(filename); assign(f,filename);reset(f);readln(f,n,k); for i:=1 to n do begin read(f,vi,0.x,vi,0.y); vi,1.x:=vi,0.x;vi,1.y:=vi,0.y; end; for i:=1 to n-1 do按横坐标升序排列各点，存入vi,0 for j:=i+1 to n do if vi,0.xvj,0.x then begin v0:=vi,0;vi,0:=vj,0;vj,0:=v0; end; for i:=1 to n-1 do按纵坐标升序排列各点，存入vi,1 for j:=i+1 to n do if vi,1.yvj,1.y then begin v0:=vi,1;vi,1:=vj,1;vj,1:=v0; end; end; procedure solve;核心计算 begin smin:=maxlongint; case k of 1:beginK=1的情形 ju1.b:=vn,1.y;ju1.t:=v1,1.y; ju1.r:=vn,0.x;ju1.l:=v1,0.x; smin:=area(ju1); end; 2:for jj:=0 to 1 do beginK=2的情形 flag=0,1的情形 ju1.b:=v1,jj.y;ju1.t:=v