算法艺术与信息学竞赛

算法艺术与信息学竞赛习题部分提示

部分习题提示

1.1节习题

1.1.1

对；不对

1.1.2

提示：考虑规模增长时的时间开销，可以对比运行时间，也可以在程序中统计基本操作数目

1.2节习题

1.2.1

不一定。这要看枚举量和枚举时间

1.2.3

枚举即可。需要注意的是要保证每个问题只有一个正确答案而不是有个答案。本题有唯一解cdebeedcba。

1.2.5

注意行有很多但是列不太多。硬币翻两次等于不翻，所以所有行/列最多翻一次。枚举每列是否翻有2^9=512种情况，此时可以用O(n)的时间计算每行是否翻（注意：列确定以后每行独立）。

1.2.6

只需要枚举横坐标相邻的点

1.2.7

设S1的长度为n。注意用串匹配来做的话时间复杂度至少为O(10^n)，不是有效算法。应该枚举S1的“分段方式”。例如231241，如果分段方式为23|124|1，则124为完整的一段，前面必为123，后面必为125，经检验这是可行的。因此如果有一个完整段的情况可以用O(n^2)次枚举来判定。剩下只需要解决没有完整段的情况，即被分成两段。如2312，如果被分为2|312，则需要枚举位数。如果是3位，有方程??2 + 1 = 312，无解；如果是4位，有方程???2 + 1 = 312?，有解31

浅谈信息学竞赛中的区间问题

华东师大二附中

周小博

【摘要】

本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近10道相关例题，进行简要分析。

【关键字】

区间模型 转化 贪心 动态规划 优化

1

【引言】

在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。

本文将从几个方面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论： 1.最大区间调度问题 2.多个资源的调度问题 3.有最终期限的区间调度问题 4.最小区间覆盖问题 5.带权区间调度、覆盖问题 6.区间和点的有关问题

我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。

本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，

浅谈信息学竞赛中的区间问题

华东师大二附中

周小博

【摘要】

本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近10道相关例题，进行简要分析。

【关键字】

区间模型 转化 贪心 动态规划 优化

1

【引言】

在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。

本文将从几个方面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论： 1.最大区间调度问题 2.多个资源的调度问题 3.有最终期限的区间调度问题 4.最小区间覆盖问题 5.带权区间调度、覆盖问题 6.区间和点的有关问题

我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。

本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，

信息学竞赛考试方式文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]

信息学竞赛考试方式

CF NOIP2017报名通知

CCF NOI系列活动之一2017年全国青少年信息学奥林匹克联赛（NOIP2017）将于2017年10月及11月分别举行初赛和复赛，有关竞赛事项公布如下。

竞赛方式：

1.初赛及复赛试题均采用电子版本，各省组织单位可视情况印刷纸质试题。

2.复赛提高组为两试，分两天进行，每试为三个题目。所有参加复赛提高组的选手均参加两天的比赛，选手最终成绩为一试与二试分数之和。复赛普及组为一试。

竞赛时间：

1.初赛（提高组、普及组）：

2017年10月14日（周六），14:30-16:30；

2. 复赛：

一试：2017年11月11日（周六），提高组8:30-12:00，普及组14:30-18:00；

二试：2017年11月12日（周日），提高组8:30-12:00。

竞赛报名：

1.初赛报名

NOIP2017初赛以省为单位，采用传统邮件方式报名。各省报名名单由各省特派员统一汇总后上报NOI竞赛办公室（）。

2.复赛报名

NOIP2017复赛以省为单位，完全采用网上注册报名方式。（复赛网上报名方式另行通知）复赛未在NOIP2017报名

信息学复赛模拟测试十

第一题 麦森数 (文件名：mason.pas)

问题描述：

P形如2-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是

P个素数，2-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

P任务：从文件中输入P（1000

输入文件mason.in:文件中只包含一个整数P（1000

P第一行：十进制高精度数2-1的位数。

P第2-11行：十进制高精度数2-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）

P不必验证2-1与P是否为素数。 样例

mason.in

1279 mason.out

386

00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 3861526224726670480531911235040360805967

算法在信息学奥赛中的应用 (基础篇)

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；

2、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。

3、输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设

中山市第三届小学生信息学邀请赛试题

比赛时间：2011年4月9日上午9：00-12：00

题目一览

试题名称 提交文件 输入文件名 输出文件名 满分 测试点数 时间限制 空间限制 注意事项：

1. 提交要求：首先在电脑的E盘下建立一个文件夹，名字为你的中文姓名，在该文件夹下建立一

个文本文件，名字也是你的中文姓名，把你所在学校、姓名、班级、家庭联系电话写在该文本文件中，最终你要提交的PAS文件和EXE文件也必须放在以你的中文姓名命名的文件夹下。如你的名字叫张三，一共有四道题，题目的文件名分别是1,2,3,4，那么张三同学提交的目录结

构如下： E:\\

---张三 (以姓名命名的文件夹)

---张三.TXT (以姓名为文件名的文本文件，内容包括学校、姓名、班级、电话) ---1.PAS (题目1的源程序) ---1.EXE (题目1的可执行文件) ---2.PAS (题目2的源程序) ---2.EXE (题目2的可执行文件) ---3.PAS (题目3的源程序) ---3.EXE (题目3的可执行文件) ---4.PAS (题目4的源程序) ---4.EXE (题目4的可执行文件) ---5.PAS (题目4的源

信息学竞赛初中组初赛模拟试题（一）及答案

选择题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题，即每题有且只有一个正确答案，选对得分；后10题为不定项选择题，即每题有1至5个正确答案，只有全部选对才得分）

1.操作系统是一类重要的系统软件，下面几个软件不属于系统软件的是（ ）。

A）MS-DOS B）Linux C）Java D）Windos 98 E）Unix

2. 按照网络覆盖面积和各台计算机相距的远近，计算机网络分为( ) A)广域网和局域网 B)信息交换网和广域网

C)分布式系统和集中式系统 D)公用网和专用网 E)总线网和星型网 3.某计算机的硬盘容量是40G，这里40G=( )字节.

A)40 B)40*1000 C)40*1024*1024 D)40*1024*1024*1024 E)40*1000*1000*1000 4．中缀表达式A-(B+C/D)*E的后缀表达式是（ ）。

A)AB-C+D/E* B) ABC+D/-E* C)ABCD/E*+- D)ABCD/+E*- E) AB-CD/

CCF NOI 2016获奖名单

金牌62名 证书编号 CCF-NOI16-001 CCF-NOI16-002 CCF-NOI16-003 CCF-NOI16-004 CCF-NOI16-005 CCF-NOI16-006 CCF-NOI16-007 CCF-NOI16-008 CCF-NOI16-009 CCF-NOI16-010 CCF-NOI16-011 CCF-NOI16-012 CCF-NOI16-013 CCF-NOI16-014 CCF-NOI16-015 姓名 毛啸 洪华敦 袁宇韬 罗哲正 徐明宽 丁力煌 周子鑫 吴作凡 闫书弈 钟知闲 杨景钦 徐泽涛 袁伟强 谢兴宇 叶昊星 省份 湖南 浙江 湖南 安徽 北京 江苏 浙江 安徽 福建 福建 四川 浙江 江苏 山东 浙江 性学校(全称) 别 男 长沙市雅礼中学 男 绍兴市第一中学 男 长沙市雅礼中学 男 安徽师范大学附属中学 男 北京师范大学附属实验中学 男 南京外国语学校 男 浙江省杭州学军中学 男 安徽师范大学附属中学 男 福建省福州第三中学 男 福建省福州第一中学 男 四川省成都市第七中学 男 浙江省余姚中学 男 南京师范大学附属中学 男 东营市胜利第一中学 男 杭州市

管理信息试卷一

一、单项选择题（每小题 1.5 分 , 本题共 30 分）

1 、管理信息可按多种方式进行分类，按（ ）分类，可将信息分为：人事信息、物资信息、资金信息等。 A ． 企业决策层次 B. 管理对象 C ． 信息稳定性 D ． 信息来源 2 、系统分析报告的重点内容是（ ）。

A ． 新系统的目标和逻辑模型 B ． 系统开发项目概述 C ． 现行系统的状况 D ． 系统实施计划 3 、下述哪个不是原型法的优点（ ）。

A ． 用户可及时反馈 B ． 省却了阶段性检查 C ． 用户积极参与 D ． 可较早发现错误和漏洞 4 、将用户角度上的概念结构转换为 DBMS 支持下的数据组织模式的过程称为（ ）。 A ． 数据库设计 B ． 数据存储设计 C ． 数据库的逻辑设计 D ． 数据库的物理设计

5 、找出企业的关键成功因素，围绕关键成功因素分析、确定企业的信息需求是什么，并进行管理信息系统的规划。这是制定管理信息系统总体规划的（ ）。

A ．价值链分析 B ．关键成功因素法 C ．企业系统规划法 D ．企业业务优化法 6 、在管理信息系统的编码中，把数据项分为几个组