当前位置:首页 >> 其它 >>

NOIP2000-2009提高组解题报告


NOI 分区联赛 - 2000 年第六届提高组试题解析
注意:解析和源程序均为 OIBH 站长刘汝佳所写,疏漏在所难免,但至少程序均通过了比赛时使用的测试数据, 所以还是可以一看。 第一题: 大家对正数进制的转换应该比较熟悉吧! (不会的看我的《循序渐进》 ) 负数进制一样。每次取的余数保证在 0~-m-1 之间。 (例如 m=-16,则余数应该在 0~15)就可以直接输出。 所以用系统的“mod”运算符的时候必须注意检查是不是在该范围(可能在 m+1~0) ,否则就调整。 调整的方法是: if 余数<0 then begin 余数=余数-m; 商=商+1; end; 程序见附件。 第二题: 很明显的动态规划。 令 d[i,j,k]为第 i 个数字到第 j 个数字加 k 个乘号所能够达到的最大值。 状态转移方程是: d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举 t, 满足 i<=t<=j-1) 注意到状态转移的时候总是使 k 减小(或不变)的,所以把 k 作为阶段来递推(节约空间) 。 在每个状态中,l=j-i 越来越小,所以从 l=0 递推到 l=n 即: for k:=1 to c do for l:=0 to n do for i:=1 to n do 递推 d[i,j,k] 显然,用两个数组记录 d[i,j,k]和 d[i,j,k-1],就可以只用两维:d[i,j] 于是算法框架就是(请对照我的源程序): 初始化 d1[i,j] for k:=1 to c do begin for l:=0 to n do for i:=1 to n do 用 d1[i,j](k-1 阶段)递推 d2[i,j](k 阶段) d1:=d2; {节省空间,因为递推的时候只与上个阶段有关,故只保留相邻两个阶段} end; 高精度乘法的方法我不是用的模拟手算的过程(这个大家会做吧) ,而用了类似 多项式乘法的方法,因为我觉得这种写法很好记!(大家仔细看看我的 mul 过程) 程序见附件。

第三题: 搜索。数据很小,因此回溯就可以了。程序先预处理,建立矩阵 add[i,j] 即第 j 个串连在第 i 个串之后能增加的长度。0 代表 j 不能增加 i 的后面。 一个需要注意的地方: 计算 add[i,j]的时候要计算最大可能值! 例如: ABABABAB 和 ABABABC 就是 5,不是 1! 现在没有问题了吧。为了方便和直观,我采用递归实现回溯搜索。程序见附件。

第四题: 有同学搜索第一个人,拣了以后第二个人用动态规划,一定能得最优解,但时间效率不大高。 有同学采用贪心,即用动态规划算出第一个人最大能拣的数,再在剩下的数中用动态规划。 反例如下: 191 000 191 第一次是: 1->9->9->1 第二次是:1 和是 21 但显然可以两次把所有的数拣完(22)。 本题是典型的多维动态规划,很象 IOI93 的第四题,另一个算法是网络流,很象 IOI97 第一题, 这里我只分析前者。这道题目的简单之处是阶段很好划分(对角线) ,这种方法我就不介绍了, 因为很多地方都有介绍。这里讲一种怪一点的动态规划^_^ 容易想到的思路是: 令 d[x1,y1,x2,y2]表示甲在 x1,y1,乙在 x2,y2 以后(包括取走(x1,y1))的过程中可以获得的最大和。 则 d[1,1,1,1]就是原问题的解。 但是是否能取数和另一个人是否事先已经到过该格子有关,我们需要设计一种走的方法,使得只根据 x1,y1, x2,y2 就能判断一些关键的格子是否已经到达过。这样,问题才具有无后效性。 为此,我们把路线作如下处理: 1)当两个人路线有交叉的时候,改成等效的,不交叉的。 如下图,1 代表第一个人,2 代表第二个人。X 代表相遇点。 X111 2 1 222X2 12 12 1X1 2X 变成: X222 1 2

111X2 12 12 1X2 1X 反正让 2 走右边就行了。 2)现在 1 在第 y1 列,2 在第 y2 列,让 1 和 2 分别向右走,到达 yy1 和 yy2 列,然后向下走一格 这样如果 yy1 < y2,便是分别取走第 y1~yy1,y2~yy2 列数,否则路线有重复,就取走 y1~yy2 的数。 为了方便连续取数,我用了一个 sum[x,y1,y2]的数组,就是第 x 行的 y1~y2 的数。 请看我的程序中的相应部分。 这样,所有的走法都可以转换成上述的,具有无后效性的结构了。 由于递推是从 d[x1,y1,x2,y2]到 d[x1+1,y1',x2+1,y2'],而总有 x1=x2=x,所以可以把状态节省为:d[y1,y2] 而把 x(当前行)作为阶段来递推: for x:=n-1 downto 1 do begin for y1:=1 to n do for y2:=y1 to n do 枚举 y1'和 y2'作为新的 y1 和 y2,注意保证 y1' >= y1, y2' >= y2(题目规定), y1' <= y2'(刚才的分析),递推 d[y1,y2] d1:=d2; {只记录相邻两个状态} end; 边界是什么呢?当然是从第 n 列的值了,就是 sum[n,y1,n](从 y1 取到 n) 说了这么多,真不知道我说清楚了没有( 好象是没有:-P ) ,如果有什么不明确的地方,请大家在论坛上提出来。 一句话,就是两个人一起,一行一行往下走,每一行可以一次向右走若干步,但是要保证 2 在 1 的右边。 注意最后输出的是 d2[1,1]。如果输出 d1[1,1],n=1 会得到 0。 (为什么?自己想啊) 现在程序就不难写了吧。程序见附件:

第七届( 第七届(2001)分区联赛复赛解题报告(提高组) )分区联赛复赛解题报告(提高组)
俞玮 赵爽 第一题:一元三次方程求解 给出一个三次方程 ,试求它所有的三个根。这里所有的根都在区间 中,并保证方程具有三个实根,且它们之间的 差不小于 1。 分析: 如果是一般的求三次方程根的问题, 那么只能直接使用求根公式, 但这是非常复杂的。 由于题目要求只精确到 0.01, 故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知,我们可以用一个 变量 从-100.000 到 100.000 以步长 0.001 做循环。若 ,则可知在区间 内存在方程的解。这样无论这个区间内的解 是什么,在取两位小数的精度后都与 取两位小数的结果是一样的。故我们就可以把取两位小数精度的 作为问题的 解。另外还有可能方程的根在区间端点 的情况,我们可以通过判断 是否为 0 来获得。 但这种方法由于用到了题目所要求的数值精度小的特殊性,故无法扩展。而在用数值方法求方程根的时候,我们最 常用的方法就是二分法。该方法的应用在于如果确定了方程 在区间 内如果存在且只存在一个根,那么我们可以用 逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间 内存在一 个方程的根,则 这个事实,并重复执行如下的过程: ? 取当前可能存在解的区间 ; ? 若 或 ,则可确定根为 并退出过程; ? 若 ,则由题目给出的定理可知根在区间 中,故对区间 重复该过程;

? 若 ,则必然有 ,也就是说根在 中,应该对此区间重复该过程。 最后,就可以得到精确到 0.001 的根。 再考虑什么样的区间内会有根 。由于题目给出了所有的根都在-100 到 100 之间,且根与根之间差不小于 1 的限制 条件,故我们可知,在 、 、……、 、 这 201 个区间内,每个区间内至多只能存在一个根。这样对除去区间 外 的 其他的区间 ,要么 ,要么 时这个方程在此区间内才有解。若 ,显然 为解;若 ,则可以利用上面所说的方法球 出解来。这样就可求出这个方程的所有解。 最后是输出的解要求排序。我们既可以在求出来之后排序,也可以从小到大的顺序求解,就可以按照升序求出所有 解。 数据: 输入 输出 1 1 -2 -1 2 -1.00 1.00 2.00 2 1 -4.65 2.25 1.4 -0.35 1.00 4.00 3 1 10 -1 -10 -10.00 -1.00 1.00 4 1 -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 份(1<k≤40) ,且每份中包含的单词个数加起来最大(每份中包含的单词 可以重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 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:array[1..maxn]of 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,a[i]); inc(ave,a[i]); end; ave:=ave div i; for i:=1 to n do a[i]:=a[i]-ave; i:=1;j:=n; while a[i]=0 do inc(i);{过滤左边的 0} while a[j]=0 do dec(j);{过滤右边的 0} while (i<j) do begin inc(a[i+1],a[i]);{将第 i 堆牌移到第 i+1 堆中去} a[i]:=0;{第 i 堆牌移走后变为 0} inc(step);{移牌步数计数} inc(i);{对下一堆牌进行循环操作} while a[i]=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-} 度超过 115 的字串 {$M 8192,0,655360} 不可能通过变换成为目标字串,因为题目限定变 program NOIPG2; 换 10 次之内,且串长 const maxn=2300; 不超过 20, 即起始串最多可经过 5 次变换时增长, type 中间串的最大长度 node=record{定义节点数据类型} 为 20+5*19=115, 否则经过余下的步数不可能变为 str:string[115];dep:byte; 长度不超过 20 的 end; {str 表示字串,其长度不会超过 115(长 目标串) ,dep 表示深度}

ctype=array[1..maxn]of ^node; bin=0..1; var maxk:byte;c:array [0..1]of ctype; x0:array[0..6,0..1]of string[20]; 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(c[i,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); x0[i,0]:=copy(temp,1,pos(' ',temp)-1); x0[i,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 x0[0,1-st]=c[st,closed[st]]^.str then begin {如果到达目标状态,则输出结果,退出} writeln(c[st,closed[st]]^.dep); halt; end; for i:=1 to closed[1-st] do if c[st,closed[st]]^.str=c[1-st,i]^.str then begin {如果双向搜索相遇(即得到同一节点) , 则输出结果 个方向搜索的步数之和) (2 , 退出} writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep); halt; end; end; procedure checkup(st:bin);{判断节点是否与前面重 复} var i:integer; begin for i:=1 to closed[st]-1 do if c[st,i]^.str=c[st,closed[st]]^.str then begin

dec(closed[st]);exit;{如果节点重复,则删 除本节点} end; bool(st);{如果节点不重复,再判断是否到达目 标状态} end; procedure expand(st:bin);{扩展产生新节点} var i,j,k,lx,ld:integer; begin inc(open[st]);d:=c[st,open[st]]^.str;{队首节点出 队} k:=c[st,open[st]]^.dep;ld:=length(d); for i:=1 to maxk do begin {从队首节点 (父节点) 出发产生新节点 (子 节点)} lx:=length(x0[i,st]); for j:=1 to ld do begin if (copy(d,j,lx)=x0[i,st]) and (length(copy(d,1,j-1)+x0[i,1-st] +copy(d,j+lx,ld))<=115) then begin {如果新节点的串长超过 115,则不扩展! 即剪掉此枝} if closed[st]>=maxn then exit;{如果队列 已满,只好退出} inc(closed[st]);{新节点入队} c[st,closed[st]]^.str:=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,l d); c[st,closed[st]]^.dep:=k+1;{子节点深度= 父节点深度+1} checkup(st);{检查新节点是否重复} end; end; end; end; Begin for st:=0 to 1 do begin{正向(st=0)逆向(st=1)搜索 节点队列初始化} open[st]:=0;closed[st]:=1; c[st,closed[st]]^.str:=x0[0,st];c[st,closed[st]]^.dep:=0; bool(st); end; repeat {选择节点数较少且队列未空、未满、深度未 达到 10 的方向先扩展} if (open[0]<=open[1]) and not ((open[0]>=closed[0]) or (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0); if (open[1]<=open[0]) and not

(open[1]>=closed[1]) or (c[1,closed[1]]^.dep>10); ((open[1]>=closed[1]) or (closed[1]>=maxn) or {终止条件:任一方队空(无解)或搜索深度超 (c[1,closed[1]]^.dep>10)) then expand(1); 过 10(10 步内无解) {如果一方搜索终止,继续另一方的搜索,直到 或双方均溢出(可能有解也可能无解,应尽量 两个方向都终止} 避免,要尽量把节 if not ((open[0]>=closed[0]) or (closed[0]>=maxn) 点数组开大一点,采用双向搜索,采取剪枝措 or 施等)} (c[0,closed[0]]^.dep>10)) then expand(0); End; if not ((open[1]>=closed[1]) or BEGIN (closed[1]>=maxn) or init; calc; writeln('NO ANSWER!') END. (c[1,closed[1]]^.dep>10)) then expand(1); until (open[0]>=closed[0]) or (c[0,closed[0]]^.dep>10) or (closed[0]>=maxn) and (closed[1]>=maxn) or 点评:基本题(较难) 考察队列、 (双向)广度优先搜索算法及字符串的运算,基本上可以考察出参赛者的数据结 构和算法水平。 题三 自由落体(存盘名:NOIPG3) [问题描述]: 在高为 H 的天花板上有 n 个小球,体积不计,位置分别为 0,1,2,….n-1。在地面上有一个小车(长为 L, 高为 K,距原点距离为 S1) 。已知小球下落距离计算公式为 d=1/2*g*(t^2),其中 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 分析:显然,小车太慢(即 V<=Vmin)或太快(V>Vmax)时,一个球也接不到。即在 V<=Vmin 或 V>Vmax 时输 出为 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= 。 那么,当 Vmin<V<=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], 球的个数就等于接球范围内所包含的 0~n-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+e<0 then num:=0 else n2:=trunc(s1-v*t2+L+e);{小车接受的球的最大编号为 n2} if n2>n-1 then n2:=n-1;{n2 取 trunc(s1-v*t2+L+e)与 n-1 的较小值} if s1-v*t1-e<=0 then n1:=0 else if s1-v*t1-e>n-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) ,每个点用一对整数坐标表示。例如:当 n=4 时,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。各个矩形必 须完全分开(边线与顶点也都不能重合) 。 [输入]: 键盘输人文件名。文件格式为 nk xl y1 x2 y2 ... ... xn yn (0<=xi,yi<=500) [输出]: 输出至屏幕。格式为: 一个整数,即满足条件的最小的矩形面积之和。 [输入输出样例] d.in : 42 11 22 36 07

