资源描述：
《清北学堂2012国庆noip模拟试题——刘佳倩》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、NOIP2012模拟赛题目名称最近点对最长路径山峰文件名(.pas/.cpp/.c)closepathmon题目类型传统传统传统输入文件close.inpath.inmon.in输出文件close.outpath.outmon.out时限2s1s1s内存限制128M64M128MProblemsProblem#1:最近点对（Close）Description求空间N个点之间最近点对的距离，并求有多少对的最近点对。由于本题数据规模较大，为了避免c++选手读入超时的情况，因此本题的数据采用以下方式生成
2、：首先给出一个N，range和seed0，令seedi+1=(seedi*16807)mod(231-1)；并且令randi=(seedimod(2*range))–range；那么N个点的坐标如下：(rand1,rand2,rand3)(rand4,rand5,rand6)(rand7,rand8,rand9)(rand10,rand11,rand12)……InputFormat输入第一行三个数字N，range，seed0意义如题目描述。OutputFormat输出一行，包含两个整数dis,k，
3、表示最近点对的距离是sqrt(dis)，一共有k对最近点对。SampleInput31001SampleOutput91631样例说明一共(-93,-51,-27),(-42,30,-28),和(44,-22,23)。第一个和第三个点距离最近，为sqrt(9163)，一共1对。数据范围20%数据满足1≤n≤800100%数据满足1≤n≤150000，range≤1000000，seed0≤1000；Problem#2:最长路径（path）Description给定一棵有N个点和N-1条边的树，请你
4、求出树中的最长路径。这里路径长度是用xor定义的，即若经过的边的权值为a1,a2,a3,...,an，则这条路径的总权值为a1xora2xora3...xoran。InputFormat第1行为一个正整数N,为点的个数;第2行至第N行,每行包含三个正整数x、y、z,表示x和y之间有一条权值为z的边。OutputFormat仅一行，包含一个数字，为最长路径的长度。SampleInput4123241134SampleOutput7样例说明2-1-3这条路径，长度为3xor4=7。数据范围对于30%的
5、数据,N<=1000;对于70%的数据,N<=40000;对于100%的数据,2<=N<=200000,保证输入信息给定的是一棵树,每条边的权值不大于10^9。Problem#3:山峰（mon）Description在N*M的棋盘上不重复的填1到N*M，如果一个数字比周围的八个数字大，那么他就是一个山峰。现在告诉你所有山峰的位置，问你填数的方案数mod12345678InputFormat输入第一行两个数字N，M意义如题目描述。接下来N行，每行M个字符，’.’表示非山峰，’X’表示山峰。Outpu
6、tFormat仅一行，包含一个数字，为取模后的方案数。SampleInput13.X.SampleOutput2数据范围100%数据满足1≤n≤4，m≤7；
