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

Noip 2003 提高组 解题报告1


Noip 2003 提高组 解题报告
题一 分析: 这一题有很多种方法,数据也较弱。我考虑到其中的层次关系,用类似于广搜的方法, 但是注意到每个结点不仅仅是由当前 head 节点扩展,而是当前队列全部节点。 源程序: program network1; const maxn=100; var c,u:array[1..maxn]of longint; //c,状态数组;u,阈值数组 w:array[1..maxn,1..maxn]of longint; //表示是否连通(有向图) anstp,head,tail,n,i,j,p,k,x,y:longint; q:array[1..10000]of record dep,num:longint; end; //队列记录两个变 量(层次与号码) ct:array[1..maxn]of boolean; //判重数组 ans:array[1..maxn]of longint; //答案,记得排序,故先用数组暂存 tag:boolean; //判断是否输出 NULL procedure qsort(s,t:longint); //快速排序 var i,j,d,x:longint; begin i:=s; j:=t; x:=ans[(s+t)shr 1]; repeat while ans[i]<x do inc(i); while ans[j]>x do dec(j); if i<=j then begin d:=ans[i]; ans[i]:=ans[j]; ans[j]:=d; inc(i); dec(j); end; until i>j; if s<j then qsort(s,j); if i<t then qsort(i,t); end; begin assign(input,'network.in'); reset(input); assign(output,'network.out'); rewrite(output); {init} readln(n,p); 神经网络

for i:=1 to n do readln(c[i],u[i]); fillchar(w,sizeof(w),0); fillchar(ct,sizeof(ct),false); for i:=1 to p do begin readln(x,y,k); w[x,y]:=k; w[y,x]:=k; end;

{main} head:=0; tail:=0; for i:=1 to n do if c[i]>0// 对首层的操作,可以传递兴奋则进队 then begin ct[i]:=true; inc(tail); q[tail].dep:=1; q[tail].num:=i; end; for i:=1 to n do if c[i]<=0 then c[i]:=-u[i]; //先确定起始值 repeat x:=head; repeat inc(x); if c[q[x].num]<=0 then continue; //若兴奋性<=0,则不会向下传 递,枚举下一个 for i:=1 to n do if not ct[i] and (w[q[x].num,i]<>0) //没有入队,存在有向边连 接 then c[i]:=c[i]+c[q[x].num]*w[q[x].num,i]; until x>=tail; 一层的全部元素。 x:=tail; repeat inc(head); for i:=1 to n do if not ct[i] and (w[i,q[head].num]<>0) then begin inc(tail); ct[i]:=true; q[tail].num:=i; q[tail].dep:=q[head].dep+1; end; //拓展队列,注意无论是否兴奋,都要入队,否则可能被当作下一层的。 //恢复尾指针 //下一层不仅仅取决于上一层的某一个元素,它来源于上

until head>=x; until head>=tail; {show} x:=q[tail].dep; k:=1; for i:=tail-1 downto 1 do if q[i].dep<>x then begin k:=i+1; break; end; //找出最后一层的元素 anstp:=0; for i:=k to tail do if c[q[i].num]>0 then begin inc(anstp); ans[anstp]:=q[i].num; end; //此时必须满足 c[k]>0 qsort(1,anstp); //别忘了排序 tag:=false; for i:=1 to anstp do begin tag:=true; writeln(ans[i],' ',c[ans[i]]); end; if not tag then writeln('NULL'); close(input); close(output); end. //没有 c[k]>0

题二 分析:

侦探推理

注意格式,前四句的东东是连在一起的,最后一句有'Today is '和'.'! 题目的两个油人的条件 1.M 是参加游戏的明明的同学数,N 是其中始终说谎的人数,P 是证言的总数。 即没有说话自相矛盾的人,有则直接退出。 2.往后有 P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是 一句证词,符合前表中所列格式。 是一句证词,只包括上述证词内容中的一个, 3.注意一共 M 个人,不要搞成 n 个人! 我们采用枚举法,先仔细处理字符串,在枚举某人是罪犯的情况下,枚举今天是星期 几。 源程序: program kj; const s:array[1..11]of string= ('I am guilty.',' is guilty.',

'I am not guilty.',' is not guilty.', 'Today is Monday.','Today is Tuesday.', 'Today is Wednesday.','Today is Thursday.', 'Today is Friday.','Today is Saturday.', 'Today is Sunday.'); {把证词信息化的有效方法,以上 11 种形式把全部的情况都限定死了,彻底排除 诸如 'Today is Mondayday.','Bush am guilty','FanPaopao is not guilty?','Iam guilty' 等等情况。注意千万不要忘掉了末尾的.否则,上述第三个便是正确形式了。另 一方面, 也不能简单的用'Today is '来圈定有关星期的证词,除非找到后再判断后面 的字符串 符不符合 'week.'的形式,后面的点是考点之一,看你读题细不细心} type ktype=record //记录同学信息 name:string; //名字 right:longint; //诚信记录,0 表示尚无记载,1 表诚实人,2 表撒 谎者 end; ztype=record //记录证词信息 kind,from,data:longint; //kind=1,为确认罪犯;kind=2,为确 认非罪犯;kind,3,为确认星期几。 from,证词所属证人。 data,证词信息化--罪 犯编号,星期编号(星期一是 1,。。。,星期天是 7) end; var ii,criminal,cnum,m,n,p:longint;//cnum 罪犯个数,超过一则跳出,输出 Cannot Determine; criminal 罪犯编号 a:array[1..100]of ktype; evi:array[1..1000]of ztype; //同学 //证词

procedure workproof(st:string; var z:ztype); //证词信息化过程 var sr:string; ti,tj:longint; begin sr:=''; ti:=0; while true do begin

inc(ti); if ord(st[ti])=58 then begin tj:=ti; break; end; sr:=sr+st[ti]; end; delete(st,1,tj+1); for ti:=1 to m do if a[ti].name=sr then begin z.from:=ti; break; end; //姓名信息化为 a 数组中编号 for ti:=1 to 11 do if pos(s[ti],st)<>0 then begin case ti of 1:begin z.kind:=1; z.data:=z.from; end; 2:begin for tj:=1 to m do if a[tj].name=copy(st,1,pos(s[ti],st)-1) then begin z.kind:=1; z.data:=tj; break; end; 找到所说的人,跳出 end; 3:begin z.kind:=2; z.data:=z.from; end; 4:begin for tj:=1 to m do if a[tj].name=copy(st,1,pos(s[ti],st)-1) then begin z.kind:=2; z.data:=tj; break; end; end; 5:begin z.kind:=3; z.data:=1; end; 6:begin z.kind:=3; z.data:=2; end; 7:begin z.kind:=3; z.data:=3; end; 8:begin z.kind:=3; z.data:=4; end; 9:begin z.kind:=3; z.data:=5; end; 10:begin z.kind:=3; z.data:=6; end; 11:begin z.kind:=3; z.data:=7; end; end; //确认星期的证词 // //在说自己 //对应于 const 中 s 数组的 11 种标准格式 //提取证词提供者姓名

break; end;

//每人之说一句话,即每个证词只有一个信息,搜到就退出

{由于初始化 kind=0,所以若此句话为废话,则有 kind 的值即可推得} end; procedure init; var i,j,k,t:longint; st:string; begin fillchar(evi,sizeof(evi),0); fillchar(a,sizeof(a),0); readln(m,n,p); for i:=1 to m do readln(a[i].name); for i:=1 to p do begin readln(st); workproof(st,evi[i]); end; cnum:=0; end; procedure work(v:longint); var day,i,j,k,x,y:longint; flag:boolean;//x 表示诚实的人数,y 表示撒谎 的人数,诚信的人数 x 应该<=m-n,撒谎的人数 y 应该<=n; begin for day:=1 to 7 do begin for i:=1 to m do a[i].right:=0; flag:=true; //跳出循环的标记 //初始化诚信记录 //枚举今天星期几 //罪犯人数初始化为 0 //对每条证词信息化

for i:=1 to p do case evi[i].kind of 1:begin if evi[i].data=v then if a[evi[i].from].right=2 产生矛盾 //若诚信记录显示为撒谎者, //确认罪犯证词 //若与证词相符(说的是真话)

then begin flag:=false; break; end

//产生矛盾(题中

说 n 个撒谎者,其余人均说真话,既不可能存在矛盾),该情况不可能,继续穷举星期 else a[evi[i].from].right:=1 //不矛盾,记为诚实者(要 么已经是诚实的人,要么诚信记录为空) else //若与证词相反(说的是假话) //若诚信记录显示为诚实人,

if a[evi[i].from].right=1 产生矛盾

then begin flag:=false; break; end 跳出枚举证词循环,继续穷举星期

//自悖,不可能,

else a[evi[i].from].right:=2;//不矛盾,记为说谎者 end; 2:begin if evi[i].data<>v then if a[evi[i].from].right=2 then begin flag:=false; break; end else a[evi[i].from].right:=1 else if a[evi[i].from].right=1 then begin flag:=false; break; end else a[evi[i].from].right:=2; end; 3:begin if evi[i].data=day then if a[evi[i].from].right=2 then begin flag:=false; break; end else a[evi[i].from].right:=1 else if a[evi[i].from].right=1 then begin flag:=false; break; end else a[evi[i].from].right:=2; end; end; //判断程序与上述完全一样 //确认星期证词 //判断程序与上述完全一样 //确认非罪犯证词

if not flag then continue; x:=0; y:=0; //人数初始化 for i:=1 to m do begin if a[i].right=1 then inc(x); if a[i].right=2 then inc(y); end; if (x<=m-n) and (y<=n) then begin inc(cnum); criminal:=v; //罪犯为过程参量 v break; end; end; end; begin assign(input,'logic.in'); reset(input); assign(output,'logic.out'); rewrite(output); init; //信息初始化 //枚举谁是罪犯 //该星期下,罪犯已被确认,不用再管其它的星期了 //由每人的诚信记录统计 x,y //找到罪犯

for ii:=1 to m do begin work(ii);

//枚举过程

if cnum>1 then begin writeln('Cannot Determine'); close(input); close(output); halt; end; (*可行性剪枝, 只用考虑罪犯数, 多于 1 则直接输出'Cannot Determine'*) end; if cnum=0 then writeln('Impossible') //程序判断出无罪犯 else writeln(a[criminal].name); //输出罪犯 close(input); close(output); end. 题三 加分二叉树

分析: 虽然题目给出的是树的条件, 但是不要把它认为是树形动态规划, 由于题中给出的是 中序,所以直接当作线性就可以,枚举树根。 源程序: program kk3; var r,n,i,j,k,t:longint; a:array[1..100]of longint; f:array[0..100,0..100]of longint; s:array[1..100,1..100]of longint; tag:boolean; procedure otry(x,y:longint); begin if x>y then exit; if not tag then begin tag:=true; write(s[x,y]); end else write(' ',s[x,y]); if x=y then exit; otry(x,s[x,y]-1); otry(s[x,y]+1,y); end; begin assign(input,'binary.in'); reset(input); assign(output,'binary.out'); rewrite(output); readln(n); for i:=1 to n do read(a[i]); fillchar(f,sizeof(f),0); for i:=1 to n do begin s[i,i]:=i; f[i,i]:=a[i]; end; //递归 边界 for i:=1 to n do for j:=0 to i-1 do f[i,j]:=1; //下三角矩阵初始化 {把树形结构变为线性结构,动规} for r:=2 to n do//线段长--结点个数 for i:=1 to n-r+1 do//第一个序号 begin j:=i+r-1;//最后一个序号