屏幕显示: 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 为循环变量,将点 1~i-1 放入矩形 1 中,点 i~j-1 放入矩形 2 中,点 j~n 放入矩形 3 中;点必须在放入前排好序(均为升序) :对于 flag=0,所有点按横坐标排序;对于 flag=1,所有点按纵坐标排序;对 于 flag=2,所有点先按横坐标排序,然后点 i~n 按纵坐标排序;对于 flag=3,所有点先按横坐标排序,然后点 1~j-1 按 纵坐标排序; 对于 flag=4,所有点先按纵坐标排序, 然后点 1~j-1 按横坐标排序; 对于 flag=5,所有点先按纵坐标排序, 然后点 i~n 按横坐标排序; 至于 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,655360} program NOIPG4; const maxn=50;maxk=3; type rect=record{定义"矩形"数据类型} l,r,t,b:word;{矩形的左边,右边,下边,上边距坐标轴的距离} end;

vxy=record{定义"点"数据类型} x,y:word;{点的横、纵坐标} end; var ju:array[1..maxk]of rect; v:array[1..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<=r1) and (l2>=l1) or (r2<=r1) and (r2>=l1) or (l2<=l1) and (r2>=r1)) and ((t2<=b1) and (t2>=t1) or (b2<=b1) and (b2>=t1) or (b2>=b1) and (t2<=t1)); end; function area(ju:rect):longint;{求矩形的面积} var temp:longint; begin temp:=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.x<ju.l then ju.l:=v.x; if v.x>ju.r then ju.r:=v.x; if v.y<ju.t then ju.t:=v.y; if v.y>ju.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,v[i,0].x,v[i,0].y); v[i,1].x:=v[i,0].x;v[i,1].y:=v[i,0].y; end; for i:=1 to n-1 do{按横坐标升序排列各点,存入 v[i,0]} for j:=i+1 to n do if v[i,0].x>v[j,0].x then begin v0:=v[i,0];v[i,0]:=v[j,0];v[j,0]:=v0; end; for i:=1 to n-1 do{按纵坐标升序排列各点,存入 v[i,1]} for j:=i+1 to n do if v[i,1].y>v[j,1].y then begin v0:=v[i,1];v[i,1]:=v[j,1];v[j,1]:=v0; end; end; procedure solve;{核心计算} begin

smin:=maxlongint; case k of 1:begin{K=1 的情形} ju[1].b:=v[n,1].y;ju[1].t:=v[1,1].y; ju[1].r:=v[n,0].x;ju[1].l:=v[1,0].x; smin:=area(ju[1]); end; 2:for jj:=0 to 1 do begin{K=2 的情形} {flag=0,1 的情形} ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y; ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x; for i:=2 to n do begin insert(v[i-1,jj],ju[1]);{将第 i-1 点放入矩形 1} ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;{将第 i 至 n 点放入矩形 2} ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x; for ii:=i+1 to n do insert(v[ii,jj],ju[2]); if not intersect(ju[1],ju[2]) then begin{如果两矩形不交叉} temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; 3:begin for jj:=0 to 1 do begin {flag=0,1 的情形} ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y; ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x; for i:=2 to n-1 do begin insert(v[i-1,jj],ju[1]); ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y; ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,jj],ju[2]); ju[3].b:=v[j,jj].y;ju[3].t:=v[j,jj].y; ju[3].r:=v[j,jj].x;ju[3].l:=v[j,jj].x; for ii:=j+1 to n do insert(v[ii,jj],ju[3]); if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; {flag=2 的情形:先竖直划分大矩形;再在右矩形中水平划分} ju[1].b:=v[1,0].y;ju[1].t:=v[1,0].y; ju[1].r:=v[1,0].x;ju[1].l:=v[1,0].x; for i:=2 to n-1 do begin for ii:=1 to n do v[ii,2]:=v[ii,0];{所有点按横坐标升序排列,存入 v[i,2]} for ii:=i to n-1 do{将点 i 至 n 按纵坐标升序排列,存入 v[i,2]} for jj:=ii+1 to n do

if v[ii,2].y>v[jj,2].y then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end;{结果:所有点先按横坐标升序排列,然后点 i 至 n 按纵坐标升序排列} insert(v[i-1,2],ju[1]);{将第 i-1 点放入矩形 1} ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;{将第 i 点放入矩形 2} ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,2],ju[2]);{将第 j-1 点放入矩形 2} ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;{将第 j 至 n 点放入矩形 3} ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=3 的情形} for j:=3 to n do begin for ii:=1 to n do v[ii,2]:=v[ii,0]; for ii:=1 to j-2 do for jj:=ii+1 to j-1 do if v[ii,2].y>v[jj,2].y then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end; ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); for i:=2 to j-1 do begin ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]); ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y; ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x; for ii:=2 to i-1 do insert(v[ii,2],ju[1]); if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or intersect(ju[1],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=4 的情形} for j:=3 to n do begin for ii:=1 to n do v[ii,2]:=v[ii,1]; for ii:=1 to j-2 do for jj:=ii+1 to j-1 do if v[ii,2].x>v[jj,2].x then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0;

end; ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); for i:=2 to j-1 do begin ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]); ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y; ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x; for ii:=2 to i-1 do insert(v[ii,2],ju[1]); if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or intersect(ju[1],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=5 的情形} ju[1].b:=v[1,1].y;ju[1].t:=v[1,1].y; ju[1].r:=v[1,1].x;ju[1].l:=v[1,1].x; for i:=2 to n-1 do begin for ii:=1 to n do v[ii,2]:=v[ii,1]; for ii:=i to n-1 do for jj:=ii+1 to n do if v[ii,2].x>v[jj,2].x then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end; insert(v[i-1,2],ju[1]); ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,2],ju[2]); ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; end; end; begin{主程序} init; solve; writeln(smin); end.

点评:压轴题 据说,本次复赛主要是前三题的竞争,可见本题能得分的人相当少,但是 K=1 应该说是送分的, K=2 也是比较容易的。通过测试,发现在 K=3 的第 4、5 组测试数据中仅用到了 flag=1 的情形,也就是说,只要写 出 flag=1 的程序段就 OK 了(没写 flag=0,2,3,4,5 的同学偷着乐?) 。

第九届全国青少年信息学奥林匹克联赛(N0IP2003) 第九届全国青少年信息学奥林匹克联赛(N0IP2003) 复赛提高组解题报告
作者:湖北省水果湖高中 作者:湖北省水果湖高中 伍先军

题一

神经网络

[分析 分析]本题是比较简单的,但要注意神经元的层数,只输出最大层(输出层)的状态非零的神经元的状态,在中间 分析 层中只有神经元处于兴奋状态时(Ci>0)才会向下一层传送信号。 [PASCAL 源程序 源程序] program NOIP2003_1_Network; const maxn=200;maxp=200; var i,j,n,p,maxlayer:integer; w:array[0..maxp]of longint;{存放边的权值} start,terminal:array[0..maxp]of byte;{存放边的起点与终点} u,c:array[0..maxn]of longint;{存放神经元的阀值与状态值} layer:array[0..maxn]of byte;{存放神经元的层数} f1,f2:text;fn1,fn2,fileNo:string; flag:boolean; begin write('Input fileNo:'); readln(fileNo); fn1:='network.in'+fileNo; fn2:='network.ou'+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n,p); for i:=1 to n do readln(f1,c[i],u[i]); fillchar(layer,sizeof(layer),0); for i:=1 to p do begin readln(f1,start[i],terminal[i],w[i]);{读入边的起点,终点,权} layer[terminal[i]]:=layer[start[i]]+1;{计算终点的层数(比起点大 1)} end; close(f1); maxlayer:=layer[terminal[p]];{求最大层数,即输出层的层数} for i:=1 to n do{计算非输入层的节点 i 的状态值} if layer[i]>0 then begin for j:=1 to p do if (terminal[j]=i) and (c[start[j]]>0){与目标节点 i 有边相连的节点 j 且其状态处于兴奋时 (Cj>0) 才向节点 I 传送信号}

then c[i]:=c[i]+w[j]*c[start[j]]; c[i]:=c[i]-u[i]; end; {输出结果} flag:=true; for i:=1 to n do if (layer[i]=maxlayer) and (c[i]>0) then begin writeln(f2,i,' ',c[i]); flag:=false; end; if flag then writeln(f2,'NULL'); close(f2); end. [点评 点评]基本题。题目阅读起来有些费神,题中边的权值 W,神经元的状态值 C,阀值 U,均未明确指出其取值范围,反 点评 映出命题不严谨。

题二

侦探推理

[分析 分析]基本思路有两种:一是可以穷举 M 个人中有 N 个人始终说假话的所有组合,据此出发,判断每句证词的真 分析 伪,再推断谁是罪犯,但这样做运算量大;二是可以穷举 M 个人中的任意一个是罪犯,由此再来判断每句证词的 真伪,推断谁说真话谁说假话,这样做运算量小得多。这里采用后者。有几点必须注意:一,不能说找到某人是罪 犯或可能是罪犯就完事了,还必须确保是否还有别人是罪犯或可能是罪犯;二,如何处理关于星期的证词呢?还是 可以采用穷举;三,某人的证词可能前后矛盾,在给某人标记他是始终说真话还是始终说假话时,一定要考察他此 前的诚信记录;因此,对某人的诚信记录要有 4 种不同的区分,可用 0 表示此人尚无有效记录(未说过真话也未说 过假话) ,用 1 表示此人说真话,用 2 表示此人说假话,用 3 表示此人说的话与他前面的证词冲突;四,如何判断 最初穷举时设定的前提(某人是罪犯)是否是本题的一个解呢?如果有人的诚信记录为 3,则肯定不是本题的解; 但是也不能强求诚信记录为 2 的人的总数一定要等于 n,而是只要诚信记录为 2 的人不超过 n 且诚信记录为 1 的人 不超过 m-n 即可,因为诚信记录为 0 的人可能说真话也可能说假话,他们只是没有说话,或只说了废话。五,由于 证词要反复用于判断, 可以先剔除其中的无效证词;为处理方便,将有效证词分为两部分: 不含星期的和含星期的。 [PASCAL 源程序 源程序] program NOIP2003_2_Logic; const maxm=20; dow:array[1..7]of string=('Sunday.','Monday.','Tuesday.','Wednesday.', 'Thursday.','Friday.','Saturday.'); var i,j,k,weekday,m,n,p,p1,p2,p3,index,resolution,total1,total2:byte; name:array[1..maxm]of string;{存放人名} witness10,witness20:array[1..100]of byte;{存放说话人的序号,分为两类,前者存放不含星期的证词的说话人的序 号,后者存放只含星期的证词的说话人的序号} witness1,witness2:array[1..100]of string;{存放证词,分为两类,第一类是不含星期的证词,第二类是只含星期的证 词} name0,temp,temp0,temp1,temp2:string; truth,truth0:array[1..maxm]of byte; {存放诚信记录} f1,f2:text;fn1,fn2,fileNo:string; flag:boolean; begin write('Input fileNo:');readln(fileNo); fn1:='logic.in'+fileNo;fn2:='logic.ou'+fileNo; assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);

readln(f1,m,n,p); for i:=1 to m do readln(f1,name[i]); total1:=0;total2:=0; for i:=1 to p do begin{对证词预处理} readln(f1,temp); index:=pos(': ',temp); temp1:=copy(temp,1,index-1);{取得说话人姓名} temp2:=copy(temp,index+2,length(temp)-index-1);{取得证词} if (temp2='I am guilty.') or (temp2='I am not guilty.') then for j:=1 to m do if name[j]=temp1 then begin inc(total1);{total1 表示第一类证词的总数} witness10[total1]:=j;{记下第一类第 total1 条证词的说话人的序号} witness1[total1]:=temp2;{记下第一类第 total1 条证词} break; end; if (pos(' is guilty.',temp2)>0) or (pos(' is not guilty.',temp2)>0) then begin temp0:=copy(temp2,1,pos(' is ',temp2)-1);{取得证词的叙述对象(主语)} flag:=false; for k:=1 to m do if temp0=name[k] then begin flag:=true; break; end; if flag then{如果证词的叙述对象(主语)确实存在} for j:=1 to m do if name[j]=temp1 then begin{记入到第一类证词中} inc(total1); witness10[total1]:=j; witness1[total1]:=temp2; break; end; end; flag:=false; for j:=1 to 7 do if temp2='Today is '+ dow[j] then begin flag:=true; break; end; if flag then{如果证词是关于星期的判断} for j:=1 to m do if name[j]=temp1 then begin{记入到第二类证词中} inc(total2);{total2 表示第二类证词的总数} witness20[total2]:=j;{记下第二类第 total2 条证词的说话人的序号} witness2[total2]:=temp2;{记下第二类第 total2 条证词} break; end; end; close(f1); resolution:=0;{resolution 表示解的个数 }

