menu zcmimi's blog

arrow_back 二分

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机

zc
2020-05-17 16:09

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可 ```cpp

include<bits/stdc++.h>

define gc get

zc
2020-05-16 21:36

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P383

zcmimi
2020-03-25 17:13

题意:求第k个没有完全平方数因子的数

可以发现答案具有单调性,可以二分答案,然后判断[1,n]中满足条件的个数是否为k

这个结果为

1(0个平方因子)的倍数-【$4,9,16

zc
2020-03-12 23:16

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2020-01-19 23:55

看到边不能重复用,n\le 200,T\le 200就可以想到网络流

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma 
zc
2020-01-18 23:37

可以先rmq预处理出区间gcd和区间min

若区间gcd=区间min那么这个区间是合法的

若一个区间合法,那么它一定有合法的子区间

我们可以根据这个性质二分区间长度

解↓决↑! ```

zc
2020-01-18 22:40

可以看成两道题吧

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

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

include<bits/stdc++.h>

nam

zc
2019-12-31 11:31

可以先考虑离散化

离散话后是1~n

一般要求中位数可以:

二分中位数x

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

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

zc
2019-12-31 11:31

首先,我们只用分析 NO 的情况,其他的都是 YES,NO 的情况有两种:

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在
zc
2019-12-21 19:47
1 / 3
Search
search