zcmimi's blog
avatar
zc
2020-01-01 17:27:00
查看原题

点击跳转

qwq

qwq

> > > qwq

avatar
zc
2019-12-31 22:54:00
查看原题

点击跳转

夫妻之间:girl \to boy

情人之间:boy \to girl

Tarjan求强连通分量,对于一对夫妻,如果两人在同一个强连通分量里,那么这对婚姻就是不安全的,反之,则是安全的。

avatar
zc
2019-12-31 21:29:00
查看原题

点击跳转

假设当前被封锁的是x

如果x不是割点,那么除x外的点都连通,答案为2\times(n-1)(x和其他n-1个点配对)

如果x是割点,删掉x后图会变成若干个连通块,设这些连通块大小为t_1,t_2,...,t_a

那么答案为:\sum_{i=1}^a t_i\times(n-t_i)+(1+sum)\times(n-sum-1)+n-1

avatar
zc
2019-12-31 20:01:00
查看原题

点击跳转

分类讨论:

Tarjan跑出割点,然后DFS搜索所有的联通快

计算每一个联通快中的割点数目

分类讨论:

  1. 没有割点

    至少需要建立两个出口

    从任意非割点的地方选择两个点建立

  2. 这个分组只有一个割点

    只需要在分组内设立一个出口

    可以设立在任意一个非割点的地方

  3. 有两个及以上个割点,则无需建立,可以直接到达其他联通块

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以看成两道题吧

50\%: 二维前缀和+二分

50\%: 主席树同时维护区间大于k的个数、总和,然后二分即可

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

这个图是个DAG,我们可以很快地处理出每个点以他为起点(ds_i)或终点(dt_i)的最长路

接着我们枚举删掉哪个点

我们可以将拓扑序小于当前点的点称作A集合,大于的称作B集合

删掉这个点后的最长路有三种可能:

A\rightarrow A,A\rightarrow B,B\rightarrow B

(to指x连接的点)

当删除一个点x时,我们可以删去所有集合中的dt_to+1+ds_x(反向图中的)

求出集合中的最大值就是当前最长路长度

接着将dt_x+1+ds_to加入集合,转移到下一个状态(原图中的)

于是我们需要一个数据结构满足以下要求:

  1. 插入某个值
  2. 删除某个值
  3. 查找最大值

我们可以用堆(手写堆或者两个stl优先队列)、平衡树、权值线段树等维护

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

kruskal重构树模板

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

先想想暴力做法:

bfs出不涉水可以到达的点,然后在这些点中找出与点1的最小距离

优化:

我们可以使用kruskal重构树来快速求出这些点

先按海拔从高到低排序,这样见出来的kruskal重构树的是海拔的小根堆

我们可以倍增找出最远可以到达的祖先,然后求出这段区间中的点与点1的最小距离

可以在dfs的时候预处理

详见代码

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

扩展欧拉定理

b\ge \varphi(m)时,a^b \equiv a^{(b \mod \varphi(m))+\varphi(m)} \pmod m

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以算是kruskal重构树的模板题

建完kruskal重构树,我们可以发现一个节点(新建的带点权的点)能走到的节点一定在它的子树中

那么我们可以用dfs序+主席树维护

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点t权值为边权,然后连边> t\rightarrow x,t\rightarrow y

代码:

37/73
Search
search