标签 - KD tree

? 解题记录 ? ? LOJ ? ? KD tree ?    2018-10-03 10:23:58    786    0    0
地址:https://loj.ac/problem/2586  说一说我和这道题的故事吧。打完T1的5分后我又来看到了T2。一看完了又不会,赶快打了个7分暴力。再想想,我貌似可以拿Subtask2的12分,准备打完T1来码。然后T1的400个set死活打不出来……于是乎这道题是彻底凉了。一下来就听见很多人码了个KD-tree爆艹T2,什么鬼????不过正解貌似是个线段树维护扫描线,没人写……  然后为了练习KDtree,今天又搬出这道题来。思路大概是一个节点维护能框住下面所有圆的最小矩形。嗯……就是把圆并近似成矩形判相交剪枝然后骗分。这个做法在考场上就能得到87分,都怪当年
? 解题记录 ? ? BZOJ ? ? KD tree ?    2017-12-16 20:36:09    364    0    0
Description巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜 欢过于甜的巧克力。对于每一块巧克力,我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的 评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x 和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c,所有甜味程度大于等于c的巧克力他都 无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少 Input第一行两个正整数n和m,分别表示巧克力个数
? 解题记录 ? ? BZOJ ? ? KD tree ?    2017-07-21 10:06:08    505    0    0
2716: [Violet 3]天使玩偶Description Input Output           终于,第一棵KDtree ,撒花~~~撒花~~~撒花~~~       才知道这道题用4个CDQ容斥不是一般的快,但是80SEC的时间限制给kdtree亮了绿灯!       主要思想先把所有操作离线,对包括所有插入节点的点集建树,把出现的点做一个exist    
? 解题记录 ? ? KD tree ? ? BZOJ ? ? cdq分治 ? ? 分治 ?    2017-07-21 10:06:08    781    0    0
Description 有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),