快省选滚粗了,来总结一下计算几何
计算几何是著名的口上A着快,写出来各种拿不到分,大坑小坑满天飞(做过的所有计算几何题只有两道1A了。所有计算几何几乎没法调试,没法对拍)。
所以在这里总结一下类型,先从基础讲起。信息学的几何和数学的几何有很大不同,由于有强大的计算能力所以一般直接爆算就是了,什么梅尼劳斯、费马点之类的公式完全用不上,暴力不解释。由于要解析几何,使用向量特别多,比如空间中一条直线,能用向量两点式就不用y=kx+b,为什么?k计算时会爆啊inf...,暴了就WA了。
向量的使用有极大的优势,可以不用区分象限什么的,面积叉积就好了,由于有了向量,什么距离面积都可以是负的,极大地统一了公式尽量免去了分类讨论与细节。
不支持交换律,A×B=a.x*b.y-b.x*a.y,就是由ABO所形成的三角形的面积的两倍(B在OA左侧为正,反之为负),至于证明。。。网上多的是。用来判断直线与点的位置关系用得最多。比如poj2318。用来求面积也有,比如bzoj1132。
也就是向量与X轴正方向的夹角,这个可比数学好用多了,比如两角之和的cos值怎么求?和角公式?直接暴力atan2、acos、asin求出角度相减就是,然后再求一个cos,这时终于感到cmath库的强大了。例:bzoj1419.
可以如上方所述暴力,但暴力较慢,如果旋转操作特别多的话还是手推和差角公式转一转。练习题目poj3845。还有一道旋转玄学bzoj3707。(顺带附上一句bzoj3707的方法在有三点共线的情况下是错的别问我是怎么知道的,不过此题不影响,反正是0,只是这个方法不能用来求最大三角形面积。)
向量两点式配合面积倒一倒来求交点还是很兹糍的,草稿纸上手玩一下就好了,不过要考虑到特殊情况才行。比如这几种情况
inline point get_inter(const seg &a,const seg &b){
long double p1=-cross(dec(a.b,a.a),dec(b.b,a.a));
long double p2=cross(dec(a.b,a.a),dec(b.a
这一些数据结构会在一些比较简单的数据结构题考到。作为纯数据结构题的话,noip不会考,省选和NOI又太简单,只有在校内考试或者网赛会遇到。
不过维护其他问题还是有用的。比如难一点的动归、几何。
就像把线段树建在了一个表上。一般我们计算一个区间中某个数出现多少次的时候会有b[a[i]]++;这样的动作。a数组就是原数组,b数组是他的值域数组。在b数组上建立线段树可以做到查询第k大、支持一些修改后的k大、插入一个整数查询一个整数是否存在。值域线段树没有用的节点可以不用先建立出来。自然也有值域数组。
要合并线段树要求两个线段树在结构上完全相同,详见黄嘉泰论文。可以做到n棵主席树nlogn的合并。在一些区间合并时合并对应的值域线段树有用。尤其是维护树上信息时相当有用。
又称主席树。可持久化的思想就是新建代替修改,保留原有版本。有两种方式:path copy和fat node。path copy常见于有指针建立的数据结构,而fat node就是用于一些必须用数组访问的数据结构。线段树一般采用path copy,对于一个修改二分下去之后每次到达的一个节点就复制该节点后修改。这样没有改变的部分就和原有节点共用。(不必担心共用节点会被更改,因为可持久化不改变原有节点。)这样就有了o(1)复制一个数组的能力(其实就是复制线段树根节点),然后log(n)的单点修改、查询。这样就可以在nlogn的时间内完成建立n个相似的值域线段树。这样就可以完成区间k大、众数之类的支持区间减法的值域数组干的事了。fat node就是给每个节点建立一个set,查询(版本号,数据)。
没什么说的。只是可以拓展到高维而已。但是空间有点捉急。这时就可以上hash了。
由排序二叉树衍生出来的许多树。比如Treap、Splay、替罪羊树、朝鲜树、重量平衡树等。
这是对最近的一些学习的总结。
这一些数据结构是一般会在动归题、几何题用到的。
维护一个栈的单调性,比如521的栈加入3后就应该弹出2 1,变成5 3.用途:一般用于一个序列中求右侧第一个比自己大的数是多少,或o(n)处理一些区间信息。
相对于单调栈只是加了一个关键字。(a,b),一般用于动归中求解最值。比如要维护比bi大的所有二元组中a最小的,这样的问题。
用于连通性、一些简单关系的处理。路径压缩或者启发合并都可以。
应该归入概念。相关的题:松鼠的新家。
字符串骗分神器。也可以替代一个开不下的数组(一般开不下的东西都遍历不完)。
其实并没有什么用。知识学习一下2^k的思路而已。类似的有lca的倍增求解。那个到特有用。
前缀拆分利器。据说数组数组的常数只有线段树的1/8.可以用来求一些前缀或者支持区间减法的比如区间和。
区间拆分利器。可以对于一个区间拆分成logn个区间之和。只需要支持区间加法即可。相关用途,区间加减乘除,最大和子序列、区间最值、区间取min和max。
1、要清楚,最好纸上画出来。
2、要优化:根据网络流建模汇总里说的
如果几个结点的流量的来源完全相同,则可以把它们合并成一个。
如果几个结点的流量的去向完全相同,则可以把它们合并成一个。
如果从点 u 到点 v 有一条容量为∞的边,并且点 v 除了点 u 以外没有别的流量来源,则可以把这两个结点合并成一个。
如果点u只有一个来源和一个去向,则可以保留容量最小边,删除点u.
3、对于边的构建的优化
4、如果确定图形可以是平面图,考虑对偶图。
时间戳:用一个计数变量表示时间,一个数组记录到达该点时的时间,每访问到一个新的点时间戳+1;
tarjan算法的核心思想是:如果当前点是我们访问到的一个连通分量中的第一个点,那么之后的点一定访问不到该点之前的时间戳,而且该点之后处于同一连通分量中的点能访问到的最小时间戳就是该点的时间戳。
如上图所示(有点丑),红色为该点的时间戳,蓝色为其他图中的边,绿色为该点能到达的最小时间戳。
计算方程:最小时间戳(u)=min(u的时间戳,所有u能到达的点v中的 最小时间戳(v){v没有分配到某个联通分量 } );
实现:用lowbit记录某点能访问到的最早时间,time记录该点的时间戳。
每到达一个点把该点压入栈,标记vis。
如果lowbit==time则该点就是这个连通分量中的第一个点,而其他点一定能访问到他。所以一直pop直到该点被弹出。(弹出来的都属于这个连通分量)
如果不懂可以自己画个图手动模拟一下感受感受。
如下情况 2 -> 1 ,从1开始DFS一次,2开始DFS一次,一定要区分这两次,mint不要混了!
还有!DFS链必须是自己的DFS链
int sta[N],top,ltcnt,size[N],mint[N],tcnt,belong[N];
void DFS(int u){
int now=++tcnt;mint[u]=now;sta[++top]=u;
for(int i=head[u];i;i=e[i].next){
if(belong[e[i].t]!=0) continue;
if(mint[e[i].t]==0) DFS(e[i].t);
mint[u]=min(mint[u],mint[e[i].t]);
}
if(mint[u]==now){
ltcnt++;
while(sta[top]!=u) size[ltcnt]++,belong[sta[top--]]=ltcnt;
size[ltcnt]++,belong[sta[top--]]=ltcnt;
}
}
2016-02-10
这几天开始学图的连通了(因为发现这是个大坑,好像很基础,但我不会)。于是就神神奇奇地开始写缩点了,但貌似调了一个晚上。所以觉得还是写一下总结总结比较不错。
先说一下什么是连通吧:
如果点A可以通过某条神奇的小道到达B,而B也可以一阵乱走走到A,那么A、B是连通的。无向肯定不用说,毕竟可以原路返回,所以两点一定连通。
连通图的定义:如果该图中任意两点都连通,则这个图是个连通图。(如果这是个有向图,还可以叫强连通图。反正有“强”的就是针对有向图的。)
(强)连通分量是什么呢?就是一个图中的尽量多的互相连通的一些点构成的一个子图呗。
如下图中橘黄色圈出来的是两个强连通分量:
(单个的1算不算?可以不用纠结,没人会考你这个。)
好了,来讲下最常用的缩点吧!
有两种缩点的方法:
1、一种是kozaraju提出的。(别问我怎么念)
2、tarjan提出。(跟我念塔儿尖)
(不知道他当初是怎么脑洞大开想到的)
图中橘黄色圈出的为强连通分量,蓝色是标号,红色是连通分量之间的边。
图中橘黄色圈出的为强连通分量,蓝色是标号,红色是连通分量之间的边。
如果我们在一个连通分量里一阵DFS乱搜,肯定能把该连通分量内的所有点搜出来,但是肯定会混杂一些其他的点。但如果我们有顺序地搜,比如从3中任意一个点开搜,肯定会刚好把3这个连通分量的所有点搜出来,记录以及标记;然后是2,1,5,4;
是不是有点拓扑顺序的感觉?
对的就是这样,所以他采用的DFS版的拓扑序。但是这个图毕竟有环,连通分量自己内部的情况太复杂——
比如这样
如果从1开始搜,你会很愉快地先把3加入拓扑序列。
拓扑序乱了怎么办呢?没有关系,看之前在DFS版拓扑中说的——现在正在访问的点永远会比它可以到达的点先输出。
我们能够保证1所在连通块总有一个点会比其他连通块中的点后出现在拓扑序列中。
没看懂?接下来更详细讲解。(其实这个方法不常用,可以略过)
上图中ABC分别代表三个连通分量
一下以abc代表三个对应连通分量中的点
我们希望得到的顺是CBA,按照这个顺序可以放心地顺着乱搜
如果我们从BAC的顺序(随机)开始生产拓扑序(注意是
我不得不得不说这是一种神奇拓扑序生成方式。
我们沿着有向边反着走,假设我们搜索到了u,那么下一步会搜索所有指向u的点,因为只要这些点存在就还不能把u加入拓扑序中。
思路如下:
function DFS(int u){
for(所有通过有向边可以到达u的点v){
如果v没有被删掉
DFS(v);//访问完后v会被删掉
}
把u加入拓扑序中
删掉当前点u(可以采用打标记的方式)
}
当然我们还可以开一下脑洞
为什么不能就顺着来呢?然后把得到的拓扑序列反转呢!
事实证明这是可以的。poj2367板题可以过。(有special judge)
那么我们还是来证明一下正确性吧:
对于原拓扑序列,该序列只有一个要求及:如果u是v的祖先(反着就是有一条从u到v的路径),那么在拓扑序中u必须比v先出现,而DFS就可以满足这个需求,在递归完成之前是绝不会被输出的,而该点的DFS可以访问到它所有的祖先。而现在我们把图正向序列反向也可以保证子孙先比祖先后出现。现在正在访问的点永远会比它可以到达的点先输出。
速度上这个办法的常数是明显大于常规拓扑排序的。
2016-02-05
对偶图是建立在原有的平面图上的。
对于为什么叫对偶图,先看下度娘对于对偶的解释:
对偶是用字数相等、结构相同、意义对称的一对短语或句子来表达两个相对应或相近或意思相同的修辞方式。
自己可以看完对偶图的建图之后再来琢磨下这个句子,脑补一下对偶图的对偶
好了,说正事。
这是一张对偶前的平面图
红线组成的是它的对偶图
什么?不知道怎么画?
就是把面变成点,相邻的面连边。(所以每一条边都会跨国原有边界。)
so,我们现有一个平面图
然后再找出图上所有面(还有最外面无限大的面)
然后,把面看成点
就像之前说的,相邻的面连边,蓝色与红色和紫色还有灰色相连(只有一个定点相同的不算,如绿色和蓝色)
然后连下去
就画好了
那么有什么用呢
比如最小割之类的啊
如果左上和右下分别为源点(S)和汇点(T),那么如果我们把外侧无限大的面分成两个 半面,(忽略无限大面自己之间的连线),构造对偶图,那么对偶图中灰蓝色点到灰紫色点的的任意一条路径都是原图的一个割。
因为对偶图中的边会跨过切只会跨过原图中的一条边。所以就可以在最短路的时间内跑最小割了。
例题传送门
2016-02-03