题目： #10056. 「一本通 2.3 练习 5」The XOR-longest Path 解析： 做完#10051后就不是很难了 继续利用异或的性质有\(dis(u,v) = dis(1,u)\oplus dis(1,v)\) 把边权放到点上，然后字典树求最大异或值 代码 #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, m, num, cnt, tot, ans; int id[N], a[N], head[N], sum[N]; bool vis[N]; struct n...

题目： #10051. 「一本通 2.3 例 3」Nikitosh 和异或 解析： 首先我们知道一个性质\(x\oplus x=0\) 我们要求\[\bigoplus_{i = l}^ra_i\]的话，相当于求\[(\bigoplus_{i = 1}^la_i)\oplus (\bigoplus_{i = 1}^ra_i)\] 所以我们维护一个异或前缀和\(sum_i\) 我们用\(l_i\)表示从左往右到第\(i\)位时的区间最大异或和 \(r_i\)表示从右往左到第\(i\)位时的区间最大异或和 显然\(l_i = max\{sum_L\oplus sum_R\}1\leq L<R\...

题目： P3121 [USACO15FEB]审查（黄金）Censoring (Gold) 解析： 多字符串匹配，首先想到AC自动机 建立一个AC自动机 因为有删除和拼接这种操作，考虑用栈维护 顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走 我们再维护一个pos数组，用来维护trie树中节点对应在文本串中的位置 代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, num; int sta[N], pos[N]; char ...

题目 The XOR Largest Pair 解析 一年前听学长讲这道题，什么01trie，好高级啊，所以没学，现在一看。。。。 看到xor就应该想到二进制，一看数据\(A_i< 2^{31}\)，考虑把所有的数都处理成长度为32的二进制数，插入字典树中，查询的时候就逐位比较，有不同的先走不同的那边，这样保证了每次插入一个数时查询的结果是最大的，然后不断更新最大值就可以了 我这种不用位运算的懒人就直接用bitset维护了 从高位到地位插入可能好算一些 代码 #include <bits/stdc++.h> using namespace std; const int N =...