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

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;
1

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;
2

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;
3

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
4

记两个加数为 x 和 y,和数为 z。 算法:搜索+剪枝 (我的算法并不能通过所有的测试,但还没有找到更加行之有效的算法) 分析:此题最容易想到的方法就是搜索,由于 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]);
5

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; 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
6

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;
7

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.

8


相关文章:
NOIP2004提高组解题报告
NOIP2004提高组解题报告_其它课程_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2004提高组解题报告_其它课程_高中教育_教育专区。Noip2004 解题报告 ...
NOIP2005提高组解题报告
NOIP2005提高组解题报告_初一理化生_理化生_初中教育_教育专区。NOIP2005提高组NOIP2005 信息学奥林匹克分区联赛 解题报告 [麓山 NOI 战队] 第一题:谁拿了最多的...
NOIP2015提高组解题报告
NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...
NOIP2004普及组复赛解题报告
NOIP2004普及组复赛解题报告_计算机软件及应用_IT/计算机_专业资料。NOIP2004普及...NOIP1995普及组复赛数据 NOIP1995普及组复赛试题 NOIP1995提高组初赛试题 NOIP1995...
NOIP2004提高组复赛试题
NOIP2004 提高组复赛试题 第十届全国青少年信息学奥林匹克联赛复赛试题 (提高组 ...NOIP2004普及组复赛解题... 8页 免费 NOIP2004普及组初赛试题... 8页 免费...
NOIP2004 提高组试题
NOIP2004 提高组试题_其它考试_资格考试/认证_教育专区。历届NOIP试题第...NOIP2003 提高组试题 7页 1下载券 Noip 2013 解题报告与参... 18页 免费 ...
NOIP历年复赛提高组试题(2004-2013)
NOIP历年复赛提高组试题(2004-2013)_学科竞赛_高中教育...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告...Noip 2013 提高组 解题报... 21页 免费 Noip ...
NOIP2004提高组初赛试题及答案
NOIP2004提高组初赛试题及答案_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2004提高组初赛试题及答案_学科竞赛_初中教育_教育专区。NOIP2004...
Noip 2003 提高组 解题报告1
Noip 2003 提高组 解题报告1_IT/计算机_专业资料。03Noip 2003 提高组 解题报告题一 分析: 这一题有很多种方法,数据也较弱。我考虑到其中的层次关系,用类似于...
更多相关标签:
noip2014提高解题报告 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2014解题报告 | noip2015复赛解题报告 | noip2016复赛解题报告 | noip2013解题报告 |