当前位置:首页 >> IT/计算机 >>

Noip2004解题报告


Noip2004 解题报告 一、津津的储蓄计划 算法:模拟法 程序: program save1; var a:array[1..12] of longint; have,save,x,temp,i:longint; f:text; begin assign(f,'save.in');reset(f); for i:=1 to 12 do readln(f,a[i]); close(f); for i:=1 to 12 do begin temp:=have+300-a[i]; if temp<0 then begin x:=i; break; end else begin save:=save+temp div 100*100; have:=temp mod 100; end; end; assign(f,'save.out');rewrite(f); if x<>0 then writeln(f,-x) else writeln(f,trunc(save*1.2)+have); close(f); end. 二、合并果子 算法:贪心+堆 分析:显然,每次从现有的数中选取两个最小数的进行 合并(将这两个数删除) ,将合并后的数记录下来,重 复 n-1 次,就能保证值最小。 由于需要不断选取最小的数,数据结构考虑采用堆。首 先建堆,每次操作,先选取最小元素 O(1),并从堆中删 除最小元素 O(logn),重复两次,再将合并后的数插入 堆中 O(logn)。 我的程序建堆采取快速排序,时间复杂度 O(nlogn),也 可以直接采取堆排序,时间复杂度同样 O(nlogn)。这样 总的时间复杂度 O(nlogn)。 程序: program fruit; uses dos; var a:array[1..20000] of longint; n,n1,ans,min1,min2:longint; f:text;

t1,t2,t3,t4,t5,t6,t7,t8:word; t:double; procedure init; var i:longint; begin gettime(t1,t2,t3,t4); assign(f,'fruit.in');reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; procedure qsort(l,r:longint); var i,j,x,temp:longint; begin i:=l;j:=r;x:=a[random(r-l+1)+l]; repeat while a[i]<x do i:=i+1; while a[j]>x do j:=j-1; if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; i:=i+1;j:=j-1; end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; function deletemin:longint; var i,j,temp:longint; begin deletemin:=a[1]; a[1]:=a[n1]; n1:=n1-1; i:=1; while i<=n1 div 2 do begin if (a[2*i]<a[2*i+1]) or (2*i=n1) then j:=2*i else j:=2*i+1; if a[i]>a[j] then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; i:=j; end else exit; end; end; procedure insert(x:longint); var i,temp:longint;
1

begin n1:=n1+1; a[n1]:=x; i:=n1; while (i>1) and (a[i]<a[i div 2]) do begin temp:=a[i];a[i]:=a[i div 2];a[i div 2]:=temp; i:=i div 2; end; end; procedure main; var i,j,k1,k2:longint; begin n1:=n; for i:=1 to n-1 do begin min1:=deletemin; min2:=deletemin; insert(min1+min2); ans:=ans+min1+min2; end; assign(f,'fruit.out');rewrite(f); writeln(f,ans); close(f); gettime(t5,t6,t7,t8); t:=((t5-t1)*60+(t6-t2))*60+(t7-t3)+(t8-t4)/100; writeln(t:0:3); end; begin init; qsort(1,n); main; end. 三、合唱队形 算法:最长子序列+枚举 分析:不妨,枚举每个人为中间身高最高的人,要使出 列的人数最小,即这个人的左边和右边都有尽可能多的 人。此人左右两边分别满足严格上升和下降的关系,且 人数最多,是典型的动态规划题目——最长子序列。 首先,求出最长子序列,左边的最大值记做 up[i],右边 的最大值记做 down[i]。 然 后 , 枚 举 每 个 人 i , 有 ki=up[i]+down[i]-1 , minans=n-maxki。 求最长子序列可以采用 O(n^2)的算法,更好的算法是 O(nlogn)。由于题中 n 的最大值为 100,我的程序采用 O(n^2)的算法。 枚举每个人的复杂度 O(n),计算 ki 的复杂度 O(1)。 总的时间复杂度 O(n^2)。 程序:

program chorus; var t:array[0..101] of longint; up,down:array[0..101] of longint; n,k:longint; f:text; procedure init; var i:longint; begin assign(f,'chorus6.in');reset(f); readln(f,n); for i:=1 to n do read(f,t[i]); close(f); end; procedure main; var i,j,max:longint; begin t[0]:=0;t[n+1]:=0; for i:=1 to n do begin max:=1; for j:=0 to i-1 do if (t[j]<t[i]) and (max<up[j]+1) then max:=up[j]+1; up[i]:=max; end; for i:=n downto 1 do begin max:=1; for j:=n+1 downto i+1 do if (t[j]<t[i]) and (max<down[j]+1) then max:=down[j]+1; down[i]:=max; end; k:=0; for i:=1 to n do if k<up[i]+down[i]-1 then k:=up[i]+down[i]-1; assign(f,'chorus.out');rewrite(f); writeln(f,n-k); close(f); end; begin init; main; end. 四、食虫算 样例输入: 5 ABCED BDACE EBBAA 记两个加数为 x 和 y,和数为 z。
2

