zcmimi's blog

arrow_back二分共23篇文章

avatar
zcmimi
2020-03-25 17:13:00

整体二分是离线算法

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

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

以静态区间第k小为例,[LG P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/pro

avatar
zc
2020-09-02 16:45:00
查看原题

点击跳转

思路还算挺神奇的

题意:

\sum C_i=k,要让\sum \dfrac{A_i}{C_i}最小

T_i=\dfrac{A_i}{C_i}

假设我们每次要给一个C_i加一,那么\Delta T_i=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1},

我们要让\Delta T_i尽可能大

这样一直加一到最后,会让所有\Delta T_i趋近于相同

\begin{aligned} \Delta T_i &=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1}\\ &=\dfrac{A_i}{C_i(C_i+1)}\\ &=\dfrac{A_i}{C_i^2+C_i} \end{aligned}\\ C_i^2+C_i-\dfrac{A_i}{\Delta T_i}=0\\ C_i=\dfrac{-1+\sqrt{1+\frac{4A_i}{\Delta T_i}}}2

由于\Delta T_i是单调的,\Delta T_i越小,答案越小

所以我们可以二分\Delta T_i,并倒推得出C_i

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

分块好题

\gcd有个性质: 一旦变动则小于原来的\frac 12(最小的质因子为2)

那么总共最多\log_2 n个不同的\gcd

每个块记录的信息:

  • 块内前缀gcd
  • 块内前缀xor和

然后对块内元素按前缀xor和排序

修改操作: 修改对应元素,并重构元素所在块

查询操作:

枚举每个块,若前缀gcd不变,则直接在排序好的元素中二分查找

否则枚举判断

复杂度O(n\sqrt n \log n)

avatar
zc
2020-05-17 16:09:00
查看原题

点击跳转

有多种做法

AC自动机暴力

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

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

AC自动机暴力

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

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

avatar
zc
2020-05-16 21:36:00
查看原题

点击跳转

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

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

avatar
zc
2020-03-12 23:16:00
查看原题

点击跳转

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

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

这个结果为

1(0个平方因子)的倍数-【4,9,16,25,...】(1个平方因子)的倍数+【36,100,...】(2个平方因子)的倍数...

也就是:

\sum_{i=1}^{i^2\le n} \mu(i)\left \lfloor \frac n{i^2}\right \rfloor

这样的话只需要线性筛到\sqrt{10^9}\le 40000,然后二分查找就可以了

avatar
zc
2020-01-19 23:55:00
查看原题

点击跳转

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

点击跳转

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

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

点击跳转

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

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

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

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

解↓决↑!

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

点击跳转

可以看成两道题吧

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

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

1/3
Search
search