zcmimi's blog

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

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
查看原题

点击跳转

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

点击跳转

n\le 100,每个点都只能经过一次

当然直接dfs了

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

点击跳转

我们定义第x个数中从右往左数第i位的贡献:有多少个在x之前的数j满足a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x的第i位是1.

f[x][i]表示第x个数第i位的贡献,a[x][i]表示第x个数第i位是多少。

a[x][i]=0,取j=x不会产生贡献。若j < x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x=a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}。所以f[x][i]=f[x-1][i].

a[x][i]=1,取j=x产生1的贡献。若j小于x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_xa_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}相反。所以f[x][i]=(x-1-f[x-1][i])(j小于x的贡献)+1(j=x的贡献)=x-f[x-1][i].

f[x]=f[x][0]×1+f[x][1]×2+f[x][2]×4+...+f[x][31]×2^{31}.

则答案就是f[1]+f[2]+...+f[n].

可以用滚动数组

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

点击跳转

50/66
Search
search