算法:搜索+剪枝 (我的算法并不能通过所有的测试,但还没有找到更加 行之有效的算法) 分析:此题最容易想到的方法就是搜索,由于 n 的最大 值是 26,对于搜索,这显然是个庞大的数目,搜索效率 的高低即是关键。 方法 1:先枚举 n 个字母的值,再检查是否满足算式。 枚举的复杂度 O(n!),检查的复杂度 O(n),总的复杂度 O(n*n!)。n 最大只能等于 10,只能得到 30%的分数。 方法 2:算式从低位向高位搜索,如果该字母未遇到才 进行搜索,z 的值直接由 x+y 产生,不进行搜索,并且 不断检查算式是否成立。这个算法的复杂度,很大程度 上取决于算式本身。 我的程序能通过 1、2、3、4、5、6、9、10。8 需要 4.230 秒,9 不能出解。 方法 3:显然,两个数相加,进位或者为 0,或者为 1。 可以枚举每一位是否进位,最高位不进位 O(2^(n-1)), 通过解方程组求得每个字母的值 O(n^2), 并判断字母的 值是否重复 O(n)。总的时间复杂度 O(2^(n-1)*(n*n+n))。 测 试 数 据 中 n 的 最 大 值 为 21 , 此 时 复 杂 度 为 O(2^20*(21*21+21))=O(484442112)。这个程序我没有实 现,但肯定能出解,会略微超时。 程序: program alpha; uses dos; var x,y,z:array[1..26] of integer; num:array[1..26] of integer; use:array[0..26] of boolean; n:integer; f:text; t1,t2,t3,t4,t5,t6,t7,t8:word; t:double; procedure init; var i:integer; ch:char; begin gettime(t1,t2,t3,t4); assign(f,'alpha7.in');reset(f); readln(f,n); for i:=n downto 1 do begin read(f,ch);x[i]:=ord(ch)-ord('A')+1;end; readln(f); for i:=n downto 1 do begin read(f,ch);y[i]:=ord(ch)-ord('A')+1;end; readln(f); for i:=n downto 1 do begin read(f,ch);z[i]:=ord(ch)-ord('A')+1;end; readln(f); close(f);

fillchar(use,sizeof(use),true); for i:=1 to n do num[i]:=-1; end; procedure output; var i:integer; begin assign(f,'alpha.out');rewrite(f); for i:=1 to n-1 do write(f,num[i],' '); writeln(f,num[n]); close(f); gettime(t5,t6,t7,t8); t:=((t5-t1)*60+(t6-t2))*60+(t7-t3)+(t8-t4)/100; writeln(t:0:3); halt; end; procedure try(step,s:integer); var i,j:integer; begin if step=n+1 then begin if s=0 then output; exit; end; if (num[x[step]]=-1) then for i:=0 to n-1 do if use[i] then begin use[i]:=false; num[x[step]]:=i; if (num[y[step]]=-1) then for j:=0 to n-1 do if use[j] then begin use[j]:=false; num[y[step]]:=j; if num[z[step]]=-1 then if use[(i+j+s) mod n] then begin use[(i+j+s) mod n]:=false; num[z[step]]:=(i+j+s) mod n; try(step+1,(i+j+s) div n); use[(i+j+s) mod n]:=true; num[z[step]]:=-1; end else else if num[z[step]]=(i+j+s) mod n then try(step+1,(i+j+s) div n); use[j]:=true;
3

num[y[step]]:=-1; end; if (num[y[step]]<>-1) then begin j:=num[y[step]]; if num[z[step]]=-1 then if use[(i+j+s) mod n] then begin use[(i+j+s) mod n]:=false; num[z[step]]:=(i+j+s) mod n; try(step+1,(i+j+s) div n); use[(i+j+s) mod n]:=true; num[z[step]]:=-1; end else else if num[z[step]]=(i+j+s) mod n then try(step+1,(i+j+s) div n); end; use[i]:=true; num[x[step]]:=-1; end; if (num[x[step]]<>-1) then begin i:=num[x[step]]; if (num[y[step]]=-1) then for j:=0 to n-1 do if use[j] then begin use[j]:=false; num[y[step]]:=j; if num[z[step]]=-1 then if use[(i+j+s) mod n] then begin use[(i+j+s) mod n]:=false; num[z[step]]:=(i+j+s) mod n; try(step+1,(i+j+s) div n); use[(i+j+s) mod n]:=true; num[z[step]]:=-1; end else else if num[z[step]]=(i+j+s) mod n then try(step+1,(i+j+s) div n); use[j]:=true; num[y[step]]:=-1; end;

