zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2020-01-04 20:18:00
查看原题

点击跳转

点分治

avatar
zc
2020-01-04 10:21:00
查看原题

点击跳转

我们先预处理出L_i,R_i分别表示与a_i相同的数出现在i左边和右边的位置

我们可以使用分治来判断一个区间是否合法

我们设当前区间为[l,r]

从两边一起找

假设枚举到位置iL_i<lR_i>r,那么左端点在[l,i],右端点在[i,r]的区间都是"non-boring"

这时我们只需要判断区间[l,i-1][i+1,r]是否合法就可以了

复杂度可以降至\Theta(n \log n)

avatar
zc
2020-01-03 18:01:00
查看原题

点击跳转

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
查看原题

点击跳转

kruskal重构树模板

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

点击跳转

可以看成两道题吧

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

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

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

点击跳转

可以先考虑离散化

离散话后是1~n

一般要求中位数可以:

二分中位数x

将区间中<x的赋值为-1,\ge x的赋值为-1

若区间和为0,那么x就是中位数

题目是要求左端点在[a,b],右端点在[c,d]的序列的最大中位数

区间[b+1,c-1]是必选的

我们可以求[a,b]的最大后缀和[c,d]的最大前缀

如果这三个部分的和大于零,那么当前二分的值是合法的

这个一看就可以用线段树维护

我们再来考虑x变成x+1会有什么变化:

  1. 原来<x的还是-1
  2. 原来>x的还是1
  3. 原来=x变成-1

所以我们只需修改值为x的位置(可以先用链表或vector存下所有值为x的位置)

其实从小到大排序后按顺序更改就完事了

数离散化后的大小不超过n

我们可以先预处理出所有x(中位数)对应的线段树

可是空间不够啊

这时候主席树就派上用场了

下面是简洁的代码:

30/66
Search
search