当前位置:首页 >> 学科竞赛 >> NOI2013河北省选第一试

NOI2013河北省选第一试


NOI2013 河北省队选拔赛
第一试

题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型

Eden 的新背包问题 bag bag bag.in bag.out 2秒 256 MB 20 5 无 传统型

Eden 的博弈树 g

ametree gametree gametree.in gametree.out 1秒 256 MB 20 5 无 传统型

Segment segment segment segment.in segment.out 8 秒 256 MB 10 10 无 传统型

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

gametree.cpp gametree.c gametree.pas

segment.cpp segment.c segment.pas

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

NOI2013 河北省队选拔赛 第一试

Eden 的新背包问题

Eden 的新背包问题
【问题描述】

“寄没有地址的信, 这样的情绪有种距离, 你放着谁的歌曲, 是怎样的心情。 能不能说给我听。 ”
失忆的 Eden 总想努力地回忆起过去,然而总是只能清晰地记得那种思念的 感觉,却不能回忆起她的音容笑貌。 记忆中,她总是喜欢给 Eden 出谜题:在 valentine’s day 的夜晚,两人在闹市 中闲逛时,望着礼品店里精巧玲珑的各式玩偶,她突发奇想,问了 Eden 这样的 一个问题:有 n 个玩偶,每个玩偶有对应的价值、价钱,每个玩偶都可以被买有 限次,在携带的价钱 m 固定的情况下,如何选择买哪些玩偶以及每个玩偶买多 少个,才能使得选择的玩偶总价钱不超过 m,且价值和最大。 众所周知的, 这是一个很经典的多重背包问题, Eden 很快解决了, 不过她似 乎因为自己的问题被飞快解决感到了一丝不高兴,于是她希望把问题加难:多次 询问,每次询问都将给出新的总价钱,并且会去掉某个玩偶(即这个玩偶不能被 选择) ,再问此时的多重背包的答案(即前一段所叙述的问题) 。 这下 Eden 犯难了,不过 Eden 不希望自己被难住,你能帮帮他么? 【输入格式】 从文件 bag.in 看读入数据。 第一行一个数 n,表示有 n 个玩偶,玩偶从 0 开始编号 第二行开始后面的 n 行,每行三个数 ai, bi, ci,分别表示买一个第 i 个玩偶需 要的价钱,获得的价值以及第 i 个玩偶的限购次数。 接下来的一行为 q,表示询问次数。 接下来 q 行,每行两个数 di, ei 表示每个询问去掉的是哪个玩偶(注意玩偶 从 0 开始编号)以及该询问对应的新的总价钱数。 (去掉操作不保留,即不同询 问互相独立) 【输出格式】 输出到文件 bag.out 中。 输出 q 行,第 i 行输出对于第 i 个询问的答案。 【样例输入】 5 2 1 4 2 3 5 1

3 2 1 1 2 10

4 1 2 1 3

第2页

共7页

NOI2013 河北省队选拔赛 第一试

Eden 的新背包问题

2 3 4 0

7 4 8 5

【样例输出】 13 11 6 12 4 【样例说明】 一共五种玩偶, 分别的价钱价值和限购次数为(2,3,4), (1,2,1), (4,1,2), (2,1,1), (3,2,3)。 五个询问,以第一个询问为例。第一个询问表示的是去掉编号为 1 的玩偶, 且拥有的钱数为 10 时可以获得的最大价值,则此时剩余玩偶为(2,3,4),(4,1,2), (2,1,1),(3,2,3),若把编号为 0 的玩偶买 4 个(即全买了) ,然后编号为 3 的玩偶 买一个, 则刚好把 10 元全部花完, 且总价值为 13。 可以证明没有更优的方案了。 注意买某种玩偶不一定要买光。 【数据规模与约定】 10%数据满足 1 ≤ n ≤ 10; 另 20%数据满足 1 ≤ n ≤ 100, ci = 1, 1 ≤ q ≤ 100; 另 20%数据满足 1 ≤ n ≤ 100, 1 ≤ q ≤ 100; 另 30%数据满足 ci = 1; 100%数据满足 1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105, 1 ≤ ai、bi、ci ≤ 100, 0 ≤ di < n, 0 ≤ ei ≤ 1000。

第3页

共7页

NOI2013 河北省队选拔赛 第一试

Eden 的博弈树

Eden 的博弈树
【问题描述】 对于有两个玩家的, 状态透明且状态转移确定的博弈游戏,博弈树是常用的 分析工具。博弈树是一棵有根树,其中的节点为游戏的状态。若节点 B 的父亲是 A,则说明状态 A 能通过一次决策转移到状态 B。每个状态都有一个唯一的决策 方, 即这个状态下应该由哪一方做出决策。我们规定双方在任何时候都是轮流做 出决策的,即树上相邻节点的决策方总是不相同的。 在这个问题中, 我们只关心两个玩家的胜负情况, 且规定游戏不会出现平局。 我们称两个玩家分别为黑方和白方,其中根节点的决策方为黑方。显然每个节点 只有两个状态:黑方胜和白方胜。若某内节点(即存在后继节点的节点)的决策 方为黑方, 则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点,反之 亦然。求解博弈树即为判明博弈树根节点的状态。 如果我们得知了所有叶节点(即无后继节点的节点)的状态,那么博弈树就 很容易求解了。 但是现在的情况是所有叶节点的状态均为未知的,需要进一步的 计算。对于一个由叶节点构成的集合 S,如果 S 中的节点均被判明为黑方胜,就 可以断言根节点为黑方胜的话,则称 S 为一个黑方胜集合。对于黑方胜集合 S, 如果对于任意的黑方胜集合 S’ 均满足|S| ≤ |S’ |(|S|表示集合 S 中的元素数目) , 则称 S 为一个最小黑方胜集合。 同样地,也可以定义白方胜集合和最小白方胜集 合。 Eden 最近在研究博弈树问题。他发现,如果一个叶节点既属于某一个最小 黑方胜集合, 又属于一个最小白方胜集合,那么求解这个节点的状态显然最有益 于求解根节点的状态。 像这样的叶节点就称之为关键叶节点。对于一棵给定的博 弈树,Eden 想要知道哪些叶节点是关键叶节点。 【输入格式】 从文件 gametree.in 中读入数据。 每个测试点包含一组测试数据。 测试数据的第一行包含一个正整数 n,表示博弈树的节点数目。节点从 1 到 n 编号,且 1 号节点为根节点。 之后 n – 1 行, 每行包含一个正整数。 i 行的正整数表示节点 i 的父节点 第 的编号。 【输出格式】 输出到文件 gametree.out 中。 在一行内输出三个空格分隔的正整数, 分别是编号最小的关键叶节点的编号, 关键叶节点的数目和所有关键叶节点的编号的异或和。 【样例输入】 7 1
第4页 共7页

NOI2013 河北省队选拔赛 第一试

Eden 的博弈树

1 2 2 3 3 【样例输出】 4 4 0 【样例说明】

如图所示,黑色节点表示决策方为黑方的节点,反之亦然。 所有的最小黑方胜集合为{4, 5}和{6, 7}。 所有的最小白方胜集合为{4, 6},{4, 7},{5, 6}和{5, 7}。 所以关键叶节点的集合为{4, 5, 6, 7}。 【数据规模与约定】 对于 30% 的数据,n ≤ 100; 对于 40% 的数据,n ≤ 1,000; 对于 50% 的数据,n ≤ 10,000,且树是随机生成的; 对于 100% 的数据,1 ≤ n ≤ 200,000,且对于节点 i(i ≠ 1) ,其父节点的编 号小于 i。

第5页

共7页

NOI2013 河北省队选拔赛 第一试

Segment

Segment
【问题描述】 要求在平面直角坐标系下维护两个操作: 1. 在平面上加入一条线段。记第 i 条被插入的线段的标号为 i。 2. 给定一个数 k,询问与直线 x = k 相交的线段中, 交点最靠上的线段的编号。 【输入格式】 从文件 segment.in 中读入数据。 第一行一个整数 n,表示共 n 个操作。 接下来 n 行,每行第一个数为 0 或 1。 若该数为 0,则后面跟着一个正整数 k,表示询问与直线 x = ((k + lastans – 1)%39989+1)相交的线段中交点(包括在端点相交的情形)最靠 上的线段的编号,其中%表示取余。若某条线段为直线的一部分,则视作直线与 线段交于该线段 y 坐标最大处。若有多条线段符合要求,输出编号最小的线段的 编号。 若该数为 1,则后面跟着四个正整数 x0, y0, x1, y1,表示插入一条两个端点为 ((x0+lastans-1)%39989+1,(y0+lastans-1)%109+1)和 ((x1+lastans-1)%39989+1,(y1+lastans-1)%109+1) 的线段。 其中 lastans 为上一次询问的答案。初始时 lastans=0。 【输出格式】 输出到文件 segment.out 中。 对于每个 0 操作,输出一行,包含一个正整数,表示交点最靠上的线段的编 号。若不存在与直线相交的线段,答案为 0。 【输入样例】 6 1 1 0 0 1 0

8 5 10 8 6 7 2 6 2 9 4 7 6 7 5

【输出样例】 2 0 3

第6页

共7页

NOI2013 河北省队选拔赛 第一试

Segment

【数据规模】 对于 30%的数据,n ≤ 1000 对于 100%的数据,1 ≤ n ≤ 105, 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 109。

第7页

共7页


更多相关文档:

河北省石家庄市2013届高三第一次模拟考试语文试题

河北省石家庄市 2013 届高三第一次模拟考试语 文试题 河北石家庄市 2013 届高中毕业班第一次模拟考试 语文试题 第卷(阅读题,共 70 分) 甲 必考题(45 分) ...

河北省邯郸市2013年高三第一次模拟考试

河北省邯郸市2013年高三第一次模拟考试 理科数学 2013.3 本试卷分第I卷(选择题)和第II卷(非选择题)两部分,其中第II卷第22题-24题为选 考题,其他题为必...

2013-2014河北省邯郸市高三第一次模拟试卷

试试 3 帮助 全部 DOC PPT TXT PDF XLS ...2013-2014河北省邯郸市高三第一次模拟试卷_从业资格...可是她 不假思索地放弃了,选择了诚信和善良,再次让...

河北省邯郸市2013年高三第一次模拟考试语文试卷

试​卷河北省邯郸市 2013 年高三第一次模拟考试语文试卷 2013.3 第Ⅰ卷 阅读题(共 70 分) 甲 必考题 一、现代文阅读(9 分,每小题 3 分) 阅读下面的...

河北省石家庄市2013届高中毕业班第一次模拟考试(word版)理综

试试 7 帮助 全部 DOC PPT TXT PDF XLS ...河北省石家庄市2013届高中毕业班第一次模拟考试(word...试卷分第 I 卷(选择题)和第 II 卷(非选择题)...

河北省邯郸市2013届高三第一次模拟考试理综试题 Word版含答案

河北省邯郸市2013届高三第一次模拟考试理综试题 Word...2013.03 本试卷分第 I 卷(选择题)和第 II 卷(...酸式滴定管在盛装标准溶液前没有用标准溶液润洗,测...

河北省唐山市2013届高三第一次模拟考试语文

试试 7 帮助 全部 DOC PPT TXT PDF XLS ...河北省唐山市2013届高三第一次模拟考试语文_语文_高中...乙选考题 请考生在第三、四两大题中选定其中一大...

2013届高考语文模拟试卷及参考答案河北省衡水中学2013届高三第一次调研考试(语文)

河北衡水中学2013届高三... 12页 3下载券喜欢...三​第​一​次​调​研​考​试​...一、文言文阅读(选择每个 2 分) (一) 、阅读...

2013希望杯七年级第一试

2​0​1​3​希​望​杯​七​年​级​第​一​试第二十四届“希望杯”全国数学邀请赛初一 2013 年 3 月 17 日一、选择题(每小题 ...

河北省保定市2013年高三第一次模拟考试语文

试试 帮助 全部 DOC PPT TXT PDF XLS ...河北省保定市 2013 年高三第一次模拟考试 语文试题...注意:作答时必须 用 2B 铅笔在答题卡上把所选大...
更多相关标签:
2013河北省公务员考试 | noi2013 | noi2013快餐店 | noi2013 day1 | noi2013树的计数 | noi2013矩阵游戏 | noi2013向量内积 | noi笔试 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com