noi和noip

1 Webb.S 一、（搜索）双向广度搜索

广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。

范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。 问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。 对广度搜索算法的改进：

１。添加一张节点表，作为反向扩展表。

２。在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。

３。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时 与之相同。

对双向广度搜索算法的改进：

略微修改一下控制结构，每次while循环时只扩展正反两个方向

NOI竞赛规则

为保证NOI竞赛的科学性和公正性，保证竞赛环境的一致性和稳定性，并为竞赛的承办单位规范化组织竞赛提供实施标准的指导，特制订本规则。 竞赛环境 场地

全体参赛选手分布在不超过4个相距30米之内的竞赛场地。每位参赛选手拥有面积不小于1.5M2的工作场地和正面面宽不小于0.8M的工作台，独立使用一台配备有规定的操作系统和编程工具的计算机。

竞赛组织者将在竞赛场地为选手提供草稿纸、饮水、以及必要的食品。 设备

选手竞赛用机的配置不低于下列指标：

CPU Intel 赛扬866 或相同及更高指标的其它类型CPU 内存 256MB

硬盘 10GB，其中选手可用空间不小于0.5GB。 网卡 100M 显示器 15”

键盘 标准英文输入键盘 鼠标 标准双键鼠标

选手竞赛用机上配备下列软件系统：

操作系统：Linux，内核版本：2.4 桌面系统：GNOME/KDE; 浏览器：Firefox, Konqueror

编辑工具：mcedit, vim, kate, kwrite, kdevelop, rhide 编译系统: gcc ≥3.2.2, g++ ≥3.2.2, Free Pascal ≥2.0.1 调试工具: gdb, ddd

上述软件

noi2

1、 航空管制

【问题描述】

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。对此，小X表示很不满意。 在这次来烟台的路上，小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。假设目前被延误航班共有n个，编号为1至n。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。起飞序列还存在两类限制条件：

第一类（最晚起飞时间限制）：编号为i的航班起飞序号不得超过ki; 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班a的起飞时间必须早于航班b，即航班a的起飞序号必须小于航班b的起飞序号。

小X思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

【输入格式】

输入文件plane.in第一行包含两个正整数n和m，n表示航班数目，m表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含n个正整数k1, k2, …

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

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 姓名 毛啸 洪华敦 袁宇韬 罗哲正 徐明宽 丁力煌 周子鑫 吴作凡 闫书弈 钟知闲 杨景钦 徐泽涛 袁伟强 谢兴宇 叶昊星 省份 湖南 浙江 湖南 安徽 北京 江苏 浙江 安徽 福建 福建 四川 浙江 江苏 山东 浙江 性学校(全称) 别 男 长沙市雅礼中学 男 绍兴市第一中学 男 长沙市雅礼中学 男 安徽师范大学附属中学 男 北京师范大学附属实验中学 男 南京外国语学校 男 浙江省杭州学军中学 男 安徽师范大学附属中学 男 福建省福州第三中学 男 福建省福州第一中学 男 四川省成都市第七中学 男 浙江省余姚中学 男 南京师范大学附属中学 男 东营市胜利第一中学 男 杭州市

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 姓名 毛啸 洪华敦 袁宇韬 罗哲正 徐明宽 丁力煌 周子鑫 吴作凡 闫书弈 钟知闲 杨景钦 徐泽涛 袁伟强 谢兴宇 叶昊星 省份 湖南 浙江 湖南 安徽 北京 江苏 浙江 安徽 福建 福建 四川 浙江 江苏 山东 浙江 性学校(全称) 别 男 长沙市雅礼中学 男 绍兴市第一中学 男 长沙市雅礼中学 男 安徽师范大学附属中学 男 北京师范大学附属实验中学 男 南京外国语学校 男 浙江省杭州学军中学 男 安徽师范大学附属中学 男 福建省福州第三中学 男 福建省福州第一中学 男 四川省成都市第七中学 男 浙江省余姚中学 男 南京师范大学附属中学 男 东营市胜利第一中学 男 杭州市

第一题：最大字符（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

算法总结

一、 动态规划和递推

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

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

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

二、 图论及网络流

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

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

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

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

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

信息学奥赛选择题

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

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

_______________________________________________________________________________