for i:=1 to m do begin{穷举,第 i 个人为罪犯} if resolution>1 then break;{如果解的个数多于 1 个,则跳出循环} fillchar(truth,sizeof(truth),0);{诚信记录赋初值为 0,表示此人尚无有效证词} for j:=1 to total1 do begin{逐条处理第一类证词} if witness1[j]='I am guilty.' then begin{如果证词为 I am guilty.} if i=witness10[j] then{如果说话人就是罪犯,则本证词为真} case truth[i] of 0:truth[i]:=1;{如果此人的诚信记录为 0,则此人说真话(记为 1)} 2:truth[i]:=3;{如果此人的诚信记录为 2(即以前说假话),则此人自相矛盾(记为 3)} end else{如果说话人不是罪犯,则本证词为假} case truth[witness10[j]] of 0:truth[witness10[j]]:=2;{如果此人的诚信记录为 0,则此人说假话(记为 2)} 1:truth[witness10[j]]:=3;{如果此人的诚信记录为 1(即以前说真话),则此人自相矛盾(记为 3)} end; end; if witness1[j]='I am not guilty.' then begin{如果证词为 I am not guilty.} if i=witness10[j] then{如果说话人是罪犯,则本证词为假} case truth[i] of 0:truth[i]:=2; 1:truth[i]:=3; end else{如果说话人不是罪犯,则本证词为真} case truth[witness10[j]] of 0:truth[witness10[j]]:=1; 2:truth[witness10[j]]:=3; end; end; if (pos(' is guilty.',witness1[j])>0) then begin{如果证词含有 is guilty. } temp:=copy(witness1[j],1,pos(' is guilty.',witness1[j])-1);{取得证词的主语} if name[i]=temp then{如果证词的主语是罪犯,则本证词为真} case truth[witness10[j]] of 0:truth[witness10[j]]:=1; 2:truth[witness10[j]]:=3; end else{如果证词的主语不是罪犯,则本证词为假} case truth[witness10[j]] of 0:truth[witness10[j]]:=2; 1:truth[witness10[j]]:=3; end; end; if (pos(' is not guilty.',witness1[j])>0) then begin{如果证词含有 is not guilty. } temp:=copy(witness1[j],1,pos(' is not guilty.',witness1[j])-1);{取得证词的主语} if name[i]=temp then{如果证词的主语是罪犯,则本证词为假} case truth[witness10[j]] of 0:truth[witness10[j]]:=2; 1:truth[witness10[j]]:=3; end else{如果证词的主语不是罪犯,则本证词为真} case truth[witness10[j]] of

0:truth[witness10[j]]:=1; 2:truth[witness10[j]]:=3; end; end; end;{第一类证词全部处理完毕} if total2>0 then begin{如果有第二类证词存在,处理第二类证词} for k:=1 to m do truth0[k]:=truth[k];{记下第一类证词全部处理完毕后的诚信记录} for weekday:=1 to 7 do begin{穷举,今天是星期日,星期一直到星期六} for k:=1 to m do truth[k]:=truth0[k];{诚信记录还原为第一类证词全部处理完毕后的诚信记录} for j:=1 to total2 do{逐条处理第二类证词} if pos(dow[weekday],witness2[j])>0 then{如果证词中含有当前穷举的星期值,则本证词为真} case truth[witness20[j]] of 0:truth[witness20[j]]:=1; 2:truth[witness20[j]]:=3; end else{如果证词中不含有当前穷举的星期值,则本证词为假} case truth[witness20[j]] of 0:truth[witness20[j]]:=2; 1:truth[witness20[j]]:=3; end; p1:=0;p2:=0;p3:=0; for k:=1 to m do if truth[k]=1 then inc(p1);{p1 表示始终说真话的人的总数} for k:=1 to m do if truth[k]=2 then inc(p2);{p2 表示始终说假话的人的总数} for k:=1 to m do if truth[k]=3 then inc(p3);{p3 表示说过自相矛盾的话的人的总数} if (p1<=m-n) and (p2<=n) and (p3=0) then begin{如果说真话的人的总数小于等于 m-n 且说假话的人的总 数小于等于 n 且没有人说过自相矛盾的话,那么当前罪犯 i 就是本题的一个解} name0:=name[i];{记下罪犯的姓名} inc(resolution);{解的个数增 1} break;{退出星期的穷举} end; end;{星期的穷举完毕} end;{第二类证词处理完毕} p1:=0;p2:=0;p3:=0; for k:=1 to m do if truth[k]=1 then inc(p1); for k:=1 to m do if truth[k]=2 then inc(p2); for k:=1 to m do if truth[k]=3 then inc(p3); if (p1<=m-n) and (p2<=n) and (p3=0) and (name0<>name[i]) then begin{为避免重复计解,此处多加了一个条件: name0<>name[i]} name0:=name[i]; inc(resolution); end; end; if resolution=1 then writeln(f2,name0);{如果只有一个解,则输出罪犯姓名} if resolution=0 then writeln(f2,'Impossible');{如果无解,则输出 Impossible} if resolution>1 then writeln(f2,'Cannot Determine');{如果有多个可能解,则输出 Cannot Determine } close(f2); end. [点评 点评]基本题,比较复杂,重点考查参赛者的字符串运算和逻辑运算,逻辑推理能力。难点主要在于如何处理关于 点评 星期的证词,以及证词之间是否存在矛盾。

题三

加分二叉树

[分析 分析]很显然, 本题适合用动态规划来解。 如果用数组 value[i,j]表示从节点 i 到节点 j 所组成的二叉树的最大加分, 分析 则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j], value[j,j]+value[i,j-1]} 题目还要求输出最大加分树的前序遍历序列,因此必须在计算过程中记下从节点 i 到节点 j 所组成的最大加分二叉 树的根节点,用数组 root[i,j]表示 [PASCAL 源程序 源程序] {$N+} program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; a:array[1..maxn]of byte; value:array[1..maxn,1..maxn]of comp; root:array[1..maxn,1..maxn]of byte; s,temp:comp; f1,f2:text;fn1,fn2,fileNo:string; procedure preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树} begin if p2>=p1 then begin write(f2,root[p1,p2],' '); preorder(p1,root[p1,p2]-1); preorder(root[p1,p2]+1,p2); end; end; begin write('Input fileNo:');readln(fileNo); fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n); for i:=1 to n do read(f1,a[i]); close(f1); fillchar(value,sizeof(value),0); for i:=1 to n do begin value[i,i]:=a[i];{计算单个节点构成的二叉树的加分} root[i,i]:=i;{记录单个节点构成的二叉树的根节点} end; for i:=1 to n-1 do begin value[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分} root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点;需要说明的是,两个节点构成的二叉树,其根节点 可以是其中的任何一个;这里选编号小的为根节点,则编号大的为其右子树;若选编号大的为根节点,则编号小的 为其左子树;因此,最后输出的前序遍历结果会有部分不同,但同样是正确的。如果最大加分二叉树的所有节点的 度数都是 0 或 2,则最后输出的前序遍历结果是唯一的。} end; for d:=2 to n-1 do begin{依次计算间距为 d 的两个节点构成的二叉树的最大加分} for i:=1 to n-d do begin

s:=value[i,i]+value[i+1,i+d];{计算以 i 为根节点,以 i+1 至 i+d 间所有节点为右子树的二叉树的最大加分} root[i,i+d]:=i; {记录根节点 i} for j:=1 to d do begin temp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];{计算以 i+j 为根节点,以 i 至 i+j-1 间所有节点为左子 树,以 i+j+1 至 i+d 间所有节点为右子树的二叉树的最大加分} if temp>s then begin{如果此值为最大} s:=temp;root[i,i+d]:=i+j;{记下新的最大值和新的根节点} end; end; temp:=value[i,i+d-1]+value[i+d,i+d];{计算以 i+d 为根节点,以 i 至 i+d-1 间所有节点为左子树的二叉树的最 大加分} if temp>s then begin s:=temp;root[i,i+d]:=i+d+1; end; value[i,i+d]:=s; end; end; writeln(f2,value[1,n]:0:0);{输出最大加分} preorder(1,n);{输出最大加分二叉树的前序遍历序列} close(f2); end. [点评 点评]基本题。考查了二叉树的遍历和动态规划算法。难点在于要记录当前最大加分二叉树的根节点。疑点是最大 点评 加分二叉树的前序遍历序列可能不唯一。 [PASCAL 源程序 源程序] program NOIP2003_4_Epidemic; const maxn=300;maxp=300; type node=array [0..maxp] of integer;{节点数据类型是一 维数组,其中下标为 0 的元素中存放该节点的孩子节点 个数,下标为 1 的元素中存放该节点的第 1 个孩子的节 点序号,下标为 i 的元素中存放该节点的第 i 个孩子的 节点序号} var i,n,p,min,max,temp,s,smin:integer; a:array[1..maxn] of ^node;{存放 n 个节点的数据, 使 用常规数组容量是不够的,故采用动态数组} f1,f2:text;fn1,fn2,fileNo:string; procedure try(i:integer);{求以 i 为根节点的树中被感染 人数的最少值} var root1,root2,j,k,m,temp,s0:integer;b:node;flag:boolean; begin if a[i]^[0]<=1 then begin{如果根节点 i 的孩子数 为 0 或 1,则已完成一轮递归} if s<smin then smin:=s;{如果此轮递归得到的 感染人数最少,则刷新最少感染人数} exit;

end; s0:=s;{记下上一层递归完后的感染人数} flag:=true;{逻辑标志} for j:=1 to a[i]^[0] do if (a[a[i]^[j]]^[0]>0) then begin{依次切断根节点 i 的第 j 个孩子, 这里进行了优化, 如果根节点 i 的第 j 个孩子是叶子节点则暂不考虑} flag:=false; s:=s0+a[i]^[0]-1;{切断 j 的同时, 被感染的人数 增加了 a[i]^[0]-1 个} if j=1 then root1:=2 else root1:=1;{选根节点 i 的 第 root1 个孩子为新树的根节点} root2:=a[i]^[root1];{求新树的根节点的序号} temp:=a[root2]^[0]; {求新树的根节点的孩子 数} for k:=1 to temp do b[k]:=a[root2]^[k];{记下合 并前新树的根节点的孩子情况} for k:=1 to a[i]^[0] do{开始合并生成新的树} if (k<>j) and (k<>root1) then begin{如果不是 刚被切断的子树或被选作新树根节点的子树} for m:=1 to a[a[i]^[k]]^[0] do{将它们并入 新树} a[root2]^[a[root2]^[0]+m]:=a[a[i]^[k]]^[m]; a[root2]^[0]:=a[root2]^[0]+a[a[i]^[k]]^[0];{新树根节点的

孩子数也随着增加} end; try(root2);{对新树进行递归运算} a[root2]^[0]:=temp;{节点 root2 的孩子数还原} for m:=1 to temp do a[root2]^[m]:=b[m];{节点 root2 的孩子情况数据还原} end; if flag then begin{如果根节点 i 的所有孩子都是 叶子节点} s:=s0+a[i]^[0]-1;{则切断任何一个都是等效的, 故感染人数为 s0+a[i]^[0]-1} if s<smin then smin:=s;{如果此轮递归得到的 感染人数最少,则刷新最少感染人数} exit; end; end; begin write('Input fileNo:');readln(fileNo); fn1:='Epidemic.in'+fileNo;fn2:='Epidemic.ou'+fileNo; [点评 点评]基本题。考查了动态数据结构和递归算法。 点评

assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2); readln(f1,n,p); for i:=1 to n do new(a[i]);{产生动态数组元素} for i:=1 to n do a[i]^[0]:=0;{每个节点的孩子数赋初 值 0} for i:=1 to p do begin{读入节点间的连接情况} readln(f1,min,max); if min>max then begin temp:=min;min:=max;max:=temp{ 序 号 较 小 的 节点为根节点,较大的为子节点} end; inc(a[min]^[0]);{根节点的孩子数增加 1} a[min]^[a[min]^[0]]:=max;{max 成为根节点 min 的第 a[min]^[0]个孩子} end; close(f1); s:=1;smin:=300;try(1); writeln(f2,smin);close(f2); end.

