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

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


NOIP2012 模拟赛 解题报告
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;

算法分析
当 N 不大时,暴力枚举所有点对,计算,取最优即可。 当 N 很大时,单纯的枚举算法超时。考虑把空间按照类似魔方的形式划分成>=N 份, 那么最近距离点对只可能在相邻两份的点之间(容斥原理)。因为点是随机分布的,所以期 望复杂度 O(kN),k 是常数.

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。

算法分析
假设是有根树,dist(i)为点 i 到根的距离,那么树上两点间异或距离是 dist(a) + dist(b) - 2dist(lca) 由于异或相消,上式可化为 dist[a] xor dist[b]。问题转化成 n 个 dist 中,取两个异或 值最大。可以以距离的 01 位为关键字,建立 Trie 树,每求出一个新的 dist(i)时,贪心 地在 Trie 树上找与当前 dist 异或值最大的值即可。

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;

算法分析

由于山峰比周围所有格子都高,所以 4*7 的地方最多有 8 个山峰! 而这题需要恰好给出的 X 位置是山峰,其余不是,条件比较严格。先搜索枚举山峰所在 位置,通过容斥原理,可以转化为求至少当前枚举位置是山峰的方案数,条件简化了不少。 可以用搜索来做,不过很可能超时。也可以用状态压缩动态规划来做: 枚举了必须是山峰的位置之后, 相当于在格子里从大到小填数, 一个山峰周围的格子是 不会比山峰早填数的,有多少种填法就对应有多少中方案树。DP 转移的时候,当前数字有 两种填法,一种填到山峰,一种填到可填的格子里去(即如果周围有山峰,必须已经填好) 。


相关文章:
清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告
清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告 清北学堂2012国庆NOIP模拟试题清北学堂2012国庆NOIP模拟试题隐藏>> NOIP2012 模拟赛 解题报告 Problem #1: 最近点对...
清北学堂2012国庆NOIP模拟试题——刘佳倩
清北学堂2012国庆NOIP模拟试题——刘佳倩 清北学堂2012国庆NOIP模拟试题清北学堂2012国庆NOIP模拟试题隐藏>> NOIP2012 模拟赛题目名称 文件名(.pas/.cpp/.c) 题目...
清北学堂NOIP2010模拟试题与详细解析(13)
清北学堂NOIP2010模拟试题与详细解析(13)_IT/计算机_专业资料。清北学堂NOIP2010....out 1S 128M 一、防护伞【题目描述】 据说 2012 的灾难和太阳黑子的爆发有...
清北学堂08国庆免费赠送试题
清北学堂2012国庆NOIP模拟... 4页 2财富值 清北学堂2012国庆NOIP模拟... 3...国庆学员辅助 学员辅助试 清北学堂 08 国庆学员辅助试题清北学堂教研部提供 上传...
更多相关标签:
noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2014解题报告 | noip2015复赛解题报告 | noip2016复赛解题报告 | noip2013解题报告 | noip2014提高解题报告 |