NOIP算法

算法总结

一、 动态规划和递推

dp一般的解题步骤： 分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化 由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧

Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解

关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。

二、 图论及网络流

最小生成树：克鲁斯卡尔算法和普利姆算法，

——重要性质1：最小生成树上任意两点的路径的最大边最小

——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数）

最短路：spfa算法、堆+迪杰斯特拉算法

Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 ——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后

SMTP（Simple Mail Transfer Protocol）即简单邮件传输协议 超文本传输协议(HTTP，HyperText Transfer Protocol) TCP：Transmission Control Protocol 传输控制协议

FTP 是File Transfer Protocol（文件传输协议）的英文简称

POP3(Post Office Protocol 3)即邮局协议的第3个版本,它是规定个人计算机如何连接到互联网上的邮件服务器进行收发邮件的协议

Noip推荐使用的语言环境

1. Windows平台:

Dev-C++ 4.9.9.2（其中包括了Windows版gcc/g++ 3.4.2版）； Lazarus 0.9.10 (其中包括了Windows版free pascal 编译器2.0.1版)； 2. Linux平台:

Red Hat 9.0 自带了gcc/g++ 3.2.2版； Lazarus 0.9.6版;

free pascal编译器1.9.8版

gdb 6.3版(Lazarus调试时需要使用高版本的gdb,而Red Hat 9.0自带的gdb版本过低.)

推荐的 pascal: fr

第一题：最大字符（zdzf.c/cpp）

读入一串由大写、小写、数字组成的字符(<256位)，输出ASCII表值最大的那个字符出来。 例如：读入：

abeADEf3 输出：e

第二题：盖房子（gfz.c/cpp） 题目正文 【问题描述】

永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。

但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。 他希望找到一块最大的正方形无瑕疵土地来盖房子。 【输入格式】

输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。 【输出格式】

一个整数，最大正方形的边长。 【输入样例】 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 【输出样例】 2

第三题：IQ（iq.c/cpp） 题目正文 【问题描述】

根据世界某权威学会的一项调查，学信息学的学生IQ非常高。举个最好的例子，如果我们把学信息学的一些学生调去学数学，那么两个竞赛的学生平均IQ都会提升！！

现在给出一群数学竞赛全体学生的IQ和信息学竞赛全体学生IQ,问最多能把几个学信息学的学生调去学数学，而两个竞赛的学生平均I

信息学奥赛选择题

一、计算机组成与工作原理

1．下列不属于冯·诺依曼计算机模型的核心思想是（D）。 A采用二进制形式表示数据和指令； B采用“存储程序”工作方式；

C计算机硬件由五大部件（运算器，控制器，存储器，输入和输出设备）组成； D结构化程序设计方法

2.计算机的基本硬件结构一直是沿袭（B ）设计的框架。 A. 比尔·盖茨 B.冯·诺依曼 C.布尔 D.图灵 3.计算机能够自动工作，主要是因为采用了（C）。

A.二进制数制 B.高速电子元件 C.存储程序控制 D.程序设计语言 4．mips是衡量CPU处理速度的一种常用指标，它的含义是（B）。 A每秒钟平均可执行的单字长定点指令的数目 B每秒钟平均可执行指令的数目

C每秒钟平均可执行的浮点指令的数目 D每秒钟平均可执行的算术运算指令的数目 5.微型计算机的性能主要取决于（ B）

A内存 B 中央处理器 C 硬盘 D 显示器 计算机处理信息的精度决定于（D ）。

A.CPU的主频 B.硬盘的容量 C.系统总线的传输速率 D.CPU字长

6.中央处理器的英文缩写是CPU,它是计算机的核心部分,一台计算机的性能很大程度上

DP Problem Set

顺序对齐

源程序名 ALIGN.??? (PAS,C,CPP) 可执行文件名 ALIGN.EXE 输入文件名 ALIGN.IN 输出文件名 ALIGN.OUT

考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。

AAD_DEFGGHC ADCDE__GH_

每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。

请你写个程序找出最佳右对齐方案。 输入

输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。 输出

一行，为最佳对齐的得分。 样例 ALIGN.IN

AADDEFGGHC ADCDEGH

ALIGN.OUT 9

_______________________________________________________________________________

第二十届全国青少年信息学奥林匹克联赛初赛

普及组pascal语言试题

1、以下哪个是面向对象的高级语言（） Ａ.汇编语言Ｂ.Ｃ++ Ｃ.Fortran D.Basic 2、1ＴＢ代表的字节数量是（）

