暑期cspj模拟赛6

#T1 双重循环暴力

#T2 dfs暴力

#T3

#include <bits/stdc++.h>
using namespace std;

const int MAX_BIT = 30; // 覆盖0~1e9的二进制位（最多30位）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("seq.in", "r", stdin);
    // freopen("seq.out", "w", stdout);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 预处理每一位的前缀和：bit_prefix[k][i]表示前i个元素（0~i-1）中第k位为1的数量
    vector<vector<int>> bit_prefix(MAX_BIT, vector<int>(n + 1, 0));
    for (int k = 0; k < MAX_BIT; ++k) {
        for (int i = 0; i < n; ++i) {
            bit_prefix[k][i + 1] = bit_prefix[k][i] + ((a[i] >> k) & 1);
        }
    }

    int or_mask = 0; // 全局按位或标记，记录所有操作1的累积结果

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            or_mask |= x; // 累积按位或操作
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--; // 转换为0-based索引，方便数组访问

            long long sum = 0;
            for (int k = 0; k < MAX_BIT; ++k) {
                int mask_bit = (or_mask >> k) & 1;
                if (mask_bit) {
                    // 该位最终为1，贡献 = 区间长度 × (1 << k)
                    sum += 1LL * (r - l + 1) * (1 << k);
                } else {
                    // 该位最终为1的数量 = 初始该位为1的数量
                    int cnt = bit_prefix[k][r + 1] - bit_prefix[k][l];
                    sum += 1LL * cnt * (1 << k);
                }
            }
            cout << sum << '\n';
        }
    }

    return 0;
}

#T4 先用整体折半搜索算出全部的方案数,然后再在单个店内算出方案数,做差值

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;

long long n,m,k;
vector<long long > a[64];

int scnt1,scnt2;
long long sum1[1100000],sum2[1100000];


void dfs1(int vidx,int start,int end,long long tot) {
    if (start > end) {
        sum1[++scnt1] = tot;
        return;
    }
    dfs1(vidx,start+1,end,tot);
    dfs1(vidx,start+1,end,tot+a[vidx][start-1]);
}

void dfs2(int vidx,int start,int end,long long tot) {
    if (start > end) {
        sum2[++scnt2] = tot;
        return;
    }
    dfs2(vidx,start+1,end,tot);
    dfs2(vidx,start+1,end,tot+a[vidx][start-1]);
}



long long solve(int vidx) {
    scnt1 = scnt2 = 0;
    dfs1(vidx,1,a[vidx].size() / 2,0);
    dfs2(vidx,a[vidx].size() / 2+1,a[vidx].size(),0);
    sort(sum1+1,sum1 + scnt1+1);
    sort(sum2+1,sum2 + scnt2+1);
    long long res = 0;
    int l = 1,r = scnt2;
    while (l <= scnt1 && r >= 1) {
        if (sum1[l] + sum2[r] >= k) {
            res += scnt1 - l + 1;
            r--;
        } else {
            l++;
        }
    }
    // 这里要减去一个，因为k == 0的时候，0也会被算进去
    return res - (k == 0);

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
      long long x,y;
        cin >> x >> y;
        a[y] .push_back(x);
        a[0].push_back(x);
    }

    long long ans = solve(0);
    for (int i = 1; i <= m; ++i) {
        if (a[i].size() == 0) {
            continue;
        }
        ans -= solve(i);
    }

    cout << ans << endl;
    return 0;
}