noip2004 提高组解题报告(1)津津的储蓄计划(2009-08-25 21:42:12) 标签:pascal noip2004 提高组 津津的储蓄计划 解题报告 分类:解题报告 题目: 津津的储蓄计划 算法分析: 不用说,这是道简单模拟,水题,但要注意 12 月不能算利息。 题目: 合并果子 算法分析: 算法分析: 这是道贪心题,不是很难,细心可秒杀,稍稍分析一下便可以发现,只要每次都合并最小的两堆便可达到最优解, 再看数据规模,n<=10000,不是太大,使用快排再加上插排便足可完成。 源程序: program fruit; end; var n,i,s,t,j,k:longint; a:array[1..10000] of longint; until i>j; if j>l then quicksort(l,j); procedure quicksort(l,r:longint);//此过程为快排,从哲文 if i<r then quicksort(i,r); 的 blog 上 copy 的,不加注释了,如需要自己去看,网 end; 址: var i,j,x,t:longint; begin begin readln (n); i:=l; j:=r; x:=a[(l+r)div 2]; for i:=1 to n do read (a[i]); repeat quicksort (1,n); while a[i]<x do inc(i); for i:=1 to n-1 do begin while a[j]>x do dec(j); t:=a[1]+a[2]; //合并最小的两堆 if (a[i]>=a[j])and(i<=j) then begin s:=s+t; t:=a[i]; a[i]:=a[j]; a[j]:=t; j:=3; inc(i); dec(j); while (t>a[j]) and (j<=n) do j:=j+1; //找到应插入的位

置,边界特殊判断一下 j:=j-1; n:=n-1; for k:=1 to j-2 do a[k]:=a[k+2]; //这道题较特殊,前面 的往前移两位 a[j-1]:=t; //塞进去 for k:=j to n do a[k]:=a[k+1]; //后面的依然前移,不过 题目: 合唱队形

是一位 end; writeln (s); end.

算法分析: 这是一道有难度的题(起码对我这种菜鸟来说是这样的) ,主要是考 DP,大体框架是这样的:首先枚举中间最高的 人 Ti,然后在他左边求最长上升子序列,在右边则求最长下降子序列,找出最大值。求最长上升(下降)子序列比 较基础,规划方程是 f(i)=max{f(j)+1}(1≤j≤i≤n,Ai<(>)Aj)(n 为中间的最高的人的下标) 。 源程序: program chorus; var m,t,h,i:integer; a,f:array[1..100] of integer; function longest1(s,e:integer):integer; //求最长上升子序列 var i,j,m:integer; begin for i:=s to e do f[i]:=1; for i:=s+1 to e do begin for j:=i-1 downto s do begin if (a[j]<a[i]) and (f[j]+1>f[i]) and (a[i]<a[h]) and (a[j]<a[h]) then f[i]:=f[j]+1; end; end; m:=0; for i:=s to e do if (f[i]>m) and (a[i]<a[h]) then m:=f[i]; longest1:=m; end; function longest2(s,e:integer):integer; //求最长下降子序列 var i,j,m:integer; begin for i:=s to e do f[i]:=1; for i:=s+1 to e do begin for j:=i-1 downto s do begin if (a[j]>a[i]) and (f[j]+1>f[i]) and (a[i]<a[h]) and (a[j]<a[h]) then f[i]:=f[j]+1; end; end; m:=0; for i:=s to e do if (f[i]>m) and (a[i]<a[h]) then m:=f[i]; longest2:=m; end; begin readln (t); for i:=1 to t do read (a[i]); m:=-1; for h:=1 to t do \\枚举中间最高的人 if (t-longest1(1,h-1)-longest2(h+1,t)-1<m) or (m=-1) then m:=t-longest1(1,h-1)-longest2(h+1,t)-1; writeln (m);

end. 总结: 这道题实现起来不是太难,只是比较基础的 DP,可在比赛中不一定能想到方法,所以说还是有一定难度的。

NOIP2005 提高组解题报告
谁拿了最多奖学金(scholar) 题目概述: 已知每个学生的个人信息,求出获得奖学金最多的学生姓名、金额,以及全部奖学金金额。 算法分析: 模拟 其中涉及简单的字符处理,特别要注意数据类型的应用。如:学生姓名可采用 char 和 string 相结合的方法处理,奖 学金金额用 longint 较为适宜。 程序: program scholar; for i:=1 to n do var name:array[1..100] of string; begin a1,a2,a5:array[1..100] of longint; p:=0; a3,a4:array[1..100] of char; if (a1[i]>80) and (a5[i]>=1) then inc(p,8000); n,i,max,total,p:longint; if (a1[i]>85) and (a2[i]>80) then inc(p,4000); maxname:string; if (a1[i]>90) then inc(p,2000); ch:char; if (a1[i]>85) and (a4[i]='Y') then inc(p,1000); f:text; if (a2[i]>80) and (a3[i]='Y') then inc(p,850); begin if p>max then assign(f,'scholar.in');reset(f); begin readln(f,n); max:=p; for i:=1 to n do maxname:=name[i]; begin end; read(f,ch); inc(total,p); while ch<>' ' do end; begin assign(f,'scholar.out');rewrite(f); name[i]:=name[i]+ch; writeln(f,maxname); read(f,ch); writeln(f,max); end; writeln(f,total); readln(f,a1[i],a2[i],ch,a3[i],ch,a4[i],ch,a5[i]); close(f); end; end. close(f); [align=center]过河(River)[/align] 题目概述: 在一条长为 L 数轴上有若干障碍点,每次前进距离为 S 到 T 之间的任意正整数(包括 S,T) ,求走过 L 或大于 L 的 距离,遇到最少的障碍点。 算法分析: 看到题目首先想到的是时间复杂度为 O(L)的递推算法。但是 L 的上限为 10^9,这种算法显然是不行的。仔细思考, 可以得到下面的结论: 存在 N0,当 n> N0 时,n 可以由若干 S 到 T 之间的正整数(包括 S,T)组成。 因此,将障碍点按升序排列, 当两相邻障碍点之间距离较大时, 可适当缩小两障碍点之间距离,但不影响最终结果。

根据上述结论,改进递推算法。由于障碍点之间距离大大缩减,算法的复杂度是可以承受的。 特别地,当 S=T 时需要单独处理。 程序: program river; inc(k); const max=105; end; var a,a1:array[0..101] of longint; end; b:array[0..100] of boolean; end; c,d:array[0..10000] of longint; for i:=1 to 100 do l,s,t,m,ans,low,i,j,k,temp:longint; begin flag:boolean; flag:=true; f:text; for j:=0 to t-1 do procedure init; if not b[i+j] then begin flag:=false;break;end; begin if flag then assign(f,'river9.in');reset(f); begin readln(f,l); low:=i; readln(f,s,t,m); break; for i:=1 to m do read(f,a[i]); end; a[0]:=0;a[m+1]:=l; end; for i:=1 to m-1 do if low<t then low:=t; for j:=i+1 to m do for i:=1 to m+1 do if a[i]>a[j] then begin begin a1[i]:=(a[i]-a[i-1]-low) mod low+a1[i-1]+low; temp:=a[i];a[i]:=a[j];a[j]:=temp; end; end; a:=a1; close(f); for i:=1 to m do d[a[i]]:=1; end; l:=a[m+1]; procedure work1; for i:=1 to l+t-1 do c[i]:=max; begin for i:=1 to l+t-1 do for i:=1 to m do for j:=s to t do if a[i] mod s=0 then inc(ans); if (i-j>=0) and (c[i]>c[i-j]+d[i]) then end; c[i]:=c[i-j]+d[i]; procedure work2; ans:=max; begin for i:=l to l+t-1 do fillchar(b,sizeof(b),false); if ans>c[i] then ans:=c[i]; b[0]:=true; end; for i:=s to t do begin begin init; for j:=0 to 100 do if s=t then work1 if b[j] then else work2; begin assign(f,'river.out');rewrite(f); k:=1; writeln(f,ans); while k*i+j<=100 do close(f); begin end. b[k*i+j]:=true; [align=center]篝火晚会(fire)[/align] 题目概述: 根据一定的移动规则,将初始圆环转化为满足一定条件的目标圆环。 算法分析:

从第一个人处断开,将圆环的问题转化为序列的问题。如果可以,求出目标序列。求出目标序列复杂度 O(n). 求出目标序列右移 0 至 n-1 位置时,不需要移动的人数。将目标序列反转,再求出目标序列右移 0 至 n-1 位置时, 不需要移动的人数。不需要移动的人数最大等价于需要移动的人数最小。复杂度 O(n)。 程序: program fire; end; var a:array[1..50000] of longint; procedure min; b:array[1..50000,1..2] of longint; begin d:array[1..50000] of longint; fillchar(w,sizeof(w),0); w:array[0..50000] of longint; for i:=1 to n do n,ans,i,j,t,max:longint; inc(w[(a[i]-i+n) mod n]); flag:boolean; for i:=0 to n-1 do f:text; if max<w[i] then max:=w[i]; procedure init; for i:=1 to (n+1) div 2 do begin begin assign(f,'fire.in');reset(f); t:=a[i];a[i]:=a[n+1-i];a[n+1-i]:=t; readln(f,n); end; for i:=1 to n do fillchar(w,sizeof(w),0); begin for i:=1 to n do readln(f,b[i,1],b[i,2]); inc(w[(a[i]-i+n) mod n]); inc(d[b[i,1]]); for i:=0 to n-1 do inc(d[b[i,2]]); if max<w[i] then max:=w[i]; end; ans:=n-max; close(f); end; for i:=1 to n do begin if d[i]<>2 then begin flag:=false;exit;end; flag:=true; end; init; procedure circle; if flag then circle; begin if flag then min; a[1]:=1;a[2]:=b[1,1]; assign(f,'fire.out');rewrite(f); for i:=3 to n do if flag then writeln(f,ans) else writeln(f,-1); if b[a[i-1],1]<>a[i-2] then a[i]:=b[a[i-1],1] close(f); else a[i]:=b[a[i-1],2]; end. if a[n]<>b[1,2] then flag:=false; [align=center]等价表达式[/align] 题目概述: 判断两表达式是否等价。 算法分析: 用栈的方法求表达式的值是经典的算法。考虑到多项式的处理比较麻烦,不妨对变量 a 进行多次赋值以判断表达式 是否等价。 值得注意,由于进行数值运算,采用哪种数据类型成为程序是否正确的关键。下面的程序,采取 mod m 的方 法,其中 m 为任意正整数。当对 a 多次赋值,且 m 取不同的较大的正整数时,可以保证算法的正确性。 程序: program equal; ('>','>','>','<','<','>','>'), const max=maxlongint; const com:array[1..7,1..7] of char=(('>','>','<','<','<','>','>'), ('>','>','>','>','<','>','>'), ('>','>','<','<','<','>','>'), ('<','<','<','<','<','=','X'),

('>','>','>','>','X','>','>'), ('<','<','<','<','<','X','X')); var there:char; oped:array[1..1000] of longint; optr:array[1..1000] of char; ned,ntr:int64; a,b:int64; flag:boolean; s:array[0..26] of string; value:array[0..26,-4..4] of int64; ans:array[0..26] of boolean; n,i,j,p,q:longint; f:text; function compare(w1,w2:char):char; var x1,x2:integer; begin case w1 of '+':x1:=1; '-':x1:=2; '*':x1:=3; '^':x1:=4; '(':x1:=5; ')':x1:=6; '#':x1:=7; end; case w2 of '+':x2:=1; '-':x2:=2; '*':x2:=3; '^':x2:=4; '(':x2:=5; ')':x2:=6; '#':x2:=7; end; compare:=com[x1,x2]; end; function operation(a:int64;there:char;b:int64):int64; var i:longint; begin case there of '+':operation:=(a+b) mod max; '-':operation:=(a-b) mod max; '*':operation:=(a*b) mod max; '^':begin operation:=1;for i:=1 to b do operation:=operation*a mod max;end; end; end; function exp(s:string;aa:int64):int64;

var i:int64; begin s:=s+'#'; i:=1; ned:=0;ntr:=1; fillchar(oped,sizeof(oped),0); optr:=''; optr[1]:='#';flag:=false; while not ((s[i]='#')and (optr[ntr]='#')) do begin if s[i] in ['0'..'9'] then begin if not flag then begin ned:=ned+1; oped[ned]:=ord(s[i])-ord('0'); flag:=true; inc(i); end else begin oped[ned]:=oped[ned]*10+ord(s[i])-ord('0'); inc(i); end; end else if s[i]='a' then begin inc(ned); oped[ned]:=aa; inc(i); end else if s[i]=' ' then inc(i) else begin flag:=false; case compare(optr[ntr],s[i]) of '<':begin ntr:=ntr+1;optr[ntr]:=s[i];inc(i);end; '>':begin there:=optr[ntr];ntr:=ntr-1; b:=oped[ned];ned:=ned-1; a:=oped[ned]; oped[ned]:=operation(a,there,b); end; '=':begin ntr:=ntr-1;inc(i);end;

end; end; end; exp:=oped[1]; end; begin

