AcWing 每日一题 - Summer

本篇解题记录题源来自 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;
}

AcWing 每日一题 - Summer

原文：https://www.cnblogs.com/RioTian/p/14761145.html