nbhkdz.com冰点文库

NOI2015


第 32 届全国信息学奥林匹克竞赛

CCF NOI 2015
第一试
竞赛时间:2015 年 7 月 17 日 8:00-13:00
题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型 是否有附加文件 程序自动分析 prog prog prog.in

prog.out 2秒 512MB 10 10 否 传统型 是 软件包管理器 manager manager manager.in manager.out 1秒 512MB 20 5 否 传统型 是 寿司晚宴 dinner dinner dinner.in dinner.out 1秒 512MB 10 10 否 传统型 否

提交源程序须加后缀 对于 Pascal 语言 prog.pas 对于 C 语言 prog.c 对于 C++ 语言 prog.cpp

manager.pas manager.c manager.cpp

dinner.pas dinner.c dinner.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关。

第 32 届全国信息学奥林匹克竞赛

第一试 程序自动分析

程序自动分析
【问题描述】 在实现程序自动分析的过程中, 常常需要判定一些约束条件是否能被同时满 足。 考虑一个约束满足问题的简化版本:假设 1 , 2 , 3 , ? 代表程序中出现的变 量,给定 个形如 = 或 ≠ 的变量相等/不等的约束条件,请判定是否 可以分别为每一个变量赋予恰当的值, 使得上述所有约束条件同时被满足。 例如, 一个问题中的约束条件为: 1 = 2 , 2 = 3 , 3 = 4 , 1 ≠ 4 ,这些约束条件显 然是不可能同时被满足的,因此这个问题应判定为不可被满足。 现在给出一些约束满足问题,请分别对它们进行判定。 【输入格式】 从文件 prog.in 中读入数据。 输入文件的第 1 行包含 1 个正整数 ,表示需要判定的问题个数。注意这些 问题之间是相互独立的。 对于每个问题,包含若干行: 第 1 行包含 1 个正整数 ,表示该问题中需要被满足的约束条件个数。 接下来 行,每行包括 3 个整数 , , ,描述 1 个相等/不等的约束条件,相 邻整数之间用单个空格隔开。若 = 1 ,则该约束条件为 = ;若 = 0 , 则该约束条件为 ≠ ; 【输出格式】 输出到文件 prog.out 中。 输出文件包括 行。 输出文件的第 行输出一个字符串“YES”或者“NO” (不包含引号,字母 全部大写) , “YES”表示输入中的第 个问题判定为可以被满足, “NO”表示不 可被满足。 【样例输入 1】 2 2 1 1 2 1 2

2 1 2 0 2 1 1 1

第2页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 程序自动分析

【样例输出 1】 NO YES 【样例说明 1】 在第一个问题中,约束条件为: 1 = 2 , 1 ≠ 2 。这两个约束条件互相矛 盾,因此不可被同时满足。 在第二个问题中,约束条件为: 1 = 2 , 2 = 1 。这两个约束条件是等价 的,可以被同时满足。 【样例输入 2】 2 3 1 2 3 4 1 2 3 1

2 1 3 1 1 1 2 3 4 4 1 1 1 0

【样例输出 2】 YES NO 【样例说明 2】 在第一个问题中,约束条件有三个: 1 = 2 , 2 = 3 , 3 = 1 。只需赋值使 得 1 = 2 = 3 ,即可同时满足所有的约束条件。 在第二个问题中,约束条件有四个: 1 = 2 , 2 = 3 , 3 = 4 , 1 ≠ 4 。由 前三个约束条件可以推出 1 = 2 = 3 = 4 ,然而最后一个约束条件却要求 1 ≠ 4 ,因此不可被满足。 【样例输入输出 3】 见选手目录下的 prog/prog.in 与 prog/prog.ans。

第3页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 程序自动分析

【数据规模与约定】 所有测试数据的范围和特点如下表所示 测试点编号 的规模 , 的规模 1 1 ≤ ≤ 10 2 3 1 ≤ ≤ 100 4 1 ≤ , ≤ 10,000 5 6 1 ≤ ≤ 100,000 7 8 9 1 ≤ ≤ 100,000 1 ≤ , ≤ 1,000,000,000 10

约定

1 ≤ ≤ 10 ∈ {0,1}

第4页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 软件包管理器

软件包管理器
【问题描述】 Linux 用户和 OS X 用户一定对软件包管理器不会陌生。 通过软件包管理器, 你可以通过一行命令安装某一个软件包, 然后软件包管理器会帮助你从软件源下 载软件包, 同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其 它软件包) ,完成所有的配置。Debian/Ubuntu 使用的 apt-get,Fedora/CentOS 使 用的 yum,以及 OS X 下可用的 homebrew 都是优秀的软件包管理器。 你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依 赖问题。如果软件包 依赖软件包 ,那么安装软件包 以前,必须先安装软 件包 。同时,如果想要卸载软件包 ,则必须卸载软件包 。现在你已经获 得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除 0 号软件包以 外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而 0 号软件包不 依 赖 任 何 一 个 软 件 包 。 依 赖 关 系 不 存 在 环 ( 若 有 ( ≥ 2) 个 软 件 包 1 , 2 , 3 , ? , ,其中 1 依赖 2 , 2 依赖 3 , 3 依赖 4 ,……, ?1 依 赖 ,而 依赖 1 ,则称这 个软件包的依赖关系构成环) ,当然也不会有 一个软件包依赖自己。 现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在 安装和卸载某个软件包时, 快速地知道这个操作实际上会改变多少个软件包的安 装状态 (即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已 安装的软件包) , 你的任务就是实现这个部分。 注意, 安装一个已安装的软件包, 或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况 下,改变安装状态的软件包数为 0。 【输入格式】 从文件 manager.in 中读入数据。 输入文件的第 1 行包含 1 个整数 ,表示软件包的总数。软件包从 0 开始编 号。 随后一行包含 ? 1 个整数,相邻整数之间用单个空格隔开,分别表示 1, 2, 3, ? , ? 2, ? 1 号软件包依赖的软件包的编号。 接下来一行包含 1 个整数 ,表示询问的总数。 之后 行,每行 1 个询问。询问分为两种: ? ? install x:表示安装软件包 uninstall x:表示卸载软件包

你需要维护每个软件包的安装状态, 一开始所有的软件包都处于未安装状态。 对于每个操作, 你需要输出这步操作会改变多少个软件包的安装状态,随后应用 这个操作(即改变你维护的安装状态) 。

第5页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 软件包管理器

【输出格式】 输出到文件 manager.out 中。 输出文件包括 行。 输出文件的第 行输出 1 个整数, 为第 步操作中改变安装状态的软件包数。 【样例输入 1】 7 0 0 0 1 1 5 5 install 5 install 6 uninstall 1 install 4 uninstall 0 【样例输出 1】 3 1 3 2 3 【样例说明 1】 0

1

2

3

4

5

6 一开始所有的软件包都处于未安装状态。 安装 5 号软件包,需要安装 0, 1, 5 三个软件包。 之后安装 6 号软件包,只需要安装 6 号软件包。此时安装了 0, 1, 5, 6 四个软 件包。 卸载 1 号软件包需要卸载 1, 5, 6 三个软件包。 此时只有 0 号软件包还处于安 装状态。
第6页 共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 软件包管理器

之后安装 4 号软件包, 需要安装 1, 4 两个软件包。 此时 0, 1, 4 处在安装状态。 最后,卸载 0 号软件包会卸载所有的软件包。 【样例输入 2】 10 0 1 2 1 3 0 0 3 2 10 install 0 install 3 uninstall 2 install 7 install 5 install 9 uninstall 9 install 4 install 1 install 9 【样例输出 2】 1 3 2 1 3 1 1 1 0 1 【样例输入输出 3】 见选手目录下的 manager/manager.in 与 manager/manager.ans。

第7页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 软件包管理器

【数据规模与约定】 测试点编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 的规模 = 5,000 = 100,000 的规模 = 5,000 = 100,000 数据不包含卸载操作 编号为 的软件包所依赖的软件包编 号在 [0, ? 1] 内均匀随机 每次执行操作的软件包编号在 [0, ? 1] 内均匀随机 备注

= 100,000

= 100,000

= 100,000

= 100,000

第8页

共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 寿司晚宴

寿司晚宴
【问题描述】 为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。 在晚宴上, 主办方为大家提供了 ? 1 种不同的寿司, 编号 1, 2, 3, ? , ? 1 , 其中第 种寿司的美味度为 + 1 (即寿司的美味度为从 2 到 n ) 。 现在小 G 和小 W 希望每人选一些寿司种类来品尝,他们规定一种品尝方案 为不和谐的当且仅当:小 G 品尝的寿司种类中存在一种美味度为 的寿司,小 W 品尝的寿司中存在一种美味度为 的寿司,而 与 不互质。 现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案(对给定的 正整数 取模) 。注意一个人可以不吃任何寿司。 【输入格式】 从文件 dinner.in 中读入数据。 输入文件的第 1 行包含 2 个正整数 , ,中间用单个空格隔开,表示共有 种寿司,最终和谐的方案数要对 取模。 【输出格式】 输出到文件 dinner.out 中。 输出一行包含 1 个整数,表示所求的方案模 p 的结果。 【样例输入 1】 3 10000 【样例输出 1】 9 【样例说明 1】 设小 G 选择的寿司的美味度值构成集合 A,小 W 选择的寿司的美味度值构 成集合 B,则有以下 9 种方案: (用{2,3}表示选择美味度为 2 和 3 的两种寿司, {}表示不选择寿司, 等等。 ) = {}, = {} = {}, = {2} = {}, = {3} = {}, = {2,3} = {2}, = {}
第9页 共 10 页

第 32 届全国信息学奥林匹克竞赛

第一试 寿司晚宴

= {2}, = {3} = {3}, = {} = {3}, = {2} = {2,3}, = {} 因此应输出 9。 【样例输入 2】 4 10000 【样例输出 2】 21 【样例输入 3】 100 100000000 【样例输出 3】 3107203 【数据规模与约定】 测试点编号 1 2 3 4 5 6 7 8 9 10 的规模 2 ≤ ≤ 30 2 ≤ ≤ 100 0 < p ≤ 1,000,000,000 2 ≤ ≤ 200 2 ≤ ≤ 500 约定

第 10 页 共 10 页


NOI_2015获奖名单

CCF NOI2015 获奖名单金牌姓名 吴作凡 金策 袁宇韬 汪文潇 吉如一 张若天 张志俊 李昊 邹逍遥 赵晟宇 王梦迪 姜志豪 王天懿 省份 安徽 浙江 湖南 福建 ...

2015noip第二十一届普及组初赛试题

2015noip第二十一届普及组初赛试题_学科竞赛_高中教育_教育专区。第二十一届...O(nIogn) C.O(n) D.O(n2) 20.在 NOI 系列赛事中参赛选手必须使用由...

NOIP2015提高组复赛试题Day1

全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克...5、特别提醒:评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版 本以...

2015noi小学组初赛试题

2015noi小学组初赛试题_学科竞赛_小学教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 一、单项选择题(共 20 题,每题 1.5 分...

NOIP2015提高组一等奖

NOIP2015提高组一等奖_计算机软件及应用_IT/计算机_专业资料。NOIP2015提高组复赛一等奖名单 CCF NOIP2015 复赛提高组一等奖获奖名单证书编号 CCF-NOIP2015-0001 CCF-...

2016.10.1 学习整理

(NOI2015 NOI 就是 NOI 不可小觑~~~ #include<iostream> #include<cstdio> #include<cstring> #define N 1000010 using namespace std; int n,t,f[N]; in...

2015“清华大学拔尖创新人才选拔营”之信息学夏令营0515(发布)

2015“清华大学拔尖创新人才选拔营”之信息学夏令营0515(发布)_营销/活动策划_...CTSC2015、APIO2015 的 成绩,已入选 NOI2015 的 A 类、B 类或 C 类的选手...

2015年高校自主招生报名条件一览表

E、信息学类:符合 2015 年高考报名要求,在 2014 年全国青少年信息学奥林匹克竞赛(简称 NOI2014)中 获奖(或 D 类选手超过铜牌分数线)的高中理科毕业生。 Ⅲ....

NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组...其实三个极限的点所花时间都差不多,我想 NOI 机子应该 也不会慢到 300ms ...

NOIP2015普及组初赛试题及答案(Pascal)

NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一...在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许...