zcmimi's blog

arrow_back技巧共16篇文章

avatar
zcmimi
2019-01-20 00:23:01

二维线段树一般用线段树套线段树写,当然也可以用四叉树

树套树,顾名思义,外层树的每个节点都是一棵树。

[题目地址:https://www.luogu.org/problemnew/

avatar
zcmimi
2019-01-20 00:22:39
avatar
zcmimi
2018-10-27

差分约束的具体概念:

如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。

例子:

假设有3个数a,b,c 我们知道:

a-b>=2
b-c>=3
a-c>=3

那么:a与c的差

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

玄学的最短路优化

一看数据范围这么大,一定不能直接做

当你删掉某条边(u,u+1)时,最短路路线为:1->x(<=u)->y(>u)->n,并且x->y一定不会属于原最短路

就是最短路->其他边->最短路

ban:(禁用)

先把所有堵车的边ban掉,然后跑最短路

接着依次加边,跑最短路,就不用清空dis了

d(x,y)xy的最短距离

每个点的答案就是d(1,x)+d(x,n)

所以开一个堆,

枚举被ban的边

把答案和没被ban的边的编号扔进去就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接bfs

2/2
Search
search