[BZOJ3054] Rainbow的信号（考虑位运算 + DP？）

传送门

BZOJ没数据范围。。。

其实数据范围是这样的。。

前20%可以直接n^3暴力枚举每个区间

前40%可以考虑每一位，因为所有数每一位都是独立的，而和的期望=期望的和，那么可以枚举每一位，再枚举区间，最大 31*n*n

想到枚举每一位也就离正解不远了，可以dp，

对于xor有贡献的是区间xor值为1的区间，那么f[i]表示以i结尾的区间异或值为1的个数，那么xor就很好解决了

对于or，我们只需要找出所有的全为0的区间，拿总区间个数减去就好，

对于and，我们只需要找出所有全为1的区间即可

#include <cstdio>#include <cstring>#define N 100005#define LL long long#define max(x, y) ((x) > (y) ? (x) : (y))int p1, p0, mx;int a[N], f[N];LL n, num0, num1, cnt;bool b[N];double ans1, ans2, ans3;//f[i]以i结尾的 xor值为1的数量int main()for(k = 0; mx; mx >>= 1, k++);for(i = 0; i < k; i++)for(j = 1; j <= n; j++)if(p0 ^ 1) num0 += (LL)(j  p0) * (j  p0);if(p1 ^ 1) num1 += (LL)(j  p1) * (j  p1);cnt *= 2;for(j = 1; j <= n; j++)if(a[j] & (1 << i)) cnt;ans1 += 1.0 * (1 << i) * cnt / n / n;ans2 += 1.0 * (1 << i) * num1 / n / n;ans3 += 1.0 * (1 << i) * (n * n  num0) / n / n;}printf("%.3lf %.3lf %.3lf\n", ans1, ans2, ans3);return 0;}

上一篇：[BZOJ4506] [Usaco2016 Jan]Fort Moo（DP？）

下一篇：Codeforces Round #345 (Div. 2) E. Table Compression（并查集）