简述
线性基应该算是线性代数范畴内的东西。在 OI 中,线性基被用来解决位运算或者是向量表示的问题。
建议读者学习了高中数学中的向量之后再来阅读本文,相信这样会帮助理解线性基。
线性基应该算是线性代数范畴内的东西。在 OI 中,线性基被用来解决位运算或者是向量表示的问题。
建议读者学习了高中数学中的向量之后再来阅读本文,相信这样会帮助理解线性基。
这道题挺有趣的,归根结底就是位运算。首先,一个充分的结论就是枚举长度为\(1\)的区间的概率为\(\frac{1}{N^2}\),而长度大于1的概率为\(\frac{2}{N^2}\)。之后,枚举\(int\)的长度\(i \in [0,30]\),把所有数的第\(i\)位组成一个序列进行扫描,之后枚举到第\(j\)个数进行分类讨论。
// CH3801.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 200; int n, arr[MAX_N]; double ans1, ans2, ans3; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &arr[i]); for (int k = 0; k < 30; k++) { int last[2], c1 = 0, c2 = 0; last[0] = last[1] = 0; for (int i = 1; i <= n; i++) if ((arr[i] >> k) & 1) { ans1 += (1 << k) * 1.0 / n / n; ans2 += (1 << k) * 1.0 / n / n; ans3 += (1 << k) * 1.0 / n / n; ans1 += (1 << k) * 2.0 / n / n * c1; ans2 += (1 << k) * 2.0 / n / n * (i - 1); ans3 += (1 << k) * 2.0 / n / n * (i - 1 - last[0]); last[1] = i; c1++, swap(c1, c2); } else { ans1 += (1 << k) * 2.0 / n / n * c2; ans2 += (1 << k) * 2.0 / n / n * (last[1]); last[0] = i, c1++; } } printf("%.3lf %.3lf %.3lf", ans1, ans3, ans2); return 0; }
这道题用的方式非常之神仙,用位运算来判断数字的选与不选。首先我们先来构造几个辅助数组,以便把映射数组\(X,Y,Box\)的值预先求出,然后再处理几个位运算的辅助数组。由于做法过于神仙,难以解释,看代码就好。
如何找到一对异或值最大的数字呢?我们先从二进制计算(位运算)本身讲起,如果我们要保证\(Xor\)值更大,那么我们就需要尽可能多的\(1\),除此之外,\(1\)的位置也非常重要,在一些情况下靠前更好。我们可以考虑从最高位为起点向最低位建立一个 Trie 树。我们记\(num[i]\)表示第\(i\)位的\(0或1\)状态。建立 Trie 树之后,我们计算出每个数所对应的异或值最大的值。我们的策略是: