本篇解题记录题源来自 AcWing 的 Summer 每日一题
补题链接：Here
Week 1
星期一 AcWing 3485. 最大异或和 （Hard
思路
先求出前i个数的异或和sum[i]，再在大小为m的滑动窗口内进行trie.
- \(\mathcal{O}(nlog\ n)\)
int n, m;
const int N = 31e5 + 10; //最多有n*31
int p[N][35], ct[N], idx; //ct[n]的作用是标记滑动窗口内0，1的数量
int sum[100010]; //sum[i]存前i个数的异或和
void insertt(int u, int c) {
int t = 0;
for (int i = 30; i >= 0; i--) {
int x = u >> i & 1;
if (!p[t][x]) {
p[t][x] = ++idx;
}
t = p[t][x];
ct[t] += c; //标记这里（有或删除）一个数可以达到该位置
}
}
int query(int u) {
int t = 0;
int res = u;
for (int i = 30; i >= 0; i--) {
int x = u >> i & 1;
if (ct[p[t][!x]] > 0) { //当x对面的那个数！x存在时(0,1)
x = (x + 1) % 2; //x就变成另外一个数 !x
}
res ^= x << i;
t = p[t][x];
}
return res;
}
void solve() {
cin >> n >> m;
int t;
for (int i = 1; i <= n; i++) {
cin >> t;
sum[i] = sum[i - 1] ^ t; //sum[i]表示前i个数的^
}
insertt(0, 1); //插入0，是为了方便前m个数进行异或得出的答案可以是它本身的值
int res = 0; //求最大值
for (int i = 1; i <= n; i++) {
if (i > m) insertt(sum[i - m - 1], -1); //将滑动窗口外的数除去，这时就要修改ct，故-1
res = max(res, query(sum[i])); //在滑动窗口内求最大值
insertt(sum[i], 1); //求完后记得插入该值，方便后面的值进行异或
}
cout << res;
}
星期二 AcWing 3493. 最大的和 （Easy
对于 \(30\%\) 数据，可以开两重 for 循环暴力找
但在 \(100\%\) 数据里肯定会 T
所以要用前缀和进行优化 （当然也可以用队列优化，这里就不展开了，贴一个讲解链接
- \(\mathcal{O}(n)\)
using ll = long long;
const int N = 1e5 + 10;
ll a[N], s[N];
ll st[N];
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
ll sum = 0;
for (int i = 1; i <= n; ++i) {
cin >> st[i];
if (st[i]) s[i] += s[i - 1], sum += a[i]; // 如果是 st[i] = 1 的情况说明直接就可选，sum 累加即可
else
s[i] = s[i - 1] + a[i]; // 需要转换状态的话则要利用前缀和累加了
}
ll res = 0;
for (int i = k; i <= n; ++i) res = max(res, s[i] - s[i - k]);
cout << res + sum;
}