assign(f,'equal.in');reset(f); readln(f,s[0]); readln(f,n); for i:=1 to n do readln(f,s[i]); fillchar(ans,sizeof(ans),true); close(f); for i:=0 to n do 解题报告(来自 OIHB,Snoopy 的奇迹 ) 能量项链 本题是一道很经典的 dp 题目,其实质就是“石子合并问题”的变形,有谈不上什么变形,倒不如说复制更好 一点。我想很多的牛人在这个题目失分的原因多为没弄懂题目的意思就下手做了,把题目看简单了。 简单的说:给你一项链,项链上有 n 颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出 一定的能量。不同的珠子的合并所释放的能量是不同的。问:按照怎样的次序合并才能使释放的能量最多? 我们用 top 表示第 i 颗珠子的头标记,用 wei 表示第 i 颗珠子的尾标记,合并两颗相邻珠子所释放的能量是: Q=top*wei*wei[i+1]或 top*top[i+1]*wei[i+1]; (一个样的) 合并不一定按顺序的,本题所提供的样例也是导致出错的一大原因。 n 个珠子进行一次合并的后,就归结到了 n-1 个珠子的合并的问题。所以我们想到了动态规划。 既然是 dp 题目,必然要满足 dp 的两大条件: 、 1.最优子结构性质; 设 Q[i,j]表示第 i 颗珠子到第 j 颗珠子合并所产生的能量。显然 Q[1,n]表示的是合并产生的总的能量。给定一种 标 号 方 法 , maxQ[1,n] 就 是 所 要 求 的 。 设 最 后 一 次 合 并 在 k 处 进 行 , 则 有 Q[1,n] = Q[1,k] + Q[k+1,n] + top[1]*wei[k]*wei[n]。要 Q[1,n]最大,必然要 Q[1,k],Q[k+1,n]最大。 证明:假设 Q[1,k]不是最大,则必然存在一 Q'[1,k]>Q[1,k]。 那么就有 Q'[1,n]=Q'[1,k]+Q[k+1,n]+top[1]*wei[k]*wei[n]>Q[1,k]。这与 Q[1,n]的最优性矛盾。 最优子结构性质得证。 2.无后效性; 无后效性是显然的,进行某次合并,合并前与合并后状态是相对独立,不相关联,互不影响的。 算法已经定了下来了,关键是怎么实现了。 项链是一个环,而我们处理是对一个串进行的。所以我们要把项链从某处割断展开,不同处的割断对应着不同 的展开方法,也就是对应着不同的标号方法。产生的 maxQ[1,n]也就不同的。所以我们要对这些 maxQ[1,n]进行打 擂,取其最大的一个,即为解了。 dp 的转移方程是: Best=maxQ[1,n] 1<=i<=n (i 表示从第 i 颗珠子处展开,顺次标号) ; Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=n }; 其中 Q[i,i]=0 1<=i<=n; dp 的时间复杂度为 O(n^3),n 种的展开方法对应需要 n 次的 dp,所以时间复杂度为 O(n^4)。空间为 O(n^2)。 显然 O(n^4)过这个题目是有点欠缺的,对的大的数据貌似很容易超时的。 如果仔细想想,我们还是做了很不重复的工作的,不同的展开方式中必然存在着很多的大量的重复运算。于是 还有很大的优化空间,既然展开做了很多的重复的工作,那么就合并起来吧。回到起点,开始的时候为什么我们要 对项链做 n 次的展开呢,基于我们在运算的时候不能够实现第一颗珠子与第 n 颗珠子的相邻性。为了一次 dp 就实 现所以的的珠子的相邻性,我们做如下处理: a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1] (原来的) (延伸的)

if ans[i] then for j:=-4 to 4 do begin value[i,j]:=exp(s[i],j); if value[i,j]<>value[0,j] then ans[i]:=false;break;end; end; assign(f,'equal.out');rewrite(f); for i:=1 to n do if ans[i] then write(f,chr(ord('A')+i-1)); writeln(f); close(f); end.

begin

也就是: a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m] 显然 m=2n-1; 我们对这一串珠子 dp 一次即可得解;dp 方程为: Best=max{Q[i,i+n-1] 1<=i<=n} Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=min(i+n-1,m)} 其中 Q[i,i]=0 1<=i<=m; 显然时间复杂度为 O(n^3),空间为 O(n^2)。min(i+n-1,m)已经对 dp 进行了优化。 (附程序) 到这里我们可以很完美的过这个题目的所以数据了;但还是觉得不够快,想用四边形优化,但想了想显然是不 可以的,W 函数不是单调的。 用树的知识可以更多的优化为(O(n^2*log2n)) 。这里就不多说了,写起来挺烦的。 for i:=1 to m-1 do begin j:=i+p; if j>m then break; for k:=i to j-1 do if f[i,j]<f[i,k]+f[k+1,j]+top*wei[k]*wei[j] then f[i,j]:=f[i,k]+f[k+1,j]+top*wei[k]*wei[j] end; end; procedure print; var i:integer; best:longint; begin best:=0; for i:=1 to n do if best<f[i,i+n-1] then best:=f[i,i+n-1]; writeln(best); end; begin init; doit; print; end.

program Qi(inout,output); var n,m:integer; top,wei:array[1..200] of integer; f:array[1..200,1..200] of longint; procedure init; var i:integer; begin readln(n); for i:=1 to n do read(top); readln; for i:=1 to n-1 do wei:=top[i+1]; wei[n]:=top[1]; m:=n*2-1; for i:=n+1 to m do begin wei:=wei[i-n]; end; end; procedure doit; var p,i,j,k:integer; begin fillchar(f,sizeof(f),0); for p:=1 to n-1 do

top:=top[i-n];

金明的预算方案 如果看过普及组试卷就会发现,对应的第二个题目,也是一个样的背景,提高组只是多了个“主件附件”的的 关系,如果去掉这一点,就全没区别了。也就成了经典的背包问题了。也就是多了这么一点,考试的时候就晕了。 不知道怎么做了。后来才发现是个很简单的 dp 题目。可惜我当时没做出来。 草率的审题,可能会得到这样的算法:dp,对每一个物品做两种决策,取与不取。如果取,满足两个条件:1. 要么它是主件,要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这 两个条件缺一不可的。于是呼,得到如下的动规方程:

f[i,j]:=f[i-1,j]; if (i 为主件 or i 的附件在包中)and (f[i,j]<f[i,j-v]+v*w) then f[i,j]:=f[i,j-v]+v*w; 我们来分析一下复杂度,空间:dp 的阶段为 n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些(因 为要确定附件的主件是否在包中),每个阶段的记录都要 O(n)的空间,所以总的就是 O(n^3)。时间,一个 dp,n^2 的外层循环,内部用布尔量加个主附件的对应数组,为 O(1),和起来就为 O(n^2)的复杂度。 可以看的出,时间的需求为 32000*60,不成问题。空间 32000*60*60,大约要 7.5M 的空间,在 64M 的要求下 是完全可以的过的。如果用上题目中的一个很隐秘的条件: “每件物品都是 10 元的整数倍” ,就可以把速度在提高 十倍。 细细的看题目,还一个很重要的条件我们还没用: “每个主件可以有0个,1个或2个附件” 。这貌似不起眼的 一句话,却给我们降低复杂度提供了条件。想一想,为什么题目要对附件的个数做限制呢,明显是在降低难度。 对于一套物品(包含主件,所以的附件) ,我们称为一个属类,对一个属类的物品的购买方法,有以下5种: 1.一个都不买 2.主件 3.主件+附件1 4.主件+附件2 5.主件+附件1+附件2 这五种购买方法也是唯一的五种方法,也就是说对一属类的物品,我们只有上述的5种购买方法。 于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为 dp 的状态。可以 得到如下的 dp 方程: f[i,j]=max{f[i-1,j]; f[i-1,j-v[i,0]]+v[i,0]*w[i,0]; f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]; f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2]; f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];} 很显然时间复杂度为 O(n^2),空间复杂度为 O(n^2),加上利用“每件物品都是 10 元的整数倍”除以 10 的优 化,本题就很完美的解决了。 (附程序) ; if qx=0 program Qi(input,output); then begin type k:=k+1; g:=k; node=record with w[k] do u:integer; begin v:array[0..2] of integer; u:=0; p:array[0..2] of integer; v[0]:=vx; p[0]:=px; end; for j:=1 to 2 do begin v[j]:=0; var p[j]:=0; end; n,m,k:integer; end; w:array[1..60] of node; end; f:array[0..60,0..3200] of longint; end; g:array[1..60] of integer; for i:=1 to m do procedure init; if qx<>0 var then begin i,j:integer; with w[g[qx]] do vx,px,qx:array[1..60] of integer; begin begin u:=u+1; readln(n,m); k:=0; v:=vx; p:=px; for i:=1 to m do end; begin end; readln(vx,px,qx); for i:=1 to k do

with w do begin for j:=0 to 2 do write('(',v[j],',',p[j],') writeln; end;

');

end; procedure doit; var i,j:integer; begin fillchar(f,sizeof(f),0); for i:=1 to k do with w do begin for j:=1 to n do begin f[i,j]:=f[i-1,j]; if (j>=v[0]) and (f[i,j]<f[i-1,j-v[0]]+v[0]*p[0]) then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0]; if (j>=v[0]+v[1]) and (f[i,j]<f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1]) then

f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1]; if (j>=v[0]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2]) then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2]; if (j>=v[0]+v[1]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[ 2]) then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[ 2]; end; end; end; procedure print; begin writeln(f[k,n]); end; begin init; doit; print; end.

作业调度方案 对本题的评价:题目超长,超简单,失分率最高。 当我在考场上拿到这个题目的时候,考试的紧张的气氛压抑着……读了一遍,不知所云,又读了一遍,依然莫 名其妙,读第三便,I give up !!!考试回来,一看,这样的题目竟然不会,一定是气的死去活来,我就是这样郁 闷了整整的一个月的。 超简单的贪心算法。 简单的说:有 n 个工件要在 m 个机器上加工,每个工件都有 m 到工序,每个工序对应着相应的加工机器。一 个工件的工序必须依次进行。同一台机器同时只能加工一个工件。每个工件的每个工序需要一定的加工时间。问: 加工完所有的工件需要的最少时间是多少? 本题在题目中连算法都给出了,考察的是对题意的理解和数据结构,但本题的规模并没有对数据结构做过高的 要求。应该可以说是本次考试的最简单的题目了,但不是送分题,很多人和我一样都望而止步了。 最简单,按部就班就可以了。 下面是题目中给我们的详尽算法: “当一个操作插入到某台机器的某个空档时(机器上最后的尚未安排操作的部分也可以看作一个空档) ,可以 靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条件(1) (2)的条件下,尽量 靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证约束条件(1) (2)的条件下,插入到最前面 的一个空档。 ” 建议大家在考试的时候使用数组,平时可以用指针写一写…… (附程序) ; program Qi(input,output); var m,n:integer; a:array[1..400] of integer; f:array[1..20,0..1000] of boolean; wu,ti:array[1..20,1..20] of integer; g,time:array[1..20] of integer; procedure init;

var begin i,j:integer; if f[wu[a,g[a]],j] begin then inc(xtime) readln(m,n); else xtime:=0; for i:=1 to n*m do read(a); j:=j+1; readln; end; for i:=1 to n do time[a]:=j-1; begin for k:=j-xtime to j-1 do f[wu[a,g[a]],k]:=false; for j:=1 to m do read(wu[i,j]); end; readln; end; end; procedure print; for i:=1 to n do var begin i,j,best:integer; for j:=1 to m do read(ti[i,j]); begin readln; best:=0; end; for i:=1 to m do end; for j:=1000 downto 0 do procedure doit; if not f[i,j] then var begin i,j,k,xtime:integer; if best<j then best:=j; begin break; fillchar(f,sizeof(f),true); end; fillchar(time,sizeof(time),0); writeln(best); fillchar(g,sizeof(g),0); end; for i:=1 to n*m do begin begin init; inc(g[a]); j:=time[a]+1; doit; xtime:=0; print; while xtime<ti[a,g[a]] do end. 备注:不知道为什么第 6 个数据我的答案是 112.而提供的答案是 116..?? 如果有错...欢迎牛人指出....呵呵.(我的 qq:418539455); 备注:

