全国站

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

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

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

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

华中地区 | 河南 湖北 湖南

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

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

华南地区 | 广东 广西 海南

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

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

来自:查字典高考网 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为最小的体力耗费值。

【信息学联赛知识:基本程序题集】相关文章:

2005年全国高中数学联赛考点诠释(一)

高中数学联赛培训讲义(一)

高中数学联赛培训讲义(二)

高中数学竞赛大纲

2007年全国高中数学联赛陕西赛区预赛试题与答案

高中数学联赛培训讲义(三)

2005年全国高中数学联赛考点诠释(二)

信息学联赛知识:动态规划的状态表示(二)

2007年全国高中数学联赛(吉林赛区)预赛试题

高中化学:最后30天要把错题再做一遍

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

网友关注

美国高考拿满分考上耶鲁大学 才女学习有法宝

高考时间不变政策微调 招生章程提前30天公布

2008年高考将建考生电子档案库 禁止擅自更改

北京“绿卡”学生高考无门 5年前政策难落实

女孩将高考笔记整理出书 获利一万捐出五千

新高考体现改革要求 高考评价机制待完善

高考状元贺鼎现身说法:问鼎清华 方法为赢

2008年高考招生政策和考务管理7个方面有变化

教育部全面部署2008年全国普通高校招生工作

认识未来的自己 职业规划何时进入中学课堂?

清华保送生:高考学习其实是分阶段的马拉松

高三学生“一诊”考试 嫦娥一号等热点成考题

多做真题勤反思 “武侠迷”卧薪三年保送南大

“小手”打乱艺考梦 美院考纲之变成最热话题

快讯:香港大学医学院纳入08年内地招生计划

棒喝时代:只有研究型大学才能成世界一流吗?

查字典高一数学精品公开课 高德教学点现场

梦想的力量无穷大 看这一群漂在北京的艺考生

加大力度严肃考纪 高考舞弊严重者取消成绩

三好学生高考前“失明”辍学一年 难忘读书梦

副作用严重 家长千万别给孩子乱吃“聪明药”

成都一高三学生 20天写出30万字的明史小说

从英国血统到美国血统 看香港的大学和高考

800考生聚集北交大 统测2008年高考艺术特长

高三故事:最后阶段我和儿子的斗争与反斗争

“90后”学生出奥数题 竟然难倒“80后”家教

十年浇开苦菜花:贫家女孩获资助 现完成学业

港校住宿管理模式:宿舍更像家 申请靠自己

理科高考状元经验谈:高考复习的“六要六忌”

高考经验:高三学生如何正确分析考试的分数

网友关注视频

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

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

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

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

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

【姜浩张超画室】

优秀!英语数学双满分,广西“最牛”高考状元730分刷新最高纪录

你高考成绩高吗?这道题目怎能成立?高难度奥数,能不能把你难住

他高考作文仅得6分,总分428分,被985高校录取,却被导师拒绝!

印度美术高考美术联考,考前培训班

招办面对面 第2集 中国科学技术大学

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

良心推荐:2019高考数学全国3卷理科12题讲解,附答案

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

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

沈阳音乐学院郎亦农教授的女高音高考曲目解析课程 第1集 沈阳音乐学院郎亦农为你讲解女高音高考曲目

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

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

葛军大爷怒了:高考我出了个小学数学送分题,你们跟我说不会做?

2019年高考试卷解析,数学套路不好用了

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

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

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

张雪峰高考志愿填报指南 第15集 高考填报志愿,想学电子信息类专业,推荐报这六所高校,不出错

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

这四首励志歌曲,送给为梦起航的高考学子们,听完心潮澎湃!

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

美术联考用纸上海考试模拟试卷纸高考统考纸 4k水粉纸素描纸 速写纸卡纸美术模拟测试试卷纸 美术考试专用纸

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

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