hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4819

题意:

给你一个n*n的矩阵, 每个点是一个数字, Q个操作,每次选择一个子矩阵, 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。

 

思路:

显然是一个二维线段树…..

然而菜鸡如我,并没有写过二维线段树啊?

那怎么办呢

一首《凉凉》送给自己

 

 

然而我们还有四叉树2333

2A,写错一个地方。第一次写四叉树,orz

 

然后又写了一个二维线段树的版本,借鉴了kuangbin的写法,改成了自己习惯的代码风格。

果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ

第三个是四叉树的做法,第二个是kuangbin 的 树套树版本的二维线段树

第一个是我改写kuangbin代码之后的代码。

可以看出,四叉树虽然好写好理解一点,但是时间上不太优秀啊….

 

广义Fibonacci数列找循环节 (二次剩余)

问题:给定,满足,求的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

对于质因数小于等于delta的部分,我们选择暴力求循环节。

暴力求循环节的代码如下:

通常做法是先暴力求出来之后,写进一个表里。

通常不会有很多项。

对于质因数大于delta的部分,我们判断每个质因数是否是delta的二次剩余,如果是,枚举(prime-1)的因子,否则枚举2*(prime+1)的因子。

贴一个板子,需要注意如果是多个函数嵌套的形式,我们只需要从外向里,依次求循环节即可。

 

再补一个,更为常用的,求斐波那契循环节的板子:

 

poj 3301 Texas Trip (三分,模板题)

题目链接

题意:

给定二维平面的n个点,要求一个面积最小的正方形,使其能覆盖所有的点。

思路:

先考虑如果水平竖直地放置正方形(边和坐标轴平行)圈住所有点的最小正方形的边长是:

L=max(xmaxxmin,ymaxymin)
然后考虑如果正方形旋转的话,能圈住所有点的正方形边长是随着角度先减后增的,有凸性,可以三分。。。
但是枚举角度计算正方形的话比较麻烦,可以选择旋转平面上的点,使得正方形仍然是水平竖直放置的,因为这样计算正方形的边长比较方便。
如果把点表示成极坐标形式:

x=r×cosθ,y=r×sinθ,θ

那么顺时针旋转 α 角度后:

x=r×cos(θα),y=r×sin(θα)

化简一下可得:

x=r×cosθ×cosα+r×sinθ×sinα=x×cosα+y×sinα
y=r×sinθ×cosαr×cosθ×sinα=y×cosαx×sinα
然后就是三分角度了。。。
三分的板子:

 


 

SPOJ CIRUT – CIRU2 (多个圆交,求交任意次的面积,模板题)

题目链接

题意&思路:

给出n个圆

求恰好k个圆相交的面积,k属于1..n

 

先放个别人的代码。。。

我真是体会到了。。。软件工程这门课的重要性。。。

这代码真是烂得印象深刻。。。几何题全是面向过程?

circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。

打算改写一下。。。这代码实在是。。烂得看不下去了。。。

所以说。。。读别人代码。。。才能体会到代码风格的重要性啊。。。orz

重构了代码,感觉清爽了很多。。

 

spoj CIRU – The area of the union of circles (多个圆面积并,模板题)

题目链接

题意:

多n个圆的面积并。

思路:

发现和求2个圆的完全不一样,具体请参考

SPOJ 8073 The area of the union of circles(计算几何の圆并)(CIRU)

圆的面积并 

格林公式在面积并问题中的应用

(用格林公式搞真是跪烂了。。。。

没有仔细看细节,当成板子好了(我最菜.jpg

将代码写成了自己熟悉的风格。

以及双倍经验题:SPOJ VCIRCLES

 

 

 

BZOJ 3262: 陌上花开 (cdq分治模板题,三维偏序)

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),表示第i朵花的属性

Output

包含N行,分别表示评级为0…N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

 

思路:

第一发cdq分治,果然很好写。

cdq分治学习笔记

题目很裸,好像没什么好分析的。

代码风格的话,我是看lwt菊苣代码长大的

 

 

辛普森积分学习笔记

16沈阳的阴影还在orz,来学习一下辛普森积分。

参考资料:梯形多步法和辛普森积分

辛普森计算定积分

辛普森积分是一种数值积分方法(然后现在只记得教计算方法的是一个小姐姐,并不记得当时学了什么orz

大概就是用梯形近似计算曲边梯形面积,辛普森积分公式如下:

下面放代码:

切了个练手题,慢慢补充总结。

需要注意的是,simpson对精度要求比较高。。。eps开到1E-10才过。。

hdu1724题目链接

hdu1724解题报告

所以问题就在于写出积分公式(如果是多重积分要变成累次积分?orz)

 

 

 

 

 

 

 

 

kd tree 学习笔记

老规矩,资料先行。

好久没学新算法了,有点忘记怎么学了orz

K-D tree 数据结构

hdu 2966 In case of failure (k-d树 最近邻近点)

 

首先来看算法的提出。

现在二维平面上有n个点,知道这n个点的坐标,然后再添加一个点,问n个点中,距离新添加的点距离最近的点。

如果不做任何预处理,那么就是暴力枚举每个点,与该定点的距离。

如何优化呢? 我们可以考虑把点域均等划分成若干个方块。

这样每次询问的时候只需要查询定点所在方格,以及定点相邻的8个方格中的点与该定点的距离即可。(除非这九个方格中没有点)

这种划分方法,对于随机数据大概是美滋滋,但是数据不会那么随机,因此划分也不能均等划 分。

这个时候, kd-tree 登场。k-d树( k-维的缩写)是在k欧几里德空间组织的数据结构

对于二维平面,kd-tree的思想是,提供一种平面的划分方法,使得对于任意输入数据,划分尽可能均匀。

划分方法其实不唯一,常用的划分方法是,对于k维中的每一维,按照方差最大的那一维划分。

(看到有些题解中,用该维度的极差(就是最大值-最小值)来作为度量,也就是按照极差最大的那一维度划分。)

(用方差的度量往往比较慢,看到根据二叉树的深度,交替维度也是一种常用做法 比如2016青岛 onsite)

下面是具体的划分过程。

 假设现在我们有平面上的点集 E ,其中有 5 个二维平面上的点 : (1,4)(5,8) (4,2) (7,9) (10,11)

        它们在平面上的分布如图:

                                                                

        首先,我们对区间 [ 1 , 5 ] 建树:

        先计算区间中所有点在第一维(也就是 x 坐标)上的方差:

                平均值 : ave_1 =5.4

                方差 : varance_1 =9.04

        再计算区间中所有点在第二维(也就是 y 坐标)上的方差:

                平均值:ave_2 =6.8

                方差:varance_2 =10.96

        明显看见,varance_2 > varance_1 ,那么我们在本次建树中,分裂方式 :split_method =2 , 再将所有的点按照 第 2 维 的大小从小到大排序,得到了新的点的一个排列:

                (4,2) (1,4)(5,8) (7,9) (10,11)

        取中间的点作为分裂点 sorted_mid =(5,8)作为根节点,再把区间 [ 1 , 2] 建成左子树 , [ 4 , 5] 建成右子树,此时,直线 : y = 8 将平面分裂成了两半,前面一半给左儿子,后面一半给了右儿子,如图:

                                                                

        建左子树 [1 , 3 ] 的时候可以发现,这时候是 第一维 的方差大 ,分裂方式就是1 ,把区间 [ 1, 2 ] 中的点按照 第一维 的大小,从小到大排序 ,取中间点(1,4) 根节点,再以区间 [ 2, 2] 建立右子树 得到节点 (4,2)

                                                                

         建右子树 [4 , 5 ] 的时候可以发现,这时还是 第一维 的方差大, 于是,我们便得到了这样的一颗二叉树 也就是 K-D tree,它把平面分成了如下的小平面,使得每个小平面中最多有一个点:

                                                                 

        可以看见,我们实际上在建树的过程中,把整个平面分成了 4 个部分

        树是建了,那么查询呢?

        查询过程:

                查询,其实相当于我们要将一个点“添加”到已经建好的 K-D tree 中,但并不是真的添加进去,只是找到他应该处于的子空间即可,所以查询就显得简单的毒攻了

                每次在一个区间中查询的时候,先看这个区间的分裂方式是什么,也就是说,先看这个区间是按照哪一维来分裂的,这样如果这个点对应的那一维上面的值比根节点的小,就在根节点的左子树上进行查询操作,如果是大的话,就在右子树上进查询操作

                每次回溯到了根节点(也就是说,对他的一个子树的查找已经完成了)的时候,判断一下,以该点为圆心,目前找到的最小距离为半径,看是否和分裂区间的那一维所构成的平面相交,要是相交的话,最近点可能还在另一个子树上,所以还要再查询另一个子树,同时,还要看能否用根节点到该点的距离来更新我们的最近距离。为什么是这样的,我们可以用一幅图来说明:

                                                                

         在查询到左儿子的时候,我们发现,现在最小的距离是 r = 10 ,当回溯到父亲节点的时候,我们发现,以目标点(10,1)为圆心,现在的最小距离 r = 10 为半径做圆,与分割平面 y = 8 相交,这时候,如果我们不在父亲节点的右儿子进行一次查找的话,就会漏掉 (10,9) 这个点,实际上,这个点才是距离目标点 (10,1) 最近的点

由于每次查询的时候可能会把左右两边的子树都查询完,所以,查询并不是简单的 log(n) 的,最坏的时候能够达到 sqrt(n)

 

放一份kd-tree的代码,按照上面讲解的过程(不是作为模板)