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

清北学堂2013NOI模拟2


NOI 模拟题 题目名称 A B C 输入文件 A.in B.in C.in 输出文件 A.out B.out C.out 提交文件 A.cpp/c/pas B.cpp/c/pas C.cpp/c/pas 时间限制 4s 1s 2s 空间限制 256MB 256MB 256MB 数据组数 10 25 10

由于机器性能问题,具体评测时间按照标程两倍来算。

r />
A 题目描述 给一棵 N 个节点的树, 树的每个节点都有一个值 xi, 从树的根到每个叶子节点都是 一条链,不妨假设其中一条链为 a0,a1,a2,a3 … an,其中 a0 为根,我们忽略这个根,则有 序列 a1,a2,a3…an。 我们将每个序列看成一个长度为 n 的数组 a[1..n], 数组中每个数都满足 0≤a[i]+i≤n。 我们按照如下的过程来遍历这个数组: Counter ? 0 I?0 While I < n I?I+1 Counter ? Counter + 1 If I = n Then Break I ? I + a[I] EndWhile 不过作为一个牛逼的程序员,你可以在程序运行的过程中修改 a[I]的值,但是有如 下限制: 1、修改 a[I]变为 x,则需要使 Counter 加上|a[I]-x|。 2、修改完的 a[I]任然需要满足 0≤a[I]+I≤n。 现在我们希望知道对于每个数上的链所对应的数组,运行完上述程序这个数组的最 小 Counter 为多少(可以随意修改 a[I]的值,对于每一个链都可以修改不同的 a[I])。 将所有不同链所对应的最小 Counter 排序后,从小到大输出。 输入数据 第一行一个数 N,表示树的节点数。 接下来 N 行,第 i+1 行描述第 i 个节点。每行有 xi, mi, y1,y2…ym。 其中 xi 为节点 i 对应的值,mi 表示 i 节点的儿子个数,y1~ym 分别表示这 mi 个儿子 的编号。 数据保证节点 1 的 x1 = -1,且每条链都满足上述要求。 输出数据 输出 K 行,K 为不同链数(也就是叶节点的数目) 。 从小到大输出,表示不同链对应的最小 Counter。 输入样例 7 -1 1 2 1 2 3 7 3 1 4 0 1 5 0 1 6 0 0 0 0 输出样例 1

3 数据规模 数据保证有 20%的数据 N≤2000; 有 60%的数据保证 N≤200000; 另有 20%的数据,输出个数 K≤50; 所有数据 N≤1000000。 样例解释 样例有两个链 -1, 1, 3, 0, 0, 0 以及 -1, 1, 0。 对于第一个链,首先花费 1 的代价,将 1 修改为 0,然后按上述程序运行,最后 Counter=3。

B 题目描述 小 B 最近刚学习了 php 语言,于是自己写了 N 个网页,并且给他们都加上了超链 接。但是由于小 B 十分懒,所以每个网页都只有一个超链接。 现在小 B 将,第一页设为了主页,它希望从主页开始点超链接,所有的网页都可以 在 K 次点击之后被连接到。所以它需要增加超链接。但是,正如刚刚所言,小 B 实在 是很懒,所以它希望能尽量少的添加超链接。 所以麻烦你告诉它,最少需要添加多少超链接。 输入数据 第一行两个数 N,K,与题目描述一致。 接下来 N 行,每行连个数 A,B,表示一个超链接,从第 A 个网页,连接到第 B 个 网页。 数据保证,每个页面只有一个连接出去的超链接。 输出数据 一个数,表示最少需要增加的超链接数。 输入样例 8 3 1 2 2 3 3 5 4 5 5 6 6 7 7 8 8 5 输出样例 2 数据规模 2 ≤ N ≤ 500 000, 1 ≤ K ≤ 20 000。 其中 20%的数据,N ≤ 5000。

C 题目描述 给一个 width* height 的矩阵,操作 K 次。每次先按 xfold[i](x 轴上)对折,然后平均 分成 cnt[i]+1 段,折起来。然后对一个子矩形(四个角分别为 x1[i],y1[i],x2[i],y2[i])染 色(渗透),然后展开,继续下一步操作。

问你没有染色的格子数。 输入格式 第一行 3 个数,width, height,K。表示宽度高度和操作次数。 接下来 N 行,每行 6 个数,表示 xfold[i],cnt[i],x1[i],y1[i],x2[i],y2[i]。 输出格式 一个数表示没有被染色的个数。 数据规模 K≤50。 0≤ x1[i]< x2[i]≤ max(xfold[i],width-xfold[i]) 0≤ y1[i]< y2[i]≤ height/(cnt[i]+1) Height mod (cnt[i]+1)=0 输入样例 5 6 1 2 2 1 1 3 2 输出样例 21 样例解释 样例解释就是上面那几幅画。


相关文章:
清北学堂2013NOI模拟2
清北学堂2013NOI模拟2 rtrt隐藏>> NOI 模拟题 题目名称 A B C 输入文件 A.in B.in C.in 输出文件 A.out B.out C.out 提交文件 A.cpp/c/pas B.cpp...
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)
清北学堂 2013 年五一模拟押题试卷 2 注意事项: 1.请用 2B 铅笔在机读卡上做答; 2.试题按学科分类,单选和多选混排,是否多选题干已做说明,多选题答案 完全...
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)
清北学堂2013年五一生物竞赛模拟押题试卷2(鲁昊骋)_学科竞赛_高中教育_教育专区。清北学堂 2013 年五一模拟押题试卷 2 注意事项: 1.请用 2B 铅笔在机读卡上做...
清北学堂练习2
5页 2财富值 2010年清北学堂生物联赛模... 14页 5财富值 2008年清北学堂化学竞赛试... 4页 免费 清北学堂2013NOI模拟2 5页 免费喜欢此文档的还喜欢 ...
清北学堂备课2
清北学堂2013NOI模拟2 5页 免费 清北学堂培训2 暂无评价 48页 免费 清北学堂...B H 2O CaCO3 C H 2O HCl HN 中和 D E O2N P N CH2CH2Cl 2 N...
清北学堂备课1
清北学堂2013NOI模拟1 7页 免费 清北学堂模拟题一解析 115页 1财富值 清北...正确画出铝的分布得 2 分,正确标出共面八面体得 1 分,共 4 分 无机化学...
清北学堂2011年全国高中数学联赛全真模拟2
2011 年全国高中数学联赛全真模拟(第二套) 年全国高中数学联赛全真模拟(第二套) 北京清北学堂内部资料(清北学堂教研部特邀湖北省竞赛相关老师命制,内部资料,禁止...
2008年清北学堂化学竞赛试卷2
2008 年清北学堂化学竞赛试卷 2 (时间:3 小时 满分...1 第三题 金属单晶的结构可用等径圆球的密堆积模拟...©2013 Baidu 使用百度前必读 | 文库协议...
2011_年清北学堂全国中学生生物学联赛模拟测试题一
2011 年清北学堂全国中学生生物学联赛模拟测试题一命题人:北京大学 赵峻 峰 ...。 A 4 种,51:24 :24 :1 B 4 种,9:3:3:1 C 3 种,2 :1:1 D...
清北学堂2012年全国高中化学竞赛模拟试卷(四)参考答案
[H2Ga(NH3)2] [BH4] (G) + Ga + H - (2) H B NH 3 H H H NH 3 第三题: 1 清北学堂:www.qbxt.cn 版权所有 翻印必究 1.(1) (未标 ....
更多相关标签:
noi2013 | noi2013快餐店 | noi2013 day1 | noi2013树的计数 | noi2013矩阵游戏 | noi2013向量内积 | noi2016 day2 | noi linux1.3.2.iso |