if (num[y[step]]<>-1) then begin j:=num[y[step]]; if num[z[step]]=-1 then if use[(i+j+s) mod n] then begin use[(i+j+s) mod n]:=false; num[z[step]]:=(i+j+s) mod n; try(step+1,(i+j+s) div n); use[(i+j+s) mod n]:=true; num[z[step]]:=-1; end else else if num[z[step]]=(i+j+s) mod n then try(step+1,(i+j+s) div n); end; end; end; begin init; try(1,0); end. Noip2004 普及组解题报告 一、不高兴的津津 算法:模拟法 程序: program unhappy; var i,a,b:integer; f,f1:text; begin assign(f,'unhappy.in');reset(f); assign(f1,'unhappy.out');rewrite(f1); for i:=1 to 7 do begin readln(f,a,b); if a+b>8 then begin writeln(f1,i); close(f1); halt; end; end; close(f); writeln(f1,0);close(f1); end. 二、花生采摘: 算法:模拟法 分析:根据题目,采摘花生必须严格按照由大到小的顺 序进行,只要先按照花生多少由大到小排序,再依次检 验时间是否满足如下条件:
4

1.时间足够达到、采摘当前花生并返回。 2.时间不够达到、采摘下一个花生并返回。 输出当前采摘花生数量。 程序: program peanuts; var a:array[0..400] of record p,x,y:integer; end; m,n,k:integer; ans:longint; f:text; procedure init; var i,j:integer; begin assign(f,'peanuts.in');reset(f); readln(f,m,n,k); for i:=1 to m do begin for j:=1 to n do begin a[(i-1)*n+j].x:=i; a[(i-1)*n+j].y:=j; read(f,a[(i-1)*n+j].p); end; readln(f); end; close(f); end; procedure sort; var i,j,temp:integer; begin for i:=1 to m*n-1 do for j:=i+1 to m*n do if a[i].p<a[j].p then begin temp:=a[i].p;a[i].p:=a[j].p;a[j].p:=temp; temp:=a[i].x;a[i].x:=a[j].x;a[j].x:=temp; temp:=a[i].y;a[i].y:=a[j].y;a[j].y:=temp; end; end; procedure output; begin assign(f,'peanuts.out');rewrite(f); writeln(f,ans); close(f); halt; end; procedure main; var i,time:integer; begin

a[0].x:=0;a[0].y:=a[1].y; time:=0;ans:=0; for i:=1 to m*n do begin if time+abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1+a[i].x<=k then begin time:=time+abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1; ans:=ans+a[i].p; end else output; end; output; end; begin init; sort; main; end. 三、FBI 树 算法:递推+树的后序遍历 分析:根据题目,只需构造出 FBI 树并进行后序遍历。 构造 FBI 树时,由子节点的状态,生成父节点的状态, 是典型的递推法。树的后序遍历是经典算法,简单的递 归即可实现,不再赘述。 程序: program fbi; var a:array[1..1024] of char; b:array[0..1024,1..1024] of char; n,num:integer; f:text; procedure init; var i:integer; begin assign(f,'fbi.in');reset(f); readln(f,n); num:=1; for i:=1 to n do num:=num*2; for i:=1 to num do read(f,a[i]); close(f); end; procedure main; var i,j,k:integer; begin for i:=1 to num do if a[i]='0' then b[n,i]:='B' else b[n,i]:='I'; i:=num;k:=n; while i>1 do
5

begin i:=i div 2;dec(k); for j:=1 to i do if b[k+1,2*j-1]=b[k+1,2*j] then b[k,j]:=b[k+1,2*j] else b[k,j]:='F'; end; end; procedure output(line,head:integer); begin if line<>n then begin output(line+1,2*head-1); output(line+1,2*head); end; write(f,b[line,head]); end; begin init; main; assign(f,'fbi.out');rewrite(f); output(0,1); writeln(f); close(f); end. 四、火星人 算法:模拟法 分析:看到题目,我的第一反应是生成 N 的全排列,这 是经典的算法。但是 N 很大,而 M 很小,生成全排列 是极其不明智的做法。 N 最大为 10000,M 至多为 100,因此只要不断找到当 前排列的下一个排列,重复 M 次即可。 例:3 的全排列 123 132 213 231 312 321 通过观察,可以总结出,找当前排列的下一个排列的方 法,具体参见程序。 程序: program martian; var a:array[1..10000] of integer; n,m:integer; f:text; procedure init; var i:integer;

