tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> IT/计算机 >>

NOIP2008提高组前三题解题报告


NOIP2008 提高组前三题解题报告
[日期:2008-11-18] 来源: 作者:张恩权 [字体:大 中 小]

NOIP2008 提高组前三题解题报告
1.笨小猴 基本的字符串处理, 细心一点应该没问题的, 不过判断素数时似乎需要考虑下 0 和 1 的情况。 参考程序: program word; const inp='word.in'; oup='word.out';

var i,j,k,min,max:longint; s:string; ch:char; f:array['a'..'z'] of integer;//记录每个字符出现的次数 procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end; function judge(k:longint):boolean;//判断素数,需考虑 0 和 1 的情况 var i:longint; begin if (k=0) or (k=1) then exit(false);

for i:=2 to trunc(sqrt(k)) do if k mod i = 0 then exit(false); exit(true); end;

begin flink; readln(s); fillchar(f,sizeof(f),0); for i:= 1 to length(s) do //统计每个字符出现的次数 inc(f[s[i]]); min:=1000; max:=0; for ch:= 'a' to 'z' do//统计最大和最小 begin if ( f[ch]<>0 ) and (f[ch]>max) then max:=f[ch]; if ( f[ch]<>0 ) and (f[ch]<min) then min:=f[ch]; end; k:=max-min; if judge(k) then//输出 begin writeln('Lucky Word'); write(k); end else begin writeln('No Answer'); write(0); end;

fclose; end.

2.火柴棒等式 预处理下,然后枚举、剪枝,范围稍微开大点,弄到 2000 似乎足够了,剪枝后不会超时的。 首先预处理下每个数(0~2000)需要多少个火柴棒,然后枚举 A 和 B,再判断。 参考程序: program matches; const inp='matches.in'; oup='matches.out'; num:array['0'..'9'] of integer=(6,2,5,5,4,5,6,3,7,6);//0~9 需要的火柴棒数 maxn=1000; var f:array[0..maxn*2] of longint; i,j,k,n,ans:longint; s:string; procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end; procedure init;//预处理 0~2000 每个数需要的火柴棒数 var i,j,k:longint; s:string; begin for i:= 0 to maxn*2 do begin str(i,s);

f[i]:=0; for j:= 1 to length(s) do inc(f[i],num[s[j]]); end; end;

begin flink; readln(n); init; ans:=0; n:=n-4;//总火柴棒数减去'+'和'='所需的火柴棒数 for i:= 0 to maxn do//枚举 A begin if f[i]>=n then continue;//剪枝 for j:= 0 to maxn do//枚举 B begin if f[i]+f[j]>=n then continue;//剪枝 k:=i+j; if f[i]+f[j]+f[k]=n then inc(ans);//符合条件,总数加一 end; end; write(ans); fclose; end.

3.传纸条 从 A 传给 B,再从 B 传给 A,中间路径不相交与某个人……。换种思路,它完全等价于,从 A 点传出 2 张纸条到 B,中间不能经过同一人。这么看来似乎就是 vijos 三取方格数的简化 版了。 解题思想就是双进程的动态规划。阶段是按传递次数划分的。 F(d,x1,y1,x2,y2)表示第 d 次传递到坐标为(x1,y1),(x2,y2)两个人手中是得到的 最大好心度。 那么可以列出方程:

F(d,x1,y1,x2,y2)=max{ f (d-1,x1',y1',x2',y2' )+a[x1,y1]+a[x2,y2] 为把纸条(x1,y1)的人,(x2' , y2')为把纸条转给(x2,y2)的人} (数学不太好,方程列的不专业,见谅^_^)

|

(x1',y1')

这么看来时间复杂度是 O(maxd*n*m*n*m),其中 maxd=n+m-2。相当于 50^5=312500000,超 时是没得说的了。 其实我们可以把状态再压缩下,先来看下其中的规律: 起点 第 1 次传递可到达 第 2 次传递可到达 …… 很快就可以发展其中的规律 第 d 次传递可到达的坐标(xi,yi)和 d 之间存在 d+2=xi+yi 那么我们就可以把上面的状态转移方程转化成 f(d,x1,x2)=max { f(d-1,x1' ,x2' ) +a[x1, (d+2-x1) ] + a[x2, (d+2-x2)] x2' 合法 } 参考程序: program message; const inp='message.in'; oup='message.out'; | x1' , (1,1) (1,2)(2,1) (1,3)(2,2)(3,1)

var a:array[1..50,1..50] of longint; f:array[0..200,1..100,1..100] of longint; tmp,i,j,k,n,m,d,x1,x2,y1,y2:longint; procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin

close(input); close(output); end; function max(a,b:longint):longint; begin if a>b then exit(a); exit(b); end;

begin flink; readln(n,m); for i:= 1 to n do begin for j:= 1 to m do read(a[i,j]); readln; end; fillchar(f,sizeof(f),0); f[0,1,1]:=a[1,1]; f[1,1,2]:=a[2,1]+a[1,2]; f[1,2,1]:=a[1,2]+a[2,1]; //边界,因为中间需要判断点不重合,所以把必须重合的状态单独考虑 for d:= 2 to (n+m-3) do for x1:= 1 to n do begin y1:=(d+2)-x1; if (y1<=0) or (y1>m) then continue; // 排除不合法的 x1 for x2:= 1 to n do begin if x1=x2 then continue;//排除不合法的 x1,x2 y2:=(d+2) - x2; if (y2<=0) or (y2>m) then continue; // 排除不合法的 x2 tmp:=f[d-1,x1,x2]; //各自从上方取,即从(x1,y1-1)传到(x1,y1),(x2,y2-1)传到(x2,y2)

if (x1-1>0) and (x2-1>0) then tmp:=max(tmp,f[d-1,x1-1,x2-1]); //从(x1-1,y1) 传到(x1,y1),(x2-1,y2)传到(x2,y2)

if (x1-1>0) and (x1-1<>x2) then tmp:=max(tmp,f[d-1,x1-1,x2]); //从(x1-1,y1) 传到(x1,y1),(x2,y2-1)传到(x2,y2)

if (x2-1>0) and (x1<>x2-1) then tmp:=max(tmp,f[d-1,x1,x2-1]); //从(x1,y1-1) 传到(x1,y1),(x2-1,y2)传到(x2,y2) f[d,x1,x2]:=tmp+a[x1,y1]+a[x2,y2]; end; end; write(f[n+m-3,n,n-1]); // 终点的只可能从两个点来,所以终点状态前移一个阶段。 fclose; end.

4.双栈排序 难……,写不出满分程序,所以还是不写了……

NOIP2008 提高组复赛 解题思路
1、字符串中统计字母出现次数 最大减最小的 然后判断质数 字符串长度<=100 2、给出 n<=24 个火柴棍, 求最多能摆出多少 a+b=c 形式的等式。 数字的摆法和计算器相同, a,b,c>=0

3、双进程方格取数:m*n 的棋盘,m,n<=50,不需使用高精度 4、给出 1..n 的排列,两个栈 S1、S2,入栈出栈共 4 个操作: (n<=1000) A:输入队列头入 S1 B:弹出 S1 栈顶元素,进入输出队列 C:输入队列头入 S2 D:弹出 S2 栈顶元素,进入输出队列 要求将 1..n 的排列排序,采用字典序最小的操作方法

个人感觉是,单就难度来看,奥赛历史最简单,由于类似 2,3 题的模型大多数能拿一等的 同学们都见过。

我的想法: 1、水题,最多 40 分钟搞定 2、 如果是考试的话, 10000*10000 的枚举, 差不多写程序+跑+打表=10+3+2min 就够了吧 (不 过我用的是骗

分手段,一个一个手算。然后 IF-THEN,IF-THEN,最后 15 分钟搞定) 。 3、经典题目,斜向划分阶段。35 分钟搞定(前三个题目 1 小时思路+编程+检查够了)

4、本届唯一挑战性题目。考虑到要求字典序最小,那么按照 ABCD 的顺序贪心即可。 对于当前的状态,设该进入到输出序列中的是 p,输入队列头是 q,S1 栈顶是 t1,S2 栈顶 是 t2,那么依次判

断,容易知道 q>=p i)如果 q<t1 或者 t1 不存在,执行 A,continue; ii)如果 t1=p,执行 B,continue; iii)如果 q<t2 或者 t2 不存在,执行 C,continue; iv)如果 q=t2,执行 D,continue; v)输出无解信息,halt;

这个算法应该是错误的。 一个反例是:7 2 5 1 4 6 3。 在上述四个判断条件中,能够产生冲突的只有 i 和 iii,在 i 和 iii 冲突的时候需要判断。 所以我对上述算法进行修改: i)如果((q<t1 或者 t1 不存在)and(输入队列中不存在 x,使得 q<t2<x<t1)) ,执行 A,continue; ii)如果 t1=p,执行 B,continue; iii)如果 q<t2 或者 t2 不存在,执行 C,continue; iv)如果 q=t2,执行 D,continue; v)输出无解信息,halt;

归纳法证明算法正确性: 当 n 很小的时候(至少我没举出反例)算法是正确的。 设 n<k 成立,考虑 n=k 的情况。 当 q=k 时,显然(不存在 x,使得 q<t2<x<t1),也没有 q<t1 或者 q<t2 的情况,所以 k 能够入 栈的充要条件是 t1

不存在或者 t2 不存在。 只要最大的数 k 放在了栈底,对其他的数都是没有影响的。所以算法依然正确。

证毕。 (表述的很不规范。 )

NOIP2008 提高组解题报告
angwuy

1 word
这道题完全是送分题,只需要直接统计,再判断素数。

参考程序: var st:string; max,min,i:longint; a:array['a'..'z']of longint; ch:char; function fun(n:longint):boolean; var i:longint; begin if n<2 then begin fun:=false;exit;end; for i:=2 to n-1 do if n mod i=0 then begin fun:=false;exit;end; fun:=true; end; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(st); fillchar(a,sizeof(a),0); for i:=1 to length(st) do inc(a[st[i]]); max:=0; min:=101; for ch:='a' to 'z' do if a[ch]>0 then begin if a[ch]>max then max:=a[ch]; if a[ch]<min then min:=a[ch]; end; if fun(max-min) then begin writeln('Lucky Word'); writeln(max-min); end else begin writeln('No Answer'); writeln(0); end; close(input); close(Output); end.

2 matches
搜索题,由于输入的情况只有 25 种,所以打表也是一种可行的方法。在数据最大时,经过 人工和电脑证明是不会到达四位数的,所以可以直接用 O(1000*1000)的搜索算法 参考程序: const mat:array[0..9]of longint=(6,2,5,5,4,5,6,3,7,6); function fun(m:longint):longint; var t:longint; begin t:=0; while m>0 do begin inc(t,mat[m mod 10]); m:=m div 10; end; fun:=t; end; var a:array[0..1000] of longint; n,i,j,ans:longint; begin assign(input,'matches.in'); reset(input); assign(output,'matches.out'); rewrite(output); readln(n); if n<10 then begin writeln(0);close(output);exit;end; a[0]:=6; for i:=1 to 1000 do a[i]:=fun(i); dec(n,4); for i:=0 to 1000 do if a[i]<n then begin for j:=0 to 1000-i do if a[i]+a[j]+a[i+j]=n then inc(ans); end; writeln(ans); close(input); close(output); end.