2k 进制数 这就是传说中的数学题吗?考试前曾沸沸扬扬的流传过这么一段: “今年的题目出于一数学教授,都是写超难的 题目,四个题目有三个是数学题。 ”再加上今年的 maths 库函数登上历史舞台。更让人深信不移:今年要考数学题。 谣言不可信啊,冤死了多少牛们…… 说本题是数学题,到不如说是个找规律的题目。 我们还是用标准的数学方法做一下好了。 本题其实就是个很简单的组合数学问题。 没上过高三做不出也就算了, 上过高三的牛们没做出来,多为放弃的了。 从题中可以看出,w 的值限制着首位的取值。所以我们要对与特殊考虑。比如样例中的 w=7,就限制了首位只 能取0和1。下面关心的就是位数的问题了,w 决定了数的最大的位数,最少的位数要求是2位。k 决定了数的位 权。 抽象的是说了半天也不说不清楚,举个例子吧:就拿样例说,k=3。所以位权是 2^k=8,w=7,决定了数的位数 最大是3{w div k+1} ,最多位的数是最高位最大只能是1{2^((w+1) mod k-1)-1} 。所以我们分两种做讨论:1.位 数是最多位,2.位数小于最多位。 1.位数为最多位(最多位为3) ; 最高位位1: 后面的两位只能在2-7之间取两个不同的数。 显然取法的种数为 c[2,6]。 {c[n,m]=m!/(n!*(m-n)!),

就是组合数} …… …… {这里的最高位只能为1,所以只讨论一种情况} 。 2.位数小于最多位。 2位:这两位只能从1-7之间取数,为 c[2,7]。 …… …… {这里只有两位的情况,所以只讨论这一种情况} 。 从上面的例子,我们可以看出一般的情况: 位权:n=2^k。 位数:l=w div k+1;{当 w mod k=0 时,最高为最大为0,结合下} 最高位最大值:2^((w+1) mod k-1)-1。 {这是我们要知道的几个基本的元素} 下面就是统计满足的数的个数: 1.位数为最多: 最高为取值 x (2<=x<=mhigh); 对于给定最高位 x 都有一些 L 位满足条件的数,这些数的个数为 c[l-1,n-x-1]。 2:位数小于最多: 对于每一个给定的 w 位数都对应着 c[w,n-1]个满足条件的数。 把这些数的个数全部加起来就可以了。 为了简化算法,我们引进一个组合公式: c[n,m]=c[n-1,m-1]+c[n,m-1]; 其中 c[n,m]=m!/(n!*(m-n)! 如果不用高精度,int64 可以过7个点,高精度就可以全过了。 (附程序); program Qi(input,output); var k,w,n,l,mhigh:integer; answer:array[1..200] of integer; c:array[1..512,1..512,1..100] of integer; procedure init; begin readln(k,w); end; procedure ready; var i,j,l,jin,s:integer; begin for i:=1 to 512 do c[1,i,1]:=i; for i:=2 to 512 do begin for j:=2 to i do begin jin:=0; for l:=1 to 100 do begin s:=c[j-1,i-1,l]+c[j,i-1,l]+jin; c[j,i,l]:=s mod 10; jin:=s div 10; end; end; end; end; procedure plus(n,m:integer); var i,jin,s:integer; begin jin:=0; for i:=1 to 100 do begin s:=answer+c[n,m,i]+jin; jin:=s div 10; answer:=s mod 10; end; end; procedure doit; var i:integer; begin ready; n:=1; for i:=1 to k do n:=n*2; n:=n-1; l:=w div k+1; mhigh:=1; for i:=1 to (w+1) mod k-1 do mhigh:=mhigh*2; mhigh:=mhigh-1;

for i:=2 to l-1 do if i<=n then plus(i,n); for i:=1 to mhigh do if l-1<=n-i then plus(l-1,n-i); end; procedure print; var i,j:integer; begin j:=100; end.

while answer[j]=0 do j:=j-1; for i:=j downto 1 do write(answer); writeln; end; begin init; doit; print;

NOIP2007 提高组解题报告
前言 本次 noip 大概是几年来最简单的一次,更多考察的是基础算法以及编写代码的能力。可以说前两题细心+后两题 乱搞就能达到 SD 的一等线。 因此使得某些菜的分数和大牛的区分不明显。这篇题解可能更多是对参加此次 noip 的感想和体会。感觉有必要记 录一下,如果能对别人有所帮助那更好。 受本人水平所限, 题目中算法并非是最优的, 但确保正确以及能在规定时间出解。 coding 照着考试时候的重新写的, 基本没什么改动,除了第四题加了一点常数优化得以卡着时限 ac。保证在我的 PentiumM587+496MB 的机器上能跑 出 400 分来。 让大牛们见笑了。 为控制长度,题目描述不在此赘述,网上一搜就有。 第一题 count 题目分析 拿到这道题目,相信很多人都和我一样比较意外。排序+线性的处理即可。放到 PJ 中也许能更好点。 数据规模 n 在 200000 因此 o(nlogn)排序可过。数据范围在 1,500,000,000<maxlongint(2,147,483,647),所谓使用高精 度存储完全没有必要。 应该大部分人和我一样直接写个 QSORT 了事。但在初评成绩公布之前,听到有人说有 40%的特殊数据专门针对 qsort。尽管最后发现是虚惊一场。 qsort 在一定情况下的最差表现为 o(n^2)。 还好 noip 的数据是很温柔的。不然因为这里而失误会冤枉死。这也是经验不足的表现。 所以可以考虑严格 o(nlogn)排序方法或者使用平衡树。参考程序仍然使用了 qsort。 这道题目适合用来初学者练习排序。 参考程序 program count; a[jj] := kk; var inc(ii); a: array[0..200000] of longint; dec(jj); n, i, tot: longint; end; procedure qsort(l, r: longint); until ii > jj; var if ii < r then qsort(ii, r); ii, jj, kk, mid: longint; if jj > l then qsort(l, jj); begin end; ii := l; begin jj := r; assign(input, 'count.in'); mid := a[(ii+jj) shr 1]; assign(output, 'count.out'); repeat reset(input); while a[ii] < mid do inc(ii); rewrite(output); while a[jj] > mid do dec(jj); readln(n); if ii <= jj then begin for i := 1 to n do read(a[i]); kk := a[ii]; qsort(1, n); a[ii] := a[jj]; tot := 1;

write(a[1]); end; for i := 2 to n do begin end; writeln(' ', tot); if a[i] = a[i-1] then begin inc(tot); close(input); end else begin close(output); writeln(' ', tot); end. write(a[i]); tot := 1; 第二题 expand 题目分析 看到这道题目,依然没有什么技术含量。所需要的就是细心。 特别注意的几个地方: 输入长度虽然在 100 之内,但是答案最大为 6000 多,因此答案不能用 string 存储,可以使用 ansistring 或者不存储 边处理边输出。 只有两个点需要倒序输出。只有一个点存在类似 d-d 的情况。所以数据还是非常弱的。 注意如果一边为数字一边为字母是不可以的。 特别注意连续'-'或者'-'在首尾的情况。 参考程序写的比较笨拙。但对于这种 ws 题目,细心和准确远比速度更重要。 参考程序 program expand; end; var if (ch1 >= 97) and (ch1 <= 122) and (ch2 >= 97) and p1, p2, p3, ii, jj, i, ch1, ch2: longint; (ch2 <= 122) then begin s: string; case p1 of procedure print(st, en: longint); 1: print(ch1+1, ch2-1); begin 2: print(ch1-31, ch2-33); if p3 = 1 then 3: print0(ch1+1, ch2-1); for ii := st to en do begin end; for jj := 1 to p2 do write(chr(ii)); exit; end end; else end; for ii := en downto st do begin write('-'); for jj := 1 to p2 do write(chr(ii)); end; end; begin end; assign(input, 'expand.in'); procedure print0(st, en: longint); assign(output, 'expand.out'); begin reset(input); for ii := st to en do begin rewrite(output); for jj := 1 to p2 do write('*'); readln(p1, p2, p3); end; readln(s); end; write(s[1]); procedure judge; for i := 2 to length(s)-1 do begin begin if s[i] = '-' then begin ch1 := ord(s[i-1]); judge; ch2 := ord(s[i+1]); end else begin if ch1 < ch2 then begin write(s[i]); if (ch1 >= 48) and (ch1 <= 57) and (ch2 >= 48) and end; (ch2 <= 57) then begin end; if p1 = 3 then print0(ch1+1, ch2-1) else print(ch1+1, writeln(s[length(s)]); ch2-1); close(input); exit; close(output);

end. 第三题 game 题目分析 这道题目,一眼就能看出是个 dp,稍微一想,每一行都是独立的,可以分别处理再累加答案。 { 摘自 yy 大牛的题解: f[i,j]=max{f[i+1,j]+w*a[i] , f[i,j-1]+w*a[j]} 按照 j-i 的大小进行 DP 即可,每一层循环之后,另 w:=w+w。其中 j-i 的最大值是 m-1,最小值是-1。 最后,max{f[i,i-1],i=0..m}就是所求。 } 上面的 f[i,j]表示从左面取到 i,从右面取到 j 的最优值。 考试中我所写的方程是 f[i, j] = max{f[i-1, j-1] + a[j]*2^i, f[i-1, j] + a[m-i+j+1]*2^i} 其中 f[i, j]表示一共取出 i 个数,其中从左侧取 j 个,那么右侧就是取 i-j 个,所能取到的最优值。 初始值 f[1, 1] = a[1]*2; f[1, 0] = a[m]*2; 最后 max{f[m, i], i=0..m}即为所求。 其实本质上是一样的。 dp 说完了,再讲高精。由于数据规模比较大,直接高精好像会 tle。需要压位,就是扩大进制数。 说也走运,当时一开始考虑使用万进制是因为题目中 a[i]范围到 1000,不想麻烦的处理 a[i],最后甚至想改回十进 制。 这样时间复杂度是 o(knm^2),k 是高精度的时间常数。 参考程序中使用了较多的 procedure&function,ws 的 4kb 的 code,和考试时候写的基本一致。尽管使得程序冗长, 但是感觉分段处理更易于理解和检查。考试时候最后检查,发现了高精中的一个小错误。挽回了 60 分。 现在看来还是有累赘。比如计算 2^n 后可以记录,不必重复计算。 最后想说,这道题目想法不难,关键是千万不要写错。要是因为一些小失误而挂掉真是能欲哭无泪。不过题目中给 出了 3 个样例,因此还是比较好调试的。 如果使用 double/int64/extended 可以过 6 个点。搜索也能有部分分。 参考程序 program game; if now[ii] >= 10000 then begin var inc(now[ii+1]); f: array[0..80, 0..80, 0..20] of longint; dec(now[ii], 10000); ans, max, temp, now: array[0..20] of longint; end; a: array[0..80] of longint; if now[lennow+1] > 0 then inc(lennow); lennow, lenmax, lenans, ii, lent, n, m, dep, i, j: longint; end; procedure print; procedure time(x: longint); begin begin write(ans[lenans]); fillchar(temp, sizeof(temp), 0); for ii := lenans-1 downto 1 do begin lent := lennow; if ans[ii] < 1000 then write(0); for ii := 1 to lent do begin if ans[ii] < 100 then write(0); temp[ii] := a[x] * now[ii]; if ans[ii] < 10 then write(0); end; write(ans[ii]); for ii := 1 to lent-1 do begin end; inc(temp[ii+1], temp[ii] div 10000); end; temp[ii] := temp[ii] mod 10000; procedure timenow; end; begin while temp[lent] > 10000 do begin for ii := 1 to lennow do begin temp[lent+1] := temp[lent] div 10000; inc(now[ii], now[ii]); temp[lent] := temp[lent] mod 10000; end; inc(lent); for ii := 1 to lennow do end;

end; procedure add(x, y: longint); begin if lent < f[x, y, 0] then lent := f[x, y, 0]; for ii := 1 to lent do begin inc(temp[ii], f[x, y, ii]); if temp[ii] >= 10000 then begin inc(temp[ii+1]); dec(temp[ii], 10000); end; end; if temp[lent+1] > 0 then inc(lent); end; procedure tihuan(x, y: longint); begin f[x, y, 0] := lent; for ii := 1 to f[x, y, 0] do f[x, y, ii] := temp[ii]; end; function panduan(x, y: longint): boolean; begin if f[x, y, 0] > lent then exit(false); if f[x, y, 0] < lent then exit(true); for ii := lent downto 1 do begin if f[x, y, ii] > temp[ii] then exit(false); if f[x, y, ii] < temp[ii] then exit(true); end; exit(false); end; procedure huanmax(x: longint); begin lenmax := f[m, x, 0]; for ii := 1 to lenmax do max[ii] := f[m, x, ii]; end; function panmax(x: longint): boolean; begin if lenmax > f[m, x, 0] then exit(false); if lenmax < f[m, x, 0] then exit(true); for ii := lenmax downto 1 do begin if max[ii] > f[m, x, ii] then exit(false); if max[ii] < f[m, x, ii] then exit(true); end; exit(false); end; procedure addans; begin if lenans < lenmax then lenans := lenmax; for ii := 1 to lenans do begin inc(ans[ii], max[ii]); if ans[ii] >= 10000 then begin inc(ans[ii+1]);

dec(ans[ii], 10000); end; end; if ans[lenans+1] > 0 then inc(lenans); end; begin assign(input, 'game.in'); assign(output, 'game.out'); reset(input); rewrite(output); readln(n, m); lenans := 0; fillchar(ans, sizeof(ans), 0); for dep := 1 to n do begin for i := 1 to m do read(a[i]); fillchar(f, sizeof(f), 0); fillchar(max, sizeof(max), 0); f[1, 1, 0] := 1; f[1, 1, 1] := a[1] * 2; f[1, 1, 0] := 1; f[1, 0, 1] := a[m] * 2; fillchar(now, sizeof(now), 0); now[1] := 2; lennow := 1; for i := 2 to m do begin timenow; time(i); add(i-1, i-1); tihuan(i, i); time(m-i+1); add(i-1, 0); tihuan(i, 0); for j := 1 to i-1 do begin time(j); add(i-1, j-1); tihuan(i, j); time(m-i+j+1); add(i-1, j); if panduan(i, j) then tihuan(i, j); end; end; huanmax(0); for i := 1 to m do begin if panmax(i) then huanmax(i); end; addans; end; print; close(input);

close(output);

end.

第四题 core 题目分析 尽管这道题目是最有价值写题解的,但是我这篇应该会让人失望。 目前最快的算法是 o(n)的。还有很多诸如 o(nlogn)、o(n^2)的等等。然后 sdyy 告诉我他的 o(n^3)的。然后我这个是 跟着题目描述上当的 o(kn^3)的,k 是直径的条数。 所以写出考试时候的程序发现自测第九个点要 1.5s,优化后总算在 0.9xs 出解。 看到题目,发现终于在 noip 见到图了...激动一个。仔细读完题{也许这就进了陷阱},看到 n=300,立刻想 o(n^3)的 算法应该可以。 但是不幸的在现场没有发现一个不能算常数的常数...至少从 oibh 上下了数据之后,我就知道自己的 10 分时怎么丢 掉的了。 先说一下我的相当低效的算法吧。基本上是按照题意的笨做法。 首先 floyd 全局最短路{这就比较低效},然后 n^2 枚举出最长路径起始点并且记录{更低效了}。对于每一条最长路 径,先 n^2 求出经过的每个点。然后从一个方向枚举路径上每个点,计算出从这个点出发的最长的不超过 s 的路径 并且计算出各个点到该路径的最短距离。统计最短距离的最大值,如果已经不比当前答案更优了就可以枚举下一条 路径了。感觉讲的还是不怎么清楚,有兴趣的就看一下我的 ws 程序吧。 由于最长路径条数 k 最坏情况下是是 o(n^2),因此第九个点甚至是可以看作是 o(n^5)。没办法算法差只能对常数优 化苛刻点了。 真正考试的时候想不出好算法,能这样也还好。 比较奇怪的问题,使用 floyd 时记录中间的节点竟然更慢了? spoj 上也出现了这道题的加强形式,好像 n= 10000。显然就需要更好的算法了。那样就请看别的题解吧。我水平实 在有限。 参考程序 program core; const maxn = 65536; var n, s, i, j, aa, bb, k, temp, st, en, ans, tou, max, len, dep, now: longint; w, f, mid: array[0..300, 0..300] of longint; p: array[0..50000, 1..2] of integer; a: array[0..300] of integer; d: array[0..300] of longint; begin assign(input, 'core.in'); assign(output, 'core.out'); reset(input); rewrite(output); readln(n, s); for i := 1 to n do begin w[i, i] := 0; f[i, i] := 0; for j := i+1 to n do begin f[i, j] := maxn; f[j, i] := maxn; w[i, j] := maxn; w[j, i] := maxn; end;

end; for i := 2 to n do begin read(aa, bb); readln(w[aa, bb]); w[bb, aa] := w[aa, bb]; f[aa, bb] := w[aa, bb]; f[bb, aa] := w[aa, bb]; end; for k := 1 to n do begin for i := 1 to n do begin for j := 1 to n do begin if f[i, j] > f[i, k] + f[k, j] then f[i, j] := f[i, k] + f[k, j]; end; end; end; fillchar(p, sizeof(p), 0); tou := 0; max := 0; for i := 1 to n-1 do begin for j := i+1 to n do begin if f[i, j] > max then begin p[1, 1] := i; p[1, 2] := j; tou := 1; max := f[i, j];

end else begin if f[i, j] = max then begin inc(tou); p[tou, 1] := i; p[tou, 2] := j; end; end; end; end; ans := maxn; for dep := 1 to tou do begin len := 0; st := p[dep, 1]; en := p[dep, 2]; now := en; while f[now, st] <> w[now, st] do begin for k := 1 to n do begin if (f[st, now] = f[st, k] + w[k, now]) and (k <> now) then begin inc(len); a[len] := now; now := k; break; end; end; end; inc(len); a[len] := now;

inc(len); a[len] := st; for i := 1 to len do begin temp := 0; st := a[i]; for k := 1 to n do begin d[k] := f[st, k]; end; for j := i+1 to len do begin en := a[j]; if f[st, en] > s then break; for k := 1 to n do begin if d[k] > f[k, en] then d[k] := f[k, en]; end; end; for k := n downto 1 do begin if d[k] > temp then begin temp := d[k]; if temp >= ans then break; end; end; if temp < ans then ans := temp; end; end; writeln(ans); close(input); close(output); end.

后记 这次 noip 还有一些特点,比如难度随题号递增了,不像 06 年那样让人一头雾水。测试数据给的也很充分,给我这 种懒人以方便,但是无形中降低了难度。因为如何自己设计测试数据也是十分有学问的事情。并且过分依赖题目所 给的测试数据也会很容易陷入出题人的圈套中。 数据还是和去年一样的温柔。 比如最后一道题目 yy 大牛使用 integer 可以 ac。 不管怎么评价 noip 的题目,它也不能改变,只有让我们去努力适应。明年的题目是否会加大难度呢?数据依然会 很让人很舒服么?总之可以说,作为纯普及性质的 noip,所需要的并不是特别高深的算法,而是需要一种弱题不失 误,难题不手软的作风。

NOIP2008 提高组解题报告
1.笨小猴 【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数,输出“Lucky Word”和 差值;否则输出“No Answer”和 0. 【题目类型】 模拟 【建议编程时间】 10 分钟(细心一些,避免出错) 。 【解题分析】 1、读入字符串(文件) 2、构造一个数组,记录 a-z 各字符出现的次数。枚举字符串中每个字符,将该字符对应数组元素加一。

3、枚举数组中 a-z,找出最大值和非零最小值,求出它们的差。 4、判断差值是否为素数,数据规模很小,可用试除法。注意 0,1 的特殊情况。 5、输出,注意大小写、换行符。 2.火柴棒等式 【问题描述】 给 n 根火柴棒,问能拼出多少种形如“A+B=C”的等式。 【题目类型】 搜索 【建议编程时间】 30 分钟。若某些问题未考虑到,调试 20 分钟。 【解题分析】 1、 读入整数 n,减去加号和等号需要的 4 根火柴。 2、 采用搜索方法,先递归枚举火柴拆分成每个数字对应根数(存在数组里) ,再枚举加号和等号的位置,计算对 应的 A,B,C,最后判断 A+B=C,统计总数。 3、 输出 tot,注意换行。 【编程注意】 1、 注意最高位不能为零,即除非该数为零,最高位不为零。 2、 递归函数两个入口,表示当前剩余火柴根数、当前位数。枚举下一根火柴的数字,记录,递归(剩余-当前火 柴,位数+1) 。 3、 当剩余根数为零时,枚举 A,B,C 的拆分方式。 4、 计算 A 时, 先将 A 设为首位, 若首位为零且位数大于 1, 则失败退出 (最高位不为零) 从首位+1 到末位: A*=10, A+=a[i]. 字符串转为整数的常用方法。 5、 注意个数为 0 时的特殊处理。 3.传纸条 【问题描述】 从 m*n 的矩阵中,只能向下、右两个方向走,找到两条互不相交的路径,使得两条路径上的权值之和最大。 【题目类型】 双线程动态规划 【建议编程时间】 40 分钟。这里的编程时间包括调试时间。 【空间复杂度】 约 27M,全局变量完全可承受。50*50*50*50*sizeof(int)=2.5*10^7. 【解题分析】 1、 读入矩阵,注意行列。 2、 采用一个四维数组记录当前两条路走到的位置(i1,j1,i2,j2)时取得的最大值,初始化为 0,表示不可能到达。 (0,0,0,0)为 1,最后减 1 输出。 3、 一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来,故内部有四个 if,分别表示两个 点从上上、上左、左上、左左继承来时,加上当前两个点所取得的最大值。例如,f[i][j][k][l] = max{f[i][j][k][l], f[i-1][j][k-1][l] + a[i][j] + a[k][l]},表示两点均从上面位置走来。 4、 输出右下角处的最大值 f[m][n][m][n],注意换行。 【编程注意】 1、 在数组边界处特殊处理,避免数组越界。 2、 若待继承的点最大值为零,则停止判断,不能从这里走来。 3、 显然,非矩阵右下角的汇合点,两个位置不能重合(否则路径相交) ,若重合则最大值为 0,不可达。 4.双栈排序 【问题描述】 通过两个栈 S1,S2,将一个给定的输入序列升序排列。定义 a 操作将元素压入 S1 栈,b 操作从 S1 栈中取出栈顶元

素,c 操作将元素压入 S2 栈,d 操作从 S2 栈中取出栈顶元素。求字典序最小的操作序列。 【建议编程时间】 贪心算法 40 分钟(包括调试) ,可得 30 分。 【解题分析】 (贪心算法,30 分) 1、读入序列 2、若能进入 S1 栈,则执行 a 操作,进入 S1 栈;重复执行 b 操作,将 S1 栈中当前元素弹出,直到不可行为止。 3、若能进入 S2 栈(c) ,并将 S2 中符合要求的元素弹出(d) ,直到不可行。 4、若两栈均无法进入,失败退出 5、输出操作序列 【判断是否能进栈】 若当前元素小于栈顶元素,则进栈,栈元素个数自增;否则不能进栈。因为栈中必须保持降序,这样才能保证依次 输出时升序。 【判断是否能出栈】 用全局变量表示当前取出的最大元素。若栈内元素个数不为零,且当前栈顶元素等于最大元素+1(因为元素是 1-n 依次取出的) ,则取出该元素,最大元素自增,栈元素个数自减。 【正确解题分析】 (转载,感谢提供解题方法的大牛) 这道题大概可以归结为如下题意: 有两个队列和两个栈,分别命名为队列 1(q1),队列 2(q2),栈 1(s1)和栈 2(s2).最初的时候,q2,s1 和 s2 都为空,而 q1 中有 n 个数(n<=1000),为 1~n 的某个排列. 现在支持如下四种操作: a 操作,将 q1 的首元素提取出并加入 s1 的栈顶. b 操作,将 s1 的栈顶元素弹出并加入 q1 的队列尾. c 操作,将 q1 的首元素提取出并加入 s2 的栈顶. d 操作,将 s2 的栈顶元素弹出并加入 q1 的队列尾. 请判断,是否可以经过一系列操作之后,使得 q2 中依次存储着 1,2,3,…,n.如果可以,求出字典序最小的一个操作序列. 这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二 分图的算法. 注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数 q1[i]和 q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在 于同一个栈中,只是压入了同一个栈).实际上,这个条件 p 是:存在一个 k,使得 i<j<k 且 q1[k]<q1[i]<q1[j]. 首先证明充分性,即如果满足条件 p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入 q1[k]的时候栈内情况如下: …q1[i]…q1[j]… 因为 q1[k]比 q1[i]和 q1[j]都小,所以很显然,当 q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则 q2 中的数字 顺序就不是 1,2,3,…,n 了). 而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在 q1[i]之前弹出.而 q1[j]>q1[i],这显然是不正确的. 接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件 p.这里我们来证明它的逆否命题, 也就是"如果不满足条件 p,那么这两个数一定可以压入同一个栈." 不满足条件 p 有两种情况:一种是对于任意 i<j<k 且 q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意 i<j,q1[i]>q1[j]. 第一种情况下,很显然,在 q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对 q1[j]产生任何影响(这里可能有 点乱,因为看起来,当 q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数 r,满足 j<k<r 且 q1[r]<q1[j]<q1[k], 也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个 r,所以说 q1[k]对 q1[j]没有影响). 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证.

