zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

解释见代码

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

点击跳转

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

f[i][j][t] = f[i][k][t'] + f[k+1][j][t''] (t'|t'' = t)

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

点击跳转

题解很妙

f[i][j][k]为从ijk步的方案数

f[i][j]这个矩阵的k次方就是答案

ans = \sum f[1][i]

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

点击跳转

连续和相当于区间和,题目的意思是求所有S_i-S_j的异或和

一般位运算的题我们都拆成二进制下32位来解决

考虑每一位

枚举k

如何统计有多少个((S_i-S_j)>>k)\&1呢?

可以开两个权值树状数组来统计01的数量

如果当前S_i的第k位为1,如果S_j\&(1<<k) = 0S_i+S_j在二进制下进位不会影响到第k位的都符合条件

也就是S_j\&((1<<k)-1) \not = (S_i\&((1<<k)-1))

\&((1<<k)-1)也就是取前k

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

点击跳转

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

点击跳转

我们可以发现gcd(a_l,...,a_r)是单调递减的,而or(a_l,...,a_r)是单调递增的

所以我们可以两次二分来找到合法区间

至于求gcd(a_l,...,a_r),or(a_l,...,a_r)我们可以用rmq来求

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

点击跳转

记录区间内最先出现的左括号和右括号

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

点击跳转

把节点按行排序

因为k很小,所以直接k^2dp就可以了

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

点击跳转

把站位当作抵消的部分

建立两棵线段树,统计x轴和y轴被覆盖的情况

每次的答案就是

放过的行数×行长度+放过的列数×列长度-抵消块数

抵消块数就是x轴被覆盖行数\times y轴被覆盖行数 \times 2

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

点击跳转

57/74
Search
search