zcmimi's blog
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
查看原题

点击跳转

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

点击跳转

f[0] = 0 

i指状态压缩后的二进制数)f[i]=\sum f[i']) 

lowbit可以很快地获取一个数在二进制下第一个1在哪 

一直lowbit和异或就可以把所有1找到 

因为这道题卡常,所以只能用lowbit

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

点击跳转

动态规划

f[n][k]表示n个节点,高度为k

根节点是固定不变的

左右子树可以自由变换

那么:

f[n][k] = \sum_{i=1}^n f[i][k-1] \times f[n-i-1][k-1]

挺好的题

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

点击跳转

我们可以发现如果p\le x,那么x\mod p \le \frac x2

所以取模最多\log x

记录区间最大值,如果小于p那么直接返回

66/73
Search
search