此时,条件 p 为 q1[i]和 q1[j]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足 1<=i<j<=n,检查是否存在 i<j<k 满足 p1[k]<p1[i]<p1[j].如果存在,那么在点 i 和点 j 之 间连一条无向边,表示 p1[i]和 p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~ 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点 都分到了两个栈中. 此时我们只考虑检查是否有解,所以只要 O(n)检查出这个图是不是二分图,就可以得知是否有解. 此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成 1 和 2 两种颜色,那么结点染色为 1 对应当前结点被压入 s1,为 2 对应被压入 s2. 为了字典序尽量小,我们希望让编号小的结点优先压入 s1. 又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色 为 1 并从它开始 DFS 染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做 的,只不过是模拟之后输出序列啦~ 还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在 k 使得 p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了 O(n^3).解决方法就是,首先预处理出数组 b,b[i]表示从 p1[i]到 p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查 b[j+1]是否小于 p1[i]且 p1[i]是否小于 p1[j]就可以了. 附代码(除去注释不到 100 行),带注释.代码中的 a 数组对应文中的队列 p1. 已经过掉所有标准数据,以及 5 7 2 4 1 6 3 这组让很多贪心程序挂掉的数据~ #include <iostream> color[adj[temp]] = 3 - color[i]; //进行染色 dfs(adj[temp]); //DFS using namespace std; } if (color[adj[temp]] == color[i]) return false; const int nn = 1002, mm = nn * 2, inf = 1000000000; //如果两个相邻结点染色相同,说明此图不 int n, tot, now; 是二分图,返回无解 int a[nn], b[nn], head[nn], color[nn]; temp = next[temp]; int adj[mm], next[mm]; } int stack[3][nn]; return true; bool result; } void addEdge(int x, int y) //加边 { ++ tot; adj[tot] = y; next[tot] = head[x]; head[x] = tot; } bool dfs(int i) //DFS 染色,检查图是否是二分图的经典算 法 { int temp = head[i]; while (temp) //邻接表,检查每一条边 { if (! color[adj[temp]]) //如果与当前结点的结点 还未染色 { int main() { freopen("twostack.in", "r", stdin); freopen("twostack.out", "w", stdout); //输入 scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); //预处理 b 数组 b[n + 1] = inf; for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL //枚举数对(i,j)并加边 tot = 0; for (int i = 1; i <= n; ++ i)