3 message
DP 题,两条路线必定一上一下,而且,当到达某一列后,前面对后面的不会有影响,符合 动态规划的无后效性,方程如下: 用 dp[I,j,k]表示当到达 I 列时,上路线在 j 行到,下路线在 k 行到的最大值。 另外加一个预处理,sum[I,j1,j2]表示在第 I 列 j1 到 j2 行的数加起来的和。 边界条件: dp[2,1,k]:=sum[1,1,k]; 递推方程: dp[I,j,k]:=max(dp[I-1,j2,k2]+sum[I-1,j,j2]+sum[I-1,k,k2]) {j<=j2<k<=k2} 答案: max(dp[m,j,n]+sum[m,j,n]) 参考程序: const maxn=10; var a:array[1..maxn,1..maxn]of longint; dp,sum:array[1..maxn,1..maxn,1..maxn]of longint; n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; begin assign(input,'message.in'); reset(input); assign(output,'message.out'); rewrite(output); readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end; for i:=1 to m do begin for i1:=1 to n do begin sum[i,i1,i1]:=a[i,i1]; for i2:=i1+1 to n do sum[i,i1,i2]:=sum[i,i1,i2-1]+a[i,i2]; end; end; fillchar(dp,sizeof(dp),255);

for i:=2 to n do dp[2,1,i]:=sum[1,1,i]; for i:=2 to m-1 do for j:=1 to n-1 do for k:=j+1 to n do if dp[i,j,k]>-1 then begin for j2:=j to k-1 do for k2:=k to n do dp[i+1,j2,k2]:=max(dp[i+1,j2,k2],dp[i,j,k]+sum[i,j,j2]+sum[i,k,k2]); end; k:=0; for i:=1 to n-1 do k:=max(k,dp[m,i,n]+sum[m,i,n]); writeln(k); close(input); close(output); end. 第四题的解题报告都有很多大牛写了,那我就不在这里献丑了 好象是用二分图来做的,在 OIBH 上有详细的题解


推荐相关:

NOIP2008提高组复赛试题及题解

NOIP2008普及组试题 7页 免费 NOIP2008提高组前三题解... 13页 免费 NOIP2008复赛普及组试题 6页 免费喜欢此文档的还喜欢 NOIP2008提高组解题报告 13页 免费 ...


NOIP2015提高组解题报告

NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区...[i]-=3;pai[cnt[i]]++; find(step+1); ...NOIP2015提高组复赛试题... 6页 免费 NOIP2015提高...


NOIP2008普及组复赛试题与解题报告

NOIP2008普及组复赛试题解题报告_学科竞赛_初中教育_教育专区。NOIP 2008 普及...1 位识别码和 3 位分 隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-...


2007年NOIP提高组第一题解题报告统计数字

2007年NOIP提高组第一题解题报告统计数字_电脑基础知识_IT/计算机_专业资料。1....NOIP2008提高组前三题解... 13页 免费 NOIP2005提高组第三题解... 21页...


NOIP2008_提高组_复赛试题

NOIP2008_提高组_复赛试题_学科竞赛_高中教育_教育...【输入】 第 3 页共 8 页 全国信息学奥林匹克...[i]之前弹出.而 q1[ j]>q1[i],这显然是不...


noip2010提高组解题报告

NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3 已经不错了。。真理。。! 考试结束。。觉得题都可做。。。 No1. 1.机器翻译...


NOIP2007提高组解题报告

【输入输出样例 1】 Game.in 2 3 1 2 3 3 4 2 【输入输出样例 1 解释...NOIP2008提高组复赛试题... NOIP2009提高组复赛题解 NOIP2010提高组解题报告 NOIP...


NOIP2010提高组解题报告

NOIP2010提高组解题报告_经济学_高等教育_教育专区。NOIP2010提高组解题报告今日推荐 78份文档 笑翻神图 爆笑图片汇集 搞笑图片乐翻人 cs3简单制作动态搞笑图片104份...


noip2010提高组解题报告

Noip2010 反观 2010 年的提高组题目:第一题机器翻译是一道纯模拟的题目, 第...NOIP2008提高组解题报告 13页 免费 NOIP2010提高组解题报告... 3页 免费喜欢...


NOIP2008提高组初赛试题_C++含答案 改动

NOIP2008提高组初赛试题_C++含答案 改动_学科竞赛_高中教育_教育专区。第十四届...完善程序 ( 前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分 ) 1...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com