手机

全国站

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

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

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

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

华中地区 | 河南 湖北 湖南

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

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

华南地区 | 广东 广西 海南

资    源
  • 资    源
当前位置:查字典高考网>高中频道>信息学联赛知识>信息学联赛知识:基本程序题集

信息学联赛知识:基本程序题集

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

基本程序题集

NOIP是一个比较基础的比赛,大家都说NOIP是考察基本算法的熟练掌握,所以个人认为无论是普及组还是提高组,都要从最最基本的题做起,要达到:只要是简单题,编完就对--不用编译;一般的题,写出来的都是对的--运行后几本上是正确的。为了提高,于是做了一个基本程序题集,以便查找自己的不足之处。

题集目录

一、贪心算法

Problem1删数问题

Problem2旅行家的预算

Problem3线段覆盖

Problem4背包问题

Problem5任务调度

Problem6果子合并

Problem7射击竞赛

Problem8任务安排

Problem9最小差距

二、分治算法

Problem1一元三次方程的解

Problem2查找第k大元素

Problem3麦森数

Problem4逆序对个数

Problem5寻找最近点对

Problem6剔除多余括号

Problem7赛程安排

三、搜索算法

Problem1皇后问题

Problem2八数码问题

Problem3拼图

Problem4质数方阵

Problem5埃及分数

Problem6字符串变换

Problem7聪明的打字员

Problem8 01序列

Problem9生日蛋糕

四、图论算法

Problem1一笔画问题

Problem2 Car的旅行路线

Problem3求割点与桥

Problem4十字绣

Problem5舞会

Problem6休息中的小呆

Problem7最优布线问题

Problem8磁盘碎片整理

Problem9说谎岛

Problem10 01串问题

Problem11海岛地图

五、数学问题

Problem1数的划分

Problem2最优分解方案

Problem3出栈序列统计

Problem4百事世界杯之旅

Problem5电子锁

Problem6堆塔问题

Problem7取数游戏

Problem8球迷购票

Problem9 Fibonacci公约数

Problem10传球问题

Problem11约瑟夫问题

Problem12青蛙过河

Problem13棋盘游戏

六、数据结构

Problem1火车栈

Problem2括号表达式

Problem3银河英雄传说

Problem4矩形覆盖

Problem5最短路径问题

Problem6果子合并

七、字符串处理

Problem1相对分子质量

Problem2表达式求值

Problem3侦探推理

Problem4最长公共子串

Problem5一元一次方程的解

Problem6多项式乘法

一、贪心算法

Problem1删数问题

题目描述:

给定一正整数n(n的位数小于240),现要删除数n中的s个数码,使其得到的新数最小,求这个最小数。

输入

输入有两行,第一行为整数n,第二行即为s

输出

输出一行,即最小的那个数

Problem2旅行家的预算

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N(N可以为零),油站i离出发点的距离i、每升汽油价格Pi(i=1,2,N)。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出No Solution。

输入

输入第一行有5个数:D1,c,D2,P,N(前四个为实数,N为整数,N=1000)

后面有N行,每行两个实数,分别表示对应的加油站离出发点的距离,与每升汽油的价格

输出

输出仅一行,即最少花费

Problem3线段覆盖

题目描述

给定数轴上的n条线段(n100),每个线段有其端点ai、bi组成(-999bi=999),由于有些线段会相互覆盖,所以求出至少去掉多少条线段,才能使剩下的所有线段之间互相没有内部公共点(若只是端点重合,则不是内部公共点)。

输入

输入第一行为整数N,接下来有N行,分别描述每条线段

输出

输出第一行为最少删除的线段数s

后面s行描述一个可行的删除方案,即删除那些线段

Problem4背包问题

题目描述

有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元,重Wi磅,(1n),此处Vi和Wi都是整数。他希望带走的东西越值钱越好,但他的背包中最多只能装下W磅的东西(W为整数),小偷可带走某个物品的一部分(只带走其中的几磅),小偷应该带走哪几件东西,每件东西的重量是多少?

输入

输入第一行为N(N=10000),后面N行描述每个物品,每行两个数,即为Vi与Wi

输出