Ａ.2的10次方 Ｂ.2的20次方 Ｃ. .2的30次方 Ｄ. .2的40次方 3、二进制数00100100和00010101的和是（） Ａ.00101000 Ｂ.001010100 Ｃ.01000101 Ｄ.00111001 4、以下哪一种设备属于输出设备 Ａ.扫描仪 B.键盘 Ｃ.鼠标 Ｄ．打印机 5、下列对操作系统功能的描述最为完整的是（） Ａ.负责外设与主机之间的信息交换 B.负责诊断机器的故障

C．控制和管理计算机系统的各种硬件和软件资源的使用 D.将源程序编译成目标程序

6、CPU、存储器、Ｉ/O设备是通过（）连接起来的 A.接口 Ｂ.总线 Ｃ.控制线 Ｄ.系统文件

7、断电后会丢失数据的存储器是（） Ａ.ＲＡＭ Ｂ.ＲＯＭ C.硬盘 Ｄ.光盘 8、以下哪一种是属于电子邮件收发的协议（） Ａ.ＳＭＴＰ Ｂ.ＵＤＰ C.Ｐ2Ｐ Ｄ.ＦＴＰ 9、下列选项中不属于图像格式的是（）

Ａ.JPEG格式 Ｂ.TXT格式 Ｃ.ＧＩＦ格式 Ｄ.ＰＮＧ

江苏省金湖中学08、09、10级 信息学奥赛组NOIP2010初赛模拟练习(三)

1、下面一段程序是用（ ）语言书写的。 int func1(int n){ int i,sum=0; for(i=1;i<=n;i++) sum+=i*i; return sum; }

A) FORTRAN B) PASCAL C) C D) PROLOG E) BASIC 2、多媒体计算机是指( ) 计算机。 A)专供家庭使用的 B)装有CD-ROM的

B)连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的

3、在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是( ) 。 A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置 B)文本框中的图形不可以衬于文档中输入的文字的下方。

C) 通过文本框,可以实现图形和文档中输入的文字的叠加,也可实现文字环绕。 D) 将图形放入文本框后,文档中输入的文字不能环绕图形。 4、计算机软件保护法是用来保护软件( )的。 A)编写权 B)复制权

NOIP 2010试题与解题报告

NOIP 2010初赛试题

（ 普及组 C语言 两小时完成 ）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．2E+03表示（ ）。

A. 2.03 B. 5 C. 8 D. 2000

2．一个字节（byte）由（ ）个二进制位组成。

A. 8 B. 16 C. 32 D. 以上都有可能

3．以下逻辑表达式的值恒为真的是（ ）。

A. P∨(¬P∧Q)∨(¬P∧¬Q) B. Q∨(¬P∧Q)∨(P∧¬Q) C. P∨Q∨(P∧¬Q)∨(¬P∧Q) D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)

4．Linux下可执行文件的默认扩展名为（ ）。

A. exe B. com C. d

noip1995普复赛试题

1 NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛

分区联赛复赛试题（初中组）

（上机编程，完成时间：210分钟）

<1> 设有下列的算式：

8 0 9

-------------

□□) □□□□

□□

-------------

□□□

□□□

-------------

1

求出□中的数字，并打印出完整的算式来。

<2> 方阵填数：在一个N ?N 的方阵中，填入1，2，……N ?N 个数，并要求构成如下的格式：

例：

<3> 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A 类数，否则就称其为B 类数。

例如：（13）10=（1101）2

其中1的个数为3，0的个数为1，则称此数为A 类数；

（10）10=（1010）2

其中1的个数为2，0的个数也为2，称此数为B 类数；

（24）10=（11000）2

其中1的个数为2，0的个数为3，则称此数为B 类数；

程序要求：求出1～1000之中（包括1与1000），全部A 、B 两类数的个数。

<4> 编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER ；数组中存放的元素为0～N-1之间

题目来源：金陵中学2005-2006年第二学期信息学奥林匹克竞赛训练题

金华一中信息学奥林匹克联赛（NOIP2009）复赛模拟试题（一）

一、题目概览 中文题目名称 英文题目名称 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 二、运行内存限制 运行内存上限 32MB 32MB 512MB 512MB 八数码 puzzle puzzle.in puzzle.out 3秒 10 10 全文比较 清扫仓库 clean clean.in clean.out 1秒 10 10 全文比较 数列 sequence sequence.in 1秒 10 10 全文比较 试题安排 arrange arrange.in 1秒 10 10 全文比较 sequence.out arrange.out

第1题 八数码

- 问题描述

大家都熟悉得不能再熟悉的八数码问题：给定一个初始状态 1 2 3 4 5 6 7 8 0

每次可以把0和与它相邻的数字交换，问最少需要多少步，可以转换到目标状态。 - 输入数据

三行三个整数，分别表示了目标状态。

- 输出数据

假如无法从初始状态到目标状态，输出一行\不含引号)，否则输出最少需要的步数。