zcmimi's blog

arrow_back异或共3篇文章

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

点击跳转

先求个异或前缀和,然后就变成求k对最大异或和

因为(i^j) = (j^i)

所以我们设2k对,到答案在除以2就可以了

我们先找出每个点能得到的最大异或和,然后放堆里

每次取出堆顶,求出它能得到的第rk+1大的异或和

如果rk+1 \le n,那就放到堆里

(因为一个点最多用n次,要不就重复了)

记得long\ long

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

点击跳转

i对答案会统计\left \lfloor \frac ni \right \rfloor次,但只有出现奇数次才会产生贡献

每次的贡献是i \bigoplus i+1 \bigoplus ... \bigoplus j,那么可以用数列之异或这道题的思路做

1/1
Search
search