当前位置:首页 >> 学科竞赛 >>

清北学堂2013NOI模拟1


NOI 模拟试题
题目 文件名 时间限制 空间限制 分数分布 最小序列 Sequence 2s 32MB 10 * 10 剪刀石头布 jsb 3s 32MB 10 * 10 图书馆 library 0.1s 32MB 2*8+7*12

最小序列

题目描述
一个包含n个数的序列A(所有的数各不相等),首先定义一个B:

Bi = max{Bj} + 1 {Aj < Ai, j < i} 然后,对于任意序列,若它满足以下条件,我们则称之为K号序列: 1. 该序列长度为K,并且是A的子序列。 2. 该序列在A中对应的B值为连续自然数。 3. 该序列在所有满足条件1,2的序列中字典序最小。 举个例子: 序列A: 2 6 7 3 4 5 1 B值: 1 2 3 2 3 4 1 长度为3且满足条件1,2的序列有{2,6,7}和{2,3,4}和{3,4,5},但{2,3,4} 字典序最小,因此3号序列为{2,3,4}。

Your Task
给你一个长度为N的序列及其对应的B值,再给你M个形如{i,j}的询问,要你求出i号 序列与j号序列的最长公共子序列的长度。

输入文件
第一行 N M 分别为序列长度,询问个数 第二行 N个数描述序列A 第三行 N个数描述对应的B值 接下来M行每行一个询问 i j

输出文件
M行,每行一个数对应一个询问的答案。

样例输入
2 1 3 3 7 2 6 7 3 4 5 1 2 3 2 3 4 1 4 1

样例输出
3 0

数据约定
10%的数据中,N ,M≤ 10; 20%的数据中,N ,M≤ 1000; 100%的数据中,N ,M≤ 500000; 保证询问合法,即 1 <= i, j <= max{B}。

剪刀石头布

题目描述
在一些一对一游戏的比赛(如下棋、乒乓球和羽毛球的单打)中,我们经常会遇到 A 胜过 B,B 胜过 C 而 C 又胜过 A 的有趣情况,不妨形象的称之为剪刀石头布情况。有的时 候,无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生,即有多少对无序三 元组(A, B, C),满足其中的一个人在比赛中赢了另一个人,另一个人赢了第三个人而第三 个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要,将(A, B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B, A)视为相同的情况。 有 N 个人参加一场这样的游戏的比赛,赛程规定任意两个人之间都要进行一场比赛: 这样总共有
N ( N ?1) 场比赛。比赛已经进行了一部分,我们想知道在极端情况下,比赛结 2

束后最多会发生多少剪刀石头布情况。

Your Task
给出已经发生的比赛结果,你可以任意安排剩下的比赛的结果,要求得到尽量多的 剪刀石头布情况。

输入文件
输入文件的第 1 行是一个整数 N,表示参加比赛的人数。 之后是一个 N 行 N 列的数字矩阵:一共 N 行,每行 N 列,数字间用空格隔开。 在第(i+1)行的第 j 列的数字如果是 1,则表示 i 在已经发生的比赛中赢了 j;该数字若 是 0,则表示在已经发生的比赛中 i 败于 j;该数字是 2,表示 i 和 j 之间的比赛尚未发生。 数字矩阵对角线上的数字,即第(i+1)行第 i 列的数字都是 0,它们仅仅是占位符号,没有任 何意义。 输入文件保证合法,不会发生矛盾,当 i≠j 时,第(i+1)行第 j 列和第(j+1)行第 i 列的 两个数字要么都是 2,要么一个是 0 一个是 1。

输出文件
一个数字表示在你安排的比赛中,出现了多少剪刀石头布情况。

样例输入
3 012 002 220

样例输出
1

数据约定
30%的数据中,N ≤ 6; 100%的数据中,N ≤ 100。

图书馆
题目描述
鲁滨逊决定做一个书架,建立自己的藏书室,他在石头墙上凿了一个矩形壁橱,把一 些栓子钉入墙体,然后找来一些木板架在两个水平的栓子上做成书架,任意两块木板不在 同一水平线上,如图所示。不巧的是,鲁滨逊忽然发现有一本珍贵的旧书特别大,无法放 进他现在架好的书架里。他仔细量了这本大书的高和厚,想改造一下他的书架,以便于把 这本书放进去(别忘了,书架是做在墙里面的,不能超出范围) 。

下面是一些改造的操作方法: (1) :把架子留在原地不动; (2) :把木板向左移或者向右移; (3) :把木板锯掉一段后向左或向右移; (4) :把栓子移到与原来位置处于同一水平线的另一个位置,并把木板左移或者右移; (5) :把木板锯掉一段,移到栓子到同一水平线上另一个位置,并把木板左移或者右移; (6) :把木板和两个栓子一起拿掉。 当木板被两个栓子架住,并且木板的中心在两个栓子之间或恰在一个栓子上方时,这 个书架是稳定的。鲁滨逊开始设计的藏书室里所有的书架都是稳定的。木板的长度是整数, 单位是英寸,因为测量工具不够精确,他只能做到以英寸为单位切割木板。在你的改造中, 所有的书架必须始终是稳定的。

Your Task
找到一个方案来改造鲁滨逊的藏书室,以便于把那本古老的大书放进去,而且要使改 动尽量的少。要尽量减少移动的栓子数目(操作 4,5 每次移动一个栓子,操作 6 每次移动 两个) ,在这个前提下,找到浪费木板长度最小的方案(操作 3,5 各切掉一定长度,操作 6 把整个木板的长度都浪费了) 。木板的厚度和栓子的直径忽略不计。那本大书只能竖直放置, 它的全部厚度都要位于木板上,而且只可以碰到其他木板或栓子的边缘。

输入文件
第一行四个整数 XN,YN,XY,YT。分别描述书橱的宽和高以及老书的宽和高。 第二行一个整数 N,描述木板的个数。 接下来 N 行,每行五个整数 yi,xi,li,x1i,x2i(单位均为英寸)分别描述: yi(0<yi<YN)-第 i 块木板离书橱底的距离。 xi(0<=xi<XN)-第 i 块木板左端离书橱左端的距离。 Li(0<li<=Xn-xi)-第 i 块木板的长度。

x1i(0<=x1i<=li/2)-第 i 块木板的靠左边的栓子和该木板左端的距离。 x2i(li/2<=x2i<=li;x1i<x2i)-第 i 块木板的靠右边的栓子和该木板左端的距离。

输出文件
一行包括两个整数,分别表示在改动最少的方案中移动的栓子数与浪费的木板长 度。

Sample input#1 11 8 3 4 4 11714 43716 72634 20303 Output for the sample input#1 00 Sample input#2 11 8 4 6 4 11714 43716 72634 20303 Output for the sample input#2 13

数据约定
100%的数据中,N ≤ 100,1<=XN,YN,XY,YT<=1000; 保证其中 8 个总分值为 16 的数据非常简单。 输入数据保证合法保证有解。


相关文章:
清北学堂2013NOI模拟2
关键词:NOI模拟 同系列文档 朝鲜历届领导人资料 朝鲜现状 为什么南北朝鲜会分裂 朝鲜的近代史1/2 相关文档推荐 清北学堂2013NOI模拟1 7页 免费 2010年清北学堂生...
清北学堂备课1
清北学堂2013NOI模拟1 7页 免费 清北学堂模拟题一解析 115页 1财富值 清北学堂信息学竞赛辅导班... 6页 免费 清北学堂遗传1章序(9.11) 25页 免费如要投...
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)_学科竞赛_高中教育_教育专区。清北学堂 2013 年五一模拟押题试卷 2 注意事项: 1.请用 2B 铅笔在机读卡上做...
清北学堂2013年五一生物竞赛模拟押题试卷6答案
清北学堂 2013 年五一生物竞赛模拟押题试卷 6 答案 1 D 11 D 21 C 31 B 41 C 51 C 61 C 71 D 81 D 91 D 101 A 111 D 2 ABCD 12 D 22 D ...
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)
清北学堂 2013 年五一模拟押题试卷 2 注意事项: 1.请用 2B 铅笔在机读卡上做答; 2.试题按学科分类,单选和多选混排,是否多选题干已做说明,多选题答案 完全...
清北学堂2013年五一生物竞赛模拟押题试卷6(李争达)
清北学堂2013年五一生物竞赛模拟押题试卷6(李争达)_学科竞赛_高中教育_教育专区。清北学堂 2013 年五一模拟押题试卷 6 注意事项: 1.请用 2B 铅笔在机读卡上做...
清北学堂练习2
4页 免费 清北学堂2013NOI模拟2 5页 免费喜欢此文档的还喜欢 ...1页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...
清北学堂2013年五一生物竞赛模拟押题试卷4(赵峻峰)
清北学堂2013年五一生物竞赛模拟押题试卷4(赵峻峰)_公务员考试_资格考试/认证_教育专区。清北学堂 2013 年五一模拟押题试卷 4 注意事项: 1.请用 2B 铅笔在机读...
清北学堂2013年五一生物竞赛模拟押题试卷3含标记答案(苏宏鑫)
清北学堂2013年五一生物竞赛模拟押题试卷3含标记答案(苏宏鑫)_学科竞赛_高中教育_教育专区。清北学堂 2013 年五一模拟押题试卷 3 注意事项: 1.请用 2B 铅笔在...
清北学堂2014年五一生物竞赛模拟押题试题1
清北学堂2014年五一生物竞赛模拟押题试题1_学科竞赛_高中教育_教育专区。清北学堂...在 2013 年 8 月的全国中学生生物竞赛中获得金 牌,进入国家集训队并保送北京...
更多相关标签:
noi2013 day1 | noi2013 | noi2013快餐店 | noi2013树的计数 | noi2013矩阵游戏 | noi2013向量内积 | noi linux1.3.2.iso | noi2016 day1 |