for (int j = i + 1; j <= n; ++ j) if (b[j + 1] < a[i] && a[i] < a[j]) { addEdge(i, j); addEdge(j, i); } //DFS 染色 memset(color, 0, sizeof(color)); result = true; for (int i = 1; i <= n; ++ i) //每次找当前未染色的编 号最小的结点,并染颜色 1 if (! color[i]) //当前位置尚未被染色 { color[i] = 1; if (! dfs(i)) //染色时出现矛盾,此时图不是 一个二分图,即无法分配到两个栈中 { result = false; //记录无解 break; } } if (! result) //无解 printf("0"); else //有解 { //模拟求解 now = 1; for (int i = 1; i <= n; ++ i)

{ //将当前数字压入对应的栈 if (color[i] == 1) printf("a "); else printf("c "); stack[color[i]][0] ++; stack[color[i]][stack[color[i]][0]] //this will work even if stack[1][0] = 0

=

a[i];

//循环检查,如果可以的话就从栈顶弹出元 素 while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now) { if (stack[1][stack[1][0]] == now) { printf("b "); stack[1][0] --; } else if (stack[2][stack[2][0]] == now) { printf("d "); stack[2][0] --; } now ++; } } }

结语 以上四道题全部做完,需要约 140 分钟,距离三小时的时限还有 40 分钟,可以编一些特殊的、极端的数据对程序 进行测试。 这个阶段要做好源代码备份,除非发现重大问题,不要修改程序源代码,尤其在离终场 10 分钟以内时,因为此时 头脑紧张,极易改错。 这样下来,330 分不是大问题,在河北省就进入省队了。但是,很多平时成绩不错的大牛考试时粗心大意,丢分现 象十分严重。 这次考试的题目很水,更考察选手的细心认真程度。真正的高手不仅会做难题, 水题也能保证不出错。 只有不出错,才能省队,因为第四题竞赛时几乎没人想出正确解法;只有保证错误不足半道,才能一等奖,因为河 北省一等奖分数线是 280 分。实际上,对于如此普及组难度的水题,即使实力一般,也可能拿到不错的成绩。 希望 NOIP2008 成功的同学总结经验,再接再厉,创造更好的成绩;NOIP 失利的同学不要气馁,总结教训,认真 细致,下次再争取。 . [原创]NOIP2009 提高组解题报告{继续供大牛 BS} 2009-11-21 10:46 P.M. 第一题: 水题,按照题目要求去枚举。 注意,同一个字母加密后的字母是一样的,加密后一样的字母原字母也是一样的。 var a,b:array['A'..'Z']of char; c:char; s1,s2,s3:string; i:longint; procedure main;

begin

exit;

readln(s1); end else readln(s2); readln(s3); begin end; fillchar(a,sizeof(a),' '); a[s1[i]]:=s2[i]; begin assign(input,'spy.in'); fillchar(b,sizeof(b),' '); b[s2[i]]:=s1[i]; reset(input); for i:=1 to length(s1) do end; if ((a[s1[i]]<>' for c:='A' to 'Z' do assign(output,'spy.out'); ')and(a[s1[i]]<>s2[i])) if a[c]=' ' then rewrite(output); or((b[s2[i]]<>' begin main; writeln('Failed'); close(input); ')and(b[s2[i]]<>s1[i])) then exit; close(output); begin writeln('Failed'); end; end. 第二题: 数论题,分解质因数。通过 a0,a1,b0,b1 确定 X 中每项质因子的最大幂数和最小幂数。然后再把每个质因子的幂数 范围乘起来。 PS:参考程序过 10 个点的总耗时为 0.23 秒,评测环境为 2.10GHz 2.00GB const if n mod i=0 then function get(var a : maxn=100; begin arr;n:longint):longint; maxm=46341; inc(t); var type n:=n div i; i : longint; data = record end begin n,c : longint; else for i:=1 to a[0].n do end; begin if a[i].n=n then exit(a[i].c); ans = record if t>0 then exit(0); n,min,max : longint; begin end; { get } end; inc(a[0].n); function min_(a,b : longint):longint; arr = array[0..maxn]of data; with a[a[0].n] do begin var begin if a<b then exit(a) else exit(b); a0,a1,b0,b1 : longint; n:=i; end; { min } fa0,fa1,fb0,fb1 : arr; c:=t; function max_(a,b : longint):longint; xmin,xmax,xn : end; begin array[0..maxn]of longint; t:=0; if a>b then exit(a) else exit(b); bool : end; end; array[1..maxm]of boolean; i:=next[i]; procedure cmin(n ,c : longint); next : end; var array[1..maxm]of longint; end; i : longint; procedure change( n : longint;var if t>0 then begin a:arr); begin for i:=1 to xn[0] do var inc(a[0].n); if xn[i]=n then i,k,t : longint; a[a[0].n].n:=i; begin begin a[a[0].n].c:=t; xmin[i]:=max_(xmin[i],c); fillchar(a,sizeof(a),0); end; exit; t:=0; if n>1 then end; i:=2; begin inc(xn[0]); while n>1 do inc(a[0].n); xn[xn[0]]:=n; begin a[a[0].n].n:=n; xmin[xn[0]]:=c; if (i>trunc(sqrt(n)))and(t=0) then a[a[0].n].c:=1; xmax[xn[0]]:=maxlongint; break; end; end; { cmin } if i=-1 then break; end; { change } procedure cmax(n ,c : longint);

for i:=1 to length(s3) do write(a[s3[i]]); writeln;

var

end;

i : longint; end; begin procedure main; for i:=1 to xn[0] do var if xn[i]=n then i,j,k,t: longint; begin begin xmax[i]:=min_(xmax[i],c); readln(a0,a1,b0,b1); exit; change(a0,fa0); end; change(a1,fa1); inc(xn[0]); change(b0,fb0); xn[xn[0]]:=n; change(b1,fb1); xmax[xn[0]]:=c; fillchar(xn,sizeof(xn),0); xmin[xn[0]]:=0; fillchar(xmax,sizeof(xmax),0); end; { cmin } fillchar(xmin,sizeof(xmin),0); procedure init; for i:=1 to fa1[0].n do var cmin(fa1[i].n,fa1[i].c); i,j:longint; for i:=1 to fb1[0].n do begin cmax(fb1[i].n,fb1[i].c); fillchar(bool,sizeof(bool),true); for i:=1 to fb1[0].n do for i:=2 to trunc(sqrt(maxm)) begin do k:=get(fb0,fb1[i].n); if bool[i] then if k<fb1[i].c then for j:=2 to maxm div i do cmin(fb1[i].n,fb1[i].c); bool[i*j]:=false; end; j:=-1; for i:=1 to fa0[0].n do fillchar(next,sizeof(next),255); begin for i:=maxm downto 1 do k:=get(fa1,fa0[i].n); begin if k<fa0[i].c then next[i]:=j; cmax(fa0[i].n,k); if bool[i] then j:=i; end; 第三题: 图论题,两次 SPFA,用 a[i]表示从起点开始到 i 结点能经过的最小值,用 b[i]表示从终点延反向边到达 i 结点能经 过的最大值。Ans=max(b[i]-a[i])。 const seg[ls].f:=f1; for i:=1 to m do maxn=100010; seg[ls].next:=a[s]; begin maxm=1000010; a[s]:=ls; readln(j,k,l); type inc(ls); if l=1 then data=record seg[ls].t:=s; insert_e(j,k,1,2) t,f,next:longint; seg[ls].f:=f2; else insert_e(j,k,3,3); end; seg[ls].next:=a[t]; end; var a[t]:=ls; end; n,m,ls:longint; end; function max(a,b:longint):longint; a,c,d,stack,v:array[0..maxn]of procedure init; begin longint; var if a>b then exit(a) else exit(b); f:array[1..maxn]of boolean; i,j,k,l:longint; end; seg:array[1..maxm]of data; begin function min(a,b:longint):longint; procedure insert_e(s,t,f1,f2:longint); readln(n,m); begin begin fillchar(a,sizeof(a),255); if a<b then exit(a) else exit(b); inc(ls); ls:=0; end; seg[ls].t:=t; for i:=1 to n do read(v[i]); procedure spfa1;

for i:=1 to xn[0] do begin if xmin[i]>xmax[i] then begin writeln(0);exit;end; if xmax[i]=maxlongint then begin writeln(0);exit;end; end; t:=1 ; for i:=1 to xn[0] do t:=t*(xmax[i]-xmin[i]+1); writeln(t); end; { main } var tt:longint; begin assign(input,'son.in'); reset(input); assign(output,'son.out'); rewrite(output); readln(tt); init; for tt:=tt downto 1 do begin main end; close(input); close(output); end.

var i,k,open,closed:longint; begin fillchar(c,sizeof(c),127); fillchar(f,sizeof(f),0); f[1]:=true; open:=0; closed:=1; stack[1]:=1; c[1]:=v[1]; while open<closed do begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 1=1)and(min(c[k],v[seg[i].t])<c[seg[i ].t]) then begin c[seg[i].t]:=min(c[k],v[seg[i].t]); if not f[seg[i].t] then begin f[seg[i].t]:=true; inc(closed);

end; end; i:=seg[i].next; end; end; end; procedure spfa2; var i,k,open,closed:longint; begin fillchar(d,sizeof(d),0); fillchar(f,sizeof(f),0); f[n]:=true; open:=0; closed:=1; stack[1]:=n; d[n]:=v[n]; while open<closed do begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 2=2)and(max(d[k],v[seg[i].t])>d[seg[ i].t]) then begin d[seg[i].t]:=max(d[k],v[seg[i].t]); if not f[seg[i].t] then inc(closed); f[seg[i].t]:=true;

begin

stack[closed mod maxn]:=seg[i].t; 第四题: 搜索题,有时候这个世界需要些暴力。DFS 搜索,每次选取填入的数的方案数进行枚举。PS:据说从右下角直接枚 举到左上角,比加剪枝也能拿 95 分。 var if a<b then exit(a) else exit(b); 3*3+(j-1)div 3+1+18; n,ans,l,time:longint; end; a:array[1..81,1..3]of longint; procedure init; v[k]:=10-max(abs(i-5),abs(j-5)); c:array[1..27,0..9]of boolean; var end; v:array[1..81]of longint; i,j,k:longint; fillchar(c,sizeof(c),1); d,d2,d3:array[1..81]of longint; begin for i:=1 to 81 do o:array[1..81]of longint; for i:=1 to 9 do begin function max(a,b:longint):longint; for j:=1 to 9 do read(d[i]); begin begin c[a[i,1],d[i]]:=false; if a>b then exit(a) else exit(b); k:=(i-1)*9+j; c[a[i,2],d[i]]:=false; end; a[k,1]:=i; c[a[i,3],d[i]]:=false; function min(a,b:longint):longint; a[k,2]:=j+9; end; begin a[k,3]:=(i-1)div end;

stack[closed mod maxn]:=seg[i].t; end; end; i:=seg[i].next; end; end; end; procedure main; var i,ans:longint; begin spfa1; spfa2; ans:=0; for i:=1 to n do ans:=max(ans,d[i]-c[i]); writeln(ans); end; begin assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output); init; main; close(input); close(output); end.

procedure check; var i,t:longint; begin t:=0; for i:=1 to 81 do inc(t,d[i]*v[i]); if t>ans then ans:=t; end; procedure dfs(dep:longint); var i,k:longint; begin if dep>l then begin check;exit;end; { if dep<1 then begin check;exit;end;} inc(time); if time>10000000 then begin writeln(ans);close(input); close(output);halt;end; k:=o[dep]; for i:=1 to 9 do if c[a[k,1],i] and c[a[k,2],i] and c[a[k,3],i] then begin c[a[k,1],i]:=false; c[a[k,2],i]:=false; c[a[k,3],i]:=false; d[k]:=i; dfs(dep+1); d[k]:=0; c[a[k,1],i]:=true; c[a[k,2],i]:=true; c[a[k,3],i]:=true; end; end;

procedure main; var i,j,k,t:longint; begin d2:=d; for i:=1 to 81 do d3[i]:=9; for i:=1 to 81 do if d2[i]>0 then begin for j:=1 to 81 do if (a[i,1]=a[j,1])or(a[i,2]=a[j,2])or(a[i,3] =a[j,3]) then dec(d3[j]); end; l:=0; while true do begin k:=maxlongint; for i:=1 to 81 do if (d2[i]=0)and(d3[i]<k) then begin k:=d3[i]*11+v[i]; j:=i; end; if k=maxlongint break; inc(l); o[l]:=j; d2[j]:=10; for i:=1 to 81 do if (a[i,1]=a[j,1])or(a[i,2]=a[j,2])or(a[i,3] =a[j,3]) then

dec(d3[j]); end; time:=0; ans:=-1; dfs(1); writeln(ans); end; begin assign(input,'sudoku.in'); reset(input); assign(output,'sudoku.out'); rewrite(output); init; main; close(input); close(output); end. 类别: 资料原创] | | 添加到搜藏 oi | 分享到 i 贴吧 | 浏览(1498) | 评论 (20) 上一篇:Crafting Winning Solutions [Pa... 下一篇:Derivatives 相关文章: ? 汇总]搜索题目推荐及解题报 告(转... ? POJ PKU 3705 解题报告(自己 没有... ? 大牛 ZZX《奇怪问题》解题报 告

then


相关文章:
更多相关标签: