AtCoder Beginner Contest 366

D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥


int a[N][N][N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i][j][k - 1];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i][j - 1][k];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i - 1][j][k];
            }
        }
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        int res = a[x2][y2][z2] - a[x1 - 1][y2][z2] - a[x2][y1 - 1][z2] -
                  a[x2][y2][z1 - 1] + a[x1 - 1][y1 - 1][z2] +
                  a[x1 - 1][y2][z1 - 1] + a[x2][y1 - 1][z1 - 1] - a[x1 - 1][y1 - 1][z1 - 1];
        cout<<res<<endl;
    }
}

E.给你一个二维平面上的 $N$ 点 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ 和一个非负整数 $D$ 。求 $(x, y)$ 使得 $\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D$ 的整数对的个数。

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq D \leq 10^6$
  • $-10^6 \leq x_i, y_i \leq 10^6$
  • $(x_i, y_i) \neq (x_j, y_j)$ for $i \neq j$.
  • All input values are integers.

Sol:考虑横纵坐标显然独立，根据数据范围我们可以枚举一维，快速查询另一维。我们需要快速得到的是一个一维的点到n个点的绝对值距离之和，这在曼哈顿距离专题是很典的东西，我们只需要提前计算前缀和，查询的时候二分即可。此时我们还需要处理另一维，同样也可以继续二分，显然绝对值求和这个式子关于y是凹函数，但这样需要讨论并且左右两次二分比较麻烦。

  • 对于求<=val的值的个数，如果val不大，我们可以先求等于val的数量，然后求一遍前缀和就可以了

左右两次二分的代码：

void solve() {
    cin >> n >> m;
    vector<int> vx(n + 1), vy(n + 1);
    for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];
    //  deb(vx);
    // deb(vy);
    sort(alls(vx));
    sort(alls(vy));
    vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
    for (int i = 1; i <= n; i++) {
        prex[i] += vx[i] + prex[i - 1];
        prey[i] += vy[i] + prey[i - 1];
    }
    for (int i = n; i >= 1; i--) {
        sufx[i] += vx[i] + sufx[i + 1];
        sufy[i] += vy[i] + sufy[i + 1];
    }
    deb(vx);
    deb(prex);
    deb(sufx);
    deb(vy);
    deb(prey);
    deb(sufy);
    int ans = 0;
    for (int x = -2e6; x <= 2e6; x++) {
        auto it = lower_bound(alls(vx), x);
        int tmp = 0;
        if (it == vx.end()) {
            tmp = n * x - prex[n];
        } else {
            int cnt = it - vx.begin() - 1;
            tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
        }

        int you = m - tmp;
        if (you < 0)
            continue;
        deb(x, tmp, you);
        auto check = [&](int y) {
            auto it = lower_bound(alls(vy), y);
            int val = 0;
            if (it == vy.end()) {
                val = n * y - prey[n];
            } else {
                int cnt = it - vy.begin() - 1;
                val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
            }
            return val <= you;
        };

        int st = vy[(n + 1) / 2];
        if (check(st) == 0)
            continue;
        int l = st, r = 2e6;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        deb(st, r);
        ans += r - st + 1;
       // int ql = l;
        l = -2e6, r = st;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        deb(l, st);
        ans += st - l + 1;
       // int qr = r;
        ans -= 1;
        // auto cal=[&](int cx,int cy){
        //     int res=0;
        //     for(int i=1;i<=n;i++){
        //         res+=abs(vx[i]-cx)+abs(vy[i]-cy);
        //     }
        //     return res;
        // };
        // for(int i=ql;i<=qr;i++){
        //     //cerr<<"**************************"<<endl;
        //     int res=cal(x,i);
        //     if(res>m){ cerr<<"**************************"<<endl;deb("acm!!!",x,i,res);}
        // }
    }
    cout << ans << endl;
}

利用trick的代码：

void solve() {
    cin >> n >> m;
    vector<int> vx(n + 1), vy(n + 1);
    for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];

    sort(alls(vx));
    sort(alls(vy));
    vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
    for (int i = 1; i <= n; i++) {
        prex[i] += vx[i] + prex[i - 1];
        prey[i] += vy[i] + prey[i - 1];
    }
    for (int i = n; i >= 1; i--) {
        sufx[i] += vx[i] + sufx[i + 1];
        sufy[i] += vy[i] + sufy[i + 1];
    }
    int ans = 0;
    auto check = [&](int y) {
        auto it = lower_bound(alls(vy), y);
        int val = 0;
        if (it == vy.end()) {
            val = n * y - prey[n];
        } else {
            int cnt = it - vy.begin() - 1;
            val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
        }
        return val;
    };
    vector<int> cnt(1e6 + 5);
    for (int i = -2e6; i <= 2e6; i++) {
        int res = check(i);
        if (res <= 1e6)
            cnt[res]++;
    }
    for (int i = 1; i <= 1e6; i++) cnt[i] += cnt[i - 1];
    for (int x = -2e6; x <= 2e6; x++) {
        auto it = lower_bound(alls(vx), x);
        int tmp = 0;
        if (it == vx.end()) {
            tmp = n * x - prex[n];
        } else {
            int cnt = it - vx.begin() - 1;
            tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
        }

        int you = m - tmp;
        if (you < 0)
            continue;

        ans += cnt[you];
    }
    cout << ans << endl;
}

F.给你 $N$ 个线性函数 $f_1, f_2, \ldots, f_N$ ，其中 $f_i(x) = A_i x + B_i$ .从N个中选k个函数并进行复合，求由 $K$ 组成的序列 $p = (p_1, p_2, \ldots, p_K)$ 中 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ 的最大可能值。

Constraints

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq K \leq \text{min}(N,10)$
  • $1 \leq A_i, B_i \leq 50$ $(1 \leq i \leq N)$
  • All input values are integers.

Sol：不难想到一个可能是一个$O(nk)$的dp，先贪心考虑这个问题怎么最优，发现可以用交换法推公式，然后按某种标准排序，也就是内层嵌套的顺序是存在调整优化空间的。我们认为按照这个标准排序后,$f_{j}(f_{i}(suf))<f_{i}(f_{j}(suf))(i<j)$。所以我们只有先确定内层的情况，才能求出外层，所以需要倒着dp。$dp[i][j]$表示当前考虑i-n这些位置选了j个函数，转移考虑选与不选即可。

bool cmp(pii c, pii d) {
    return c.sec * (1 - d.fs) > d.sec * (1 - c.fs);
}
void solve() {
    cin >> n >> m;
    vector<pii> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i].fs >> v[i].sec;
    sort(v.begin() + 1, v.end(), cmp);
    int k = min(10LL, m);
    vector<vector<int>> dp(n + 2, vector<int>(k + 1, 0));
    dp[n+1][0]=1;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = dp[i + 1][j];
            if(j)dp[i][j] = max(dp[i][j], v[i].fs * dp[i + 1][j - 1] + v[i].sec);
        }
    }
    cout<<dp[1][k]<<endl;
}

G.给你一个简单的无向图，图中有 $N$ 个顶点和 $M$ 条边。 $i$ -th 边双向连接顶点 $u_i$ 和 $v_i$ 。给出构造：每个点赋值点权，要求满足：

  • 对于出度至少为 $1$ 的每个顶点 $v$ ，写在其相邻顶点上的数字（不包括 $v$ 本身）的总 XOR 为 $0$ 。

Constraints

  • $1 \leq N \leq 60$
  • $0 \leq M \leq N(N-1)/2$
  • $1 \leq u_i < v_i \leq N$
  • $(u_i, v_i) \neq (u_j, v_j)$ for $i \neq j$.
  • All input values are integers.

Sol:考虑高斯消元解异或方程组,本题特殊之处在于:对于无穷多解的情况需要输出构造一种非零解(这里特指每个变量都不为0).考虑为自由变量赋正整数值,且尽可能异或不为0.

int gauss(vector<vector<int>>& a, int n, vector<int>& solution) {
    vector<int> freevar;           // 记录自由变量对应的列
    vector<int> pivot(n + 1, -1);  // 记录每一行的主元所在的列
    solution.assign(n + 1, 0);
    int r = 1;
    for (int c = 1; c <= n; c++) {
        int t = r;
        // 找到当前列中的主元
        for (int i = r; i <= n; i++) {
            if (a[i][c]) {
                t = i;
                break;
            }
        }
        if (!a[t][c]) {
            freevar.push_back(c);
            continue;  // 当前列没有主元，继续到下一列
        }
        pivot[r] = c;  // 第 r 行的主元在 c 列
        if (t != r) {  // 交换行，将主元行放在第 r 行
            for (int i = c; i <= n + 1; i++)
                swap(a[r][i], a[t][i]);
        }
        // 消去主元下方的所有行
        for (int i = r + 1; i <= n; i++) {
            if (a[i][c])
                for (int j = n + 1; j >= c; j--) a[i][j] ^= a[r][j];
        }
        r++;
    }

    // 检查是否有解
    for (int i = r; i <= n; i++) {
        if (a[i][n + 1])
            return 0;  // 无解
    }
    int tot = 0;
    int rksz = r - 1;  // 这是系数矩阵的秩
    // 自由变量根据题目要求情况去赋值
    for (auto i : freevar) solution[i] = 1LL << tot, tot++;
    //------------------------------
    for (int i = rksz; i >= 1; i--) {
        int sum = a[i][n + 1];
        for (int j = 1; j <= n; j++) {
            if (j == pivot[i]) {
                continue;
            }  // 如果不是主元所在的列
            sum ^= (a[i][j] * solution[j]);  // 右边已经求出来的，左边自由变量遗留
        }
        solution[pivot[i]] = sum;  // 求解对应的主元变量
    }
    assert(rksz <= n);
    if (rksz < n)
        return 2;  // 无穷多解
    return 1;      // 唯一解
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector b(n + 1, vector<int>(n + 2));
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        b[u][v] = b[v][u] = 1;
    }
    vector<int> sol(n + 1);
    int t = gauss(b, n, sol);
    if (t == 0)
        cout << "No" << endl;
    else {
        for (int i = 1; i <= n; i++)
            if (sol[i] < 1) {
                cout << "No" << endl;
                return;
            }
        cout << "Yes" << endl;
        for (int i = 1; i <= n; i++) cout << sol[i] << " ";
    }
}