zcmimi's blog

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

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

点击跳转

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

点击跳转

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

点击跳转

二分第k大平均数w,统计平均数大于等于它的区间的个数

这样的区间满足\frac {s_r - s_{l-1}}{r-l+1} \ge w

化简一下: s_r - s_{l-1} \ge w(r-(l-1)) \\\\ s_r - wr \ge s_{l-1} - w(l-1) 那么我们只要用树状数组统计一下就可以了(当然你要用权值线段树也可以)

因为平均数可能不是整数,所以我们要离散化一下才能统计

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

点击跳转

区间dp

显然设f[i][j]表示[i,j]最小的表示方法

普通情况:

f[i][j] = \min(f[i][k]+f[k+1][j])

当我们找到循环节:

f[i][j] = \min(f[i][j],f[i][k] + 2 + \text{<循环节个数>})

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

点击跳转

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

点击跳转

一段区间检查后能不被吃掉的汉堡满足其他汉堡的能量值都是它的倍数

那我们就求出区间\gcd. 而这个汉堡的能量值必须等于区间gcd,所以它的能量值也是区间最小值。

那我们就再记录区间最小值并且记录数量

那么满足这个复杂度而且最方便的当然是线段树了

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

点击跳转

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

点击跳转

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

点击跳转

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

点击跳转

58/65
Search
search