begin assign(f,'martian10.in');reset(f); readln(f,n); readln(f,m); for i:=1 to n do read(f,a[i]); close(f); end; procedure main; var m1,i,j,p,q,temp:integer; flag:boolean; begin for m1:=1 to m do begin flag:=false; for i:=n-1 downto 1 do begin for j:=n downto i+1 do if a[i]<a[j] then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; p:=i; flag:=true;break; end; if flag then break; end; for i:=p+1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; end; flag:=false; end; assign(f,'martian.out');rewrite(f); for i:=1 to n-1 do write(f,a[i],' '); writeln(f,a[n]); close(f); end; begin init; main; end.

6


相关文章:
NOIP2004提高组解题报告.doc
NOIP2004提高组解题报告 - Noip2004 解题报告 一、津津的储蓄计
NOIP普及组解题报告.doc
NOIP普及组解题报告 - NOIP2006 复赛普及组解题报告 【第一题解题思想】 :这道题属于容易题,但是题目难度大于 NOIP2005 和 2004 普及组第一题, 和去年第二题...
noip2004 提高组复赛试题及参考程序(pascal).pdf
noip2004 提高组复赛试题及参考程序(pascal) - 第十届信息学奥林匹克联赛复赛试题 (NOIP2004) 一、津津的储蓄计划(save.pas/c/cpp) 【问题描述】 津津的零....
NOIP2004普及组.pdf
NOIP2004普及组 - 第十届全国青少年信息学奥林匹克联赛初赛试题 ( 普及
2007noip解题报告.pdf
2007noip解题报告 - 第一题: 开个足够大的数组,把所有数读入,Nlog
noip2010提高组解题报告.doc
NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3...NOIP2010普及组个人解题... 9页 免费 NOIP2004提高组解题报告 8页 免费 ...
NOIP2000解题报告.ppt
NOIP2000解题报告 NOIP2000解题报告 by Leo 题1.进制转换
noip2005普及组解题报告.doc
noip2005普及组解题报告 - noip2005 普及组解题报告 陶陶摘苹果
NOIP2015提高组解题报告.doc
NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...
2011noip提高组解题报告.pdf
2011noip提高组解题报告 - 第一题很简单,用循环队列可做出。我当初为省时
NOIP2004初赛提高组P试题与答案.doc
NOIP2004初赛提高组P试题与答案 - 第十届全国青少年信息学奥林匹克联赛初
NOIP2003解题报告.pdf
NOIP2003解题报告 - 清北学堂金牌特训班专享资料 北京清北学堂教育科技中
noip2016普及组解题报告_图文.pdf
noip2016普及组解题报告_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档noip2016普及组解题报告_学科竞赛_初中教育_教育专区。 ...
NOIP2012普及组复赛解题报告c++版本.doc
NOIP2012普及组复赛解题报告c++版本_工学_高等教育_教育专区。NOIP2012普及组解题报告c++版本,信息学奥赛2012普及组复赛 信息学奥赛 NOIP2012普及组解题报告(c++版本)...
NOIP2011提高组解题报告day1.doc
NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地毯...NOIP2010提高组解题报告 6页 1下载券 NOIP2004提高组解题报告 8页 免费 NOIP...
NOIP2004【第十届初赛C语言提高组试题与答案】 (1).doc
NOIP2004【第十届初赛C语言提高组试题与答案】 (1) - 第十届全国青少
NOIP2004普及组初赛试题答案.doc
NOIP2004普及组初赛试题答案_IT/计算机_专业资料。这是noip历年题目,有助于你的...NOIP2004提高组解题报告 8页 免费 NOIP2004提高组初赛试题... 11页 免费 NOIP...
NOIP2011复赛题解.doc
NOIP2011复赛题解 - noip2011 普及组解题报告 NOIP2011 普及组解题报告 ahbbzeq 2011.11.25 转载请注明来源 一、数字反转 没得满分只能说明一个问题...
NOIP2004提高组初赛试题及答案.doc
NOIP2004提高组初赛试题及答案_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2004提高组初赛试题及答案_学科竞赛_初中教育_教育专区。NOIP2004...
noip2013解题报告.pdf
noip2013解题报告_IT/计算机_专业资料。附带详细解析和代码的解题报告 NOIP2013解题报告长郡中学 黄鑫 1.circle 题目描述: n 个小伙伴(编号从 0 到 n-1)...
更多相关标签: