tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

清北学堂2012国庆NOIP模拟试题——刘佳倩


NOIP2012 模拟赛
题目名称 文件名(.pas/.cpp/.c) 题目类型 输入文件 输出文件 时限 内存限制 最近点对 close 传统 close.in close.out 2s 128M 最长路径 path 传统 path.in path.out 1s 64M 山峰 mon 传统 mon.in mon.out 1s 128M

Probl

ems
Problem #1: 最近点对(Close)
Description
求空间 N 个点之间最近点对的距离,并求有多少对的最近点对。 由于本题数据规模较大,为了避免 c++选手读入超时的情况,因此本题的数据采用以下 方式生成: 首先给出一个 N,range 和 seed0,令 seedi+1 = (seedi * 16807) mod (231-1);并且令 randi = (seedi mod (2 * range)) – range; 那么 N 个点的坐标如下:

(rand1, rand2, rand3) (rand4, rand5, rand6) (rand7, rand8, rand9) (rand10, rand11, rand12) ……

Input Format
输入第一行三个数字 N,range,seed0 意义如题目描述。

Output Format
输出一行, 包含两个整数 dis,k, 表示最近点对的距离是 sqrt(dis), 一共有 k 对最近点对。

Sample Input

3 100 1

Sample Output
9163 1

样例说明
一共(-93, -51, -27), (-42, 30, -28), 和 (44, -22, 23)。第一个和第三个点距离最近,为 sqrt(9163),一共 1 对。

数据范围
20%数据满足 1≤n≤800 100%数据满足 1≤n≤150000,range≤1000000,seed0≤1000;

Problem #2: 最长路径(path)
Description
给定一棵有 N 个点和 N-1 条边的树,请你求出树中的最长路径。 这里路径长度是用 xor 定义的,即若经过的边的权值为 a1,a2,a3,...,an,则这条路径的 总权值为 a1 xor a2 xor a3 ... xor an。

Input Format
第 1 行为一个正整数 N,为点的个数; 第 2 行至第 N 行,每行包含三个正整数 x、y、z,表示 x 和 y 之间有一条权值为 z 的边。

Output Format
仅一行,包含一个数字,为最长路径的长度。

Sample Input
4 123 241 134

Sample Output
7

样例说明
2-1-3 这条路径,长度为 3 xor 4 = 7。

数据范围
对于 30%的数据,N<=1000; 对于 70%的数据,N<=40000; 对于 100%的数据,2<=N<=200000,保证输入信息给定的是一棵树,每条边的 权值不大于 10^9。

Problem #3: 山峰(mon)
Description
在 N*M 的棋盘上不重复的填 1 到 N*M,如果一个数字比周围的八个数字大,那么他就 是一个山峰。现在告诉你所有山峰的位置,问你填数的方案数 mod 12345678

Input Format
输入第一行两个数字 N,M 意义如题目描述。 接下来 N 行,每行 M 个字符,’.’表示非山峰,’X’表示山峰。

Output Format
仅一行,包含一个数字,为取模后的方案数。

Sample Input
13 .X.

Sample Output
2

数据范围
100%数据满足 1≤n≤4,m≤7;


推荐相关:

清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告

清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告 清北学堂2012国庆NOIP模拟试题清北学堂2012国庆NOIP模拟试题隐藏>> NOIP2012 模拟赛 解题报告 Problem #1: 最近点对...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com