zcmimi's blog

arrow_back位运算共10篇文章

avatar
zcmimi
2020-06-01 13:28:00
avatar
zc
2020-04-27 12:37:00
查看原题

点击跳转

很妙的构造题

首先,可以发现异或和明显不大于总和

第二,如果异或和与总和的奇偶不同,那么无解(二进制下最低位不同,没法用进位来填充)

剩下的就都可以构造了

u=v的时候,输出u就可以了,当u=0的时候记得特判

x=\frac{u+v}2

那么\left\{x,x,u\right\}就一定可以满足

如果x \And u=0的时候\left\{x,u\right\}等价于\left\{x+u\right\}

那么\left\{x,x+u\right\}可以满足

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

点击跳转

直接建立20棵线段树统计1,2,4,8,...,2^20就可以了

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

点击跳转

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

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

点击跳转

首先将数列按位分解成32个位数列.

枚举区间的左端点,,区间的and值要对答案有贡献必须为1,随着右端点右移,and值为不递增的,而区间的or值要对答案有贡献必须为1,随着右端点右移,or值为不递减的。

可以求出每一段一段的最大长度然后统计

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

点击跳转

可以用带权并查集维护

s_x表示x到父亲的异或值

当合并的时候

l=l-1

fl,fr分别为l,r的父亲

合并后应该是:s_r \bigoplus s_l = x

\because s_r' = x \bigoplus s_l, s_r' = s_r \bigoplus s_{fr}',

\therefore s_{fr}' = x \bigoplus s_l \bigoplus s_r

我们又看到0 \leq i < 2^{30}

我们可以用hash或map离散化

注意l,r可以为0,所以实际操作时应该++r

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

点击跳转

那个只要有 10000…… 11000…… …… 就可以一直搞下去 直到为0

但是也有特殊情况:

比如k \le 4

不过这种情况特判和dfs都可以解决

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

点击跳转

f[0] = 0 

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

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

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

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

1/1
Search
search