手机

全国站

热门城市 | 全国 北京 上海 广东

华北地区 | 北京 天津 河北 山西 内蒙古

东北地区 | 辽宁 吉林 黑龙江

华东地区 | 上海 江苏 浙江 安徽 福建 江西 山东

华中地区 | 河南 湖北 湖南

西南地区 | 重庆 四川 贵州 云南 西藏

西北地区 | 陕西 甘肃 青海 宁夏 新疆

华南地区 | 广东 广西 海南

资    源
  • 资    源
当前位置:查字典高考网>高中频道>信息学联赛知识>信息学联赛知识:贪心策略的特点与在信息学竞赛中的应用

信息学联赛知识:贪心策略的特点与在信息学竞赛中的应用

来自:查字典高考网 2009-11-12

贪心策略的特点与在信息学竞赛中的应用

1、求最长路径问题(NOI93):

对一个不存在回路的有向图,编程求出途经结点数最多的一条路径。有向图存放在一个文本文件中,第0行为一个数字,为该图的结点总数N,其下还有N行,每行有N个非0即1的数字。若第i行第j列的数字为1,则表示结点i到结点j存在由i指向j的边,否则该数为0。

2、删数问题的源程序:

输入数据:一个高精度正整数N,所删除的数字个数S。

输出数据:去掉的数字的位置和组成的新的正整数。

Program Delete_digit;

Var n:string;{n是由键盘输入的高精度正整数}

s,a,b,c:byte;{s是所要删除的数字的个数}

data:array[1..200] of 0..9; {记录删除的数字所在位置}

begin

readln(n);

readln(s);

for a:=1 to s do

for b:=1 to length(n) do if n[b]n[b+1] then {贪心选择}

begin

delete(n,b,1);

data[a]:=b+a-1; {记录所删除的数字的位置}

break;

end;

while n[1]='0' do delete(n,1,1); {将字符串首的若干个0去掉}

writeln(n);

for a:=1 to s do writeln(data[a],' ');

end.

3、最优乘车问题

输入数据:输入文件INPUT.TXT。文件的第行是一个数字M(1100)表示开通了M条单向巴士线路,第2行是一个数字N(1500),表示共有N个车站。从第3行到第M+2行依次给出了第一条到第M条巴士线路的信息。其中第i+2行给出的是第i条巴士线路的信息,从左至右依次按行行驶顺序给出了该线路上的所有站点,相邻两个站号之间用一个空格隔开。

输出数据:输出文件是OUTPUT.TXT。文件只有一行,为最少换车次数(在0,1,,M-1中取值),0表示不需换车即可达到。如果无法乘车达到S公园,则输出NO。

Program Travel;

var m:1..100; {m为开通的单向巴士线路数}

n:1..500; {n为车站总数}

result:array[1..501] of -1..100; {到某车站的最少换车数}

num:array[1..500,1..50] of 1..500; {从某车站可达的所有车站序列}

sum:array[1..500] of 0..50; {从某车站可达的车站总数}

check:array[1..500] of Boolean; {某车站是否已扩展完}

Procedure Init;

var f1:text;

a,b,c,d:byte;

data:array[1..100] of 0..100;

begin

assign(f1,'input.txt');

reset(f1);

readln(f1,m);

readln(f1,n);

result[501]:=100;

for a:=1 to m do

begin

for b:=1 to 100 do data[b]:=0;

b:=0;

repeat

inc(b);

read(f1,data[b]);

until eoln(f1);

for c:=1 to b-1 do

for d:=c+1 to b do

begin

inc(sum[data[c]]);

num[data[c],sum[data[c]]]:=data[d];

end;

end;

end;

Procedure Done;

var min,a,b,c,total:integer;

begin

fillchar(result,sizeof(result),-1);

result[1]:=0;

for c:=1 to sum[1] do result[num[1,c]]:=0;

b:=data[1,1];

repeat

for c:=1 to sum[b] do

if (result[num[b,c]]=-1) then result[num[b,c]]:=result[b]+1;

min:=501;

for c:=1 to n do if (result[c]-1) and (result[c]result[min])

then min:=c;

b:=min;

until result[n]

writeln(result[n]);{到达S公园的最少换车次数}

end;

begin

Init;

end.

4、最佳游览路线问题

输入数据:输入文件是INPUT.TXT。文件的第一行是两个整数M和N,之间用一个空格符隔开,M表示有多少条旅游街(1100),N表示有多少条林荫道(120000)。接下里的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数,依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。

输出文件:输出文件是 OUTPUT.TXT。文件只有一行,是一个整数,表示你的程序找到的最佳浏览路线的总分值。

Program Tour;

var m,n:integer; {M为旅游街数,N为林荫道数}

data:array[1..20000] of -100..100;{data是由相邻两条林荫道所分}

procedure Init; {隔的旅游街的最大分值}

var a,b,c:integer;

f1:text;

begin

assign(f1,'input.txt');

reset(f1);

read(f1,m,n);

for a:=1 to n-1 do read(f1,data[a]); {读取每一段旅游街的分值}

for a:=2 to m do

for b:=1 to n-1 do

begin

read(f1,c);

if cdata[b] then data[b]:=c; {读取每一段旅游街的分值,并选择}

end; {到目前位置所在列的最大分值记入数组data}

close(f1);

end;

procedure Done;

var a,sum,result,c:integer;

f2:text;

begin

result:=0;

sum:=0;

a:=0;

while (an) do

begin

inc(a); {从数组的第一个数据开始累加,将累加所}

sum:=sum+data[a]; {得到的最大分值记入result}

if sumresult then result:=sum;

if sum0 then sum:=0; {若当前累加值为负数,则从当前状态起从新}

end; {累加}

assign(f2,'output.txt');

rewrite(f2);

writeln(f2,result);

close(f2);

end;

begin

Init;

Done;

end.

[标签:竞赛联赛,竞赛]

网友关注

2010年南通职业大学录取分数线

2010年湖南工程职业技术学院录取分数线

2010年长沙通信职业技术学院录取分数线

2010年湖南体育职业学院录取分数线

2010年湖南现代物流职业技术学院录取分数线

2010年湖南水利水电职业技术学院录取分数线

2010年湖南都市职业学院录取分数线

2010年湖南艺术职业学院录取分数线

2010年泰州职业技术学院录取分数线

2010年湖南科技经贸职业学院录取分数线

2010年长沙社会安全职业技术学院录取分数线

2010年湖南商务职业技术学院录取分数线

2010年湖南软件职业学院录取分数线

2010年南通纺织职业技术学院录取分数线

2010年无锡职业技术学院录取分数线

2010年湖南机电职业技术学院录取分数线

2010年湖南电子科技职业学院录取分数线

2010年湖南九嶷职业技术学院录取分数线

2010年郴州职业技术学院录取分数线

2010年广州城市职业学院录取分数线

2010年南京工业职业技术学院录取分数线

2010年娄底职业技术学院录取分数线

2010年张家界航空工业职业技术学院录取分数线

2010年邵阳医学高等专科学校录取分数线

2010年连云港职业技术学院录取分数线

2010年长沙环境保护职业技术学院录取分数线

2010年民办明达职业技术学院录取分数线

2010年广州南洋理工职业学院录取分数线

2010年苏州工艺美术职业技术学院录取分数线

2010年无锡商业职业技术学院录取分数线

网友关注视频

2019高考·语文试题有亮点 凸显时代主题 厚植家国情怀

凤凰县高级中学高考试卷分析专题教研会

高考前必听的5首励志歌曲,《Dream it possible》最能鼓舞人心!

这!就是专业 第18集 中国科学技术大学

这!就是专业 第36集 河北经贸大学——数学专业

体育大杂烩 第2217集 太厉害!马龙登上全国高考作文题

学渣男高考英语全写B,老师给老爸说成绩,老爸直接听懵了!

这!就是专业 第47集 江苏理工学院

看懂图片,你也会做高考地理题,解析2019年高考文综地理4

高考阅卷名师给考生的高考作文密训课 第4集 高考作文审题实操方法精讲(二)

北京新闻 2019 5.9万余北京考生今日高考 语文试题鼓励创造性阅读与表达

这!就是专业 第31集 阜阳师范学院信息工程学院

这!就是专业 第15集 中国矿业大学——数学专业

武汉美术高考

amc传媒音乐影像 第一季 第598集 西安原创乐队走进英泰青卓 用音乐助力高考学子

爆笑班主任 第一季 第220集 高考前最后一只视频,山东王老师揭秘高考的秘密

【高考英语】七选五解析,不算太难

探秘历史 第二季 第233集 考英语用来睡觉,结果仍是高考状元,如今她怎么样了?

探秘历史 第二季 第211集 此人高考数学考了0分,因作文写3句话被重点大学录取

凤凰县高级中学高考试卷分析专题教研会

高考政治一轮:《经济生活》第九课(社会主义市场经济)练习

最新高考数学全国2卷第12题视频解读

高中数学 107 高考如何秒杀数列

【姜浩张超画室】

高考英语作文分析2

视频|2019全国高考今日开考: 语文特级教师评析上海卷高考作文

高级中学高考试卷分析专题教研评比活动

视频|上海高考作文: 寻找“中国味” 专家

初二辍学,3次高考落榜,如今却成为最成功的音乐人之一

招办面对面 第76集 阜阳师范学院信息工程学院