输出第一行为大的最大价值,后面依次描述物品i应偷多少(如果没偷,则不输出,输出对应的i为升序)。

Problem5任务调度

题目描述

一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:

1.包含n个单位时间任务的集合S={1,2,

2.n个取整的期限d1,,dn,(1n),任务i要求在di前完成;

3.n个非负的权(或罚款)w1,,wn。如果任务i没在时间di之前结束,则导致罚款wi;

要求找出S的一个调度,使之最小化总的罚款。

输入

输入第一行为N(N=1000),后面N行每行两个数,即为对应的di与wi

输出

输出最小总罚款Problem6果子合并

Problem6果子合并

题目描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

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

网友关注

谁愿意只做陪衬 中等生如何修炼成尖子生?

浏阳大妈经历33场考试 56岁获得大学文凭

杭州美女学霸登《科学》杂志封面 名校履历闪亮

2016年三亚高考体检将从2月24日开始进行

2017年山东省将进入高考改革试点 免费师范生教育

2016年雅安:这些新规事关高考 考试作弊被纳入法律

直击中戏艺考现场 考生素颜上阵排长队(图)

2016高考复习2月-6月规划:百日冲刺再提100分

2016年3月1日起北京高考生将开始体检 会检查丙氨酸氨基转移酶

再报江苏高考新方案获批 已于今天上午公布

21岁女大学生8年拔光头发:不拔几根就睡不着

2016年高考,全国各地都使用哪套试卷?

83岁“高考狂人”第12次参考 称人都有点理想

阅卷老师亲自整理的高考得分宝典

2016年青海对口高职考试纳入高职院校单考单招工作的通知

全国建筑类院校盘点:新老“八校”你都知道吗

从审题到素材运用 专家指导避开高频误区

15年本科“红牌专业”出炉 你“躺枪”了么?

2016年湖南高考全部使用全国卷 名师细谈变化与备考

2016年山东省春季高考特殊考生报名的通知

童星关晓彤素颜现身北影 引来众人围观(图)

2016年高考复习干货!针对考试丢分点的四个建议

高校图书馆借阅书单发布:复旦学霸武大武侠

山东六类考生享受增加分数或降低分数投档

高考经验分享:这样对症下药才事半功倍

教育部透露2016年高考命题要点 传统文化、创新能力都要考

2016年联合招收华侨、港澳台学生福建报名点公告

江苏高考新方案获批 将实施“3+3”模式

辟谣:2017年海南高考改革方案目前还未公布

高考前最后的寒假:谁的青春不奋斗

网友关注视频

星闻乐坊 第1272集 张杰的一首歌成了高考神曲

探秘历史 第二季 第479集 河南叛逆高考生,写下8000字批判作文,现状如何?

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

2019 广西:帅气学霸高考730分 数学英语满分!

这!就是专业 第20集 长沙理工大学—数据科学专业

爆笑班主任 第一季 第221集 高考结束学生有多疯狂?山东王老师疯狂吐槽

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

高中数学必修5 高考数列选填真题技巧秒杀讲解

高考同学看过来,难度系数三颗星的奥数1

励志歌曲《阳光总在风雨后》送给高考的莘莘学子,祝金榜题名!

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

2019年高考数学全国2卷理科第4题讲解及答案

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

最新高考数学全国2第12题视频讲解及答案

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

体育生参加高考,太猛了,第一名是飞起来了吗?

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

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

广州早晨 2019 山西一高中班主任带学生骑行1800公里去上海

【姜浩张超画室】

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

2019高考语文全国2卷小说阅读解析

amc传媒音乐影像 第一季 第600集 高中校长演唱《记忆花园》为高考学子助力打气

老师好:这大概是高考前所有班主任都会干的事,取消一切副课!

高考作文:全国2卷 材料作文破题分析 2019高考助力

老马讲高考真题第九季2018年高考地理新课标一卷第37题

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

2019全国高考志愿填报攻略 第50集 天津市高考历史三年本科录取排名

张雪峰高考志愿填报指南 第47集 高考志愿,令人头疼的数学系,才是专业万金油,毕业后机会多

高职高考数学公式