威风镰鼬

题解

/ 注册

全部文章 / 题解（共3篇）

题解 | #起床困难综合症#

思路按位确定以下，在某一位如果是0，那么经过这些操作之后是0还是1，类似，如果某一位是1的时候也可以这样确定。那么我们就可以用logn的时间算出某一个数经过这些操作之后的值，但是这里m有点大，我们不能直接枚举。我们从高位向低位考虑，如果这一位上放0可以变成1，就直接放0，否则看放1是否能变成1...

位运算贪心

2022-05-12

1 554

题解 | #集合中的质数#

思路考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。代码 #include<bits/stdc++.h&...

状压位运算数论

2021-11-25

3 406

题解 | #毒瘤xor#

思路可以用位运算和前缀和的相关知识。要让X异或a[i]求和最大SUM，则SUM的每一位都是1，我们需要求的是X的每一位该取0还是1。我们可以用一个二维数组a[i][j]记录前i个数第j位是1的个数，这样我们就能知道L~R范围内某一位的0多还是1多。运用异或的性质我们知道，在0多的情况下X那一位该取...

前缀和异或位运算

2021-06-12

4 466