for k:=i to j do//枚举树根 begin t:=a[k]+f[i,k-1]*f[k+1,j]; if t>f[i,j] then begin f[i,j]:=t; s[i,j]:=k; end; //记录最优解,以便递归求先序排列 end; end; writeln(f[i,n]); tag:=false;//控制空格。 otry(1,n); close(input); close(output); end.

题四 分析:

传染病控制

本题的意思就是给出一个多叉树,每层砍掉一个支,要求剩下最少。我们可以采用搜 索的方法,砍掉一颗子树,就把该子树的兄弟节点的儿子节点归到该节点下。注意回溯后 要还原数组。 源程序: program kk4; const maxn=500; //more than maximum var num,best,n,p:longint; a:array[1..maxn]of record l:longint; d:array[1..maxn]of longint; end; //define a as an record type,making a[0] be the length is also good procedure init; var i,k,x,y:longint; begin best:=maxlongint; fillchar(a,sizeof(a),0); readln(n,p); for i:=1 to p do begin readln(x,y); ordered sequence //Never consider testdata would give you an

if x>y then begin k:=x; x:=y; y:=k; end; inc(a[x].l); a[x].d[a[x].l]:=y; //increase the subtree number of x,make y the last subtree(a[x].l) of x end; num:=1; end; procedure otry(k,num:longint); var temp,i,j,root,z,r:longint; tag:boolean; t:array[1..maxn]of longint; tl:longint; begin if a[k].l<=1 then begin if num<best then best:=num; exit; end; // If No.k has only one or none son(It must be cut,we can only cut this one,so exit) tag:=false; //tag=true means every son of No.k is a leave. for i:=1 to a[k].l do if a[a[k].d[i]].l>0 //If No.k's No.i son is not a leave then begin tag:=true; temp:=num; //traceback pretreatment if i=1 then z:=2 else z:=1; // What if k has only one subtree?/?/?--we've discussed at the beginning of the procedure root:=a[k].d[z]; //Remember,z only means No.k's No.z son,we have to transform it into People No.root tl:=a[root].l; //traceback pretreatment

for j:=1 to tl do t[j]:=a[root].d[j]; //traceback pretreatment for j:=1 to a[k].l do //combine tree,make No.k's subtrees(except i and z)'s subtrees be No.root's subtree. if (i<>j) and (z<>j) then begin for r:=1 to a[a[k].d[j]].l do a[root].d[a[root].l+r]:=a[a[k].d[j]].d[r]; //not the one cut,not root

a[root].l:=a[root].l+a[a[k].d[j]].l; // Don't forget to add the number end; otry(root,num+a[k].l-1); //add infected people number(except the son cut) a[root].l:=tl; //revert //revert

for j:=1 to tl do a[root].d[j]:=t[j]; end;

if not tag //If No.k's subtrees are nothing but leaves then begin num:=num+a[k].l-1; //Just add,no recursion if num<best then best:=num; //find answer end; end; begin assign(input,'epidemic.in'); reset(input); assign(output,'epidemic.out'); rewrite(output); init; //initial

otry(1,1); //Start with No.1.NOTICE that there are one infected at first writeln(best); //show close(input); close(output); end.


相关文章:
NOIP2001提高组解题报告1.doc
NOIP2001提高组解题报告1_初三数学_数学_初中教育_教育专区。NOIP2001提高组(...1885.03 5 1924.23 6 1 27 29 16 14 21 32 23 31 24 33 41 21 42...
NOIP2003提高组.pdf
NOIP2003提高组_互联网_IT/计算机_专业资料。第九届全国青少年信息学奥林匹克联赛( N0IP2003 ) 2003 年 11 月 29 日 提高组试题 三小时完成 题一【问题背景...
noip2003提高组题目.doc
noip2003提高组题目 - 第九届全国青少年信息学奥林匹克联赛(N0IP2003) 2003 年 11 月 29 日 提高组试题 三小时完成 题一 神经网络 【问题背景】 人工神经网络...
NoiP2003提高组复赛试题分析_天津南开中学滕伟.doc
Noip 2003 提高组 解题报... 12页 免费 NOIP2003解题报告 10页 1下载券 NOIP2010提高组复赛复习... 70页 1下载券 NOIP复赛冲刺资料集锦10 45页 免费 NOIP20...
NOIP2003提高组初赛试题.doc
NOIP2003提高组初赛试题_其它考试_资格考试/认证_教育...已知 S(Ci)∩S(C6)≠ф,i=1,2,...,5,S(...NOIP1997普及组解题报告 NOIP1997普及组初赛试题1...
NOIP2005提高组第一、二题解题报告_图文.ppt
NOIP2005提高组、二题解题报告 - NOIP2005提高组、二题 解题报告 谁拿了最多奖学金 (scholar.pas/c/cpp) 【问题描述】 某校的惯例是在每学期的...
NOIP2003提高组初赛答案.doc
NOIP2003提高组NOIP2003提高组隐藏>> 第九届分区提高组官方参考解答 一,单选 10 题 每题 1.5 分 B B D A B B C E C B 二,不定项选择 10 题 每题...
NOIP2011提高组解题报告day1.doc
NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地毯 【问题描述】 为了准备个独特的颁奖典礼,组织者在会场的片矩形区域(可看做是...
NOIP2002提高组初赛试题答案.doc
NOIP2002普及组解题报告 4页 免费喜欢此文档的还喜欢 NOIP2003提高组初赛答案 1页 免费 NOIP2005提高组初赛试题及... 7页 免费 NOIP2001提高组初赛试题答... ...
第九届全国青少年信息学奥林匹克联赛(N0IP2003)解题报告.doc
noip复赛重要知识第九届全国青少年信息学奥林匹克联赛( 第九届全国青少年信息学...(N0IP2003) ) 复赛提高组解题报告题一 【问题背景】 人工神经网络(Artificial ...
2007年NOIP提高组第一题解题报告统计数字.doc
2007年NOIP提高组解题报告统计数字_电脑基础知识_IT/计算机_专业
NOIP2005提高组解题报告.doc
NOIP2005提高组解题报告_初一理化生_理化生_初中教育_教育专区。NOIP2005提高组NOIP2005 信息学奥林匹克分区联赛 解题报告 [麓山 NOI 战队] 第一题:谁拿了最多的...
NOIP2015提高组解题报告.doc
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造
Noip 2013 提高组 解题报告.pdf
Noip 2013 提高组 解题报告 --By GreenCloudS Day
加分二叉树解题报告.doc
加分二叉树解题报告_电脑基础知识_IT/计算机_专业资料。树型DP,动态规划2014.8.19 加分二叉树【NOIP2003 提高组】 Description 设一个 n 个节点的二叉树 tree ...
noip2010提高组解题报告.doc
NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3...Noip 2003 提高组 解题报... 12页 1下载券 NOIP2000-2009提高组解题... ...
NOIP2007提高组解题报告.doc
NOIP2007 提高组解题报告 1. 统计数字(count.pas/c/cpp)【问题描述】 某次...Noip 2003 提高组 解题报... 12页 1下载券 NOIP2010提高组解题报告 6页...
NOIP2002-2005解题报告.doc
noip2005提高组解题报告... 52页 免费 2005TP初赛解题报告 暂无评价 15页 1下载...二、NOIP2003 题一:神经网络(Network) 【问题描述】人工神经网络(Artificial ...
NOIP 2012 提高组 解题报告.pdf
Day 1: Problem Vigenère 密码(vigenere) 国王游戏(game) 开车旅行(drive) Contest...Noip 2003 提高组 解题报... 12页 免费 noip2005提高组解题报告... 52...
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2 - 计算系数 【问题描述】 给定一个多项
更多相关标签: