Home Archives Tags Friends About
杂题
2025-05-20

manual 是 anual 的 m 词形式（胡言乱语）

Everyone is potential. （每个人都是蛋白质。）

CF2043E Matrix Transformation

https://codeforces.com/problemset/problem/2043/E

给定 \(n\times m\) 的 \(01\) 矩阵 \(A,B\)，可任意将 \(A\) 的一行置为 \(0\) 或一列置为 \(1\)，问是否能将 \(A\) 变成 \(B\)。

发现如果 \(B\) 的某一行是 \(0\)，那么不管 \(A\) 这一行是什么东西都可以通过一次操作让这一行满足条件（当然，要求这步操作最后进行）。列也是相似的。

那么就有一个撤销的思路，从 \(B\) 中不断删除全 \(0\) 行或全 \(1\) 列，不能删了就对比二者剩下的部分是否全等（因为此时任何操作都是非法的）。

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int T;
    for (std::cin >> T; T--; ) {
        int n, m;
        std::cin >> n >> m;
        using arr = std::vector<int>;
        using brr = std::vector<arr>;
        using crr = std::vector<brr>;
        brr cn(31, arr(n + 1)), cm(31, arr(m + 1));
        crr a(31, brr(n + 1, arr(m + 1))), b(31, brr(n + 1, arr(m + 1)));
        for (int i = 1; i <= n; ++i)
            for (int j = 1, x; j <= m; ++j) {
                std::cin >> x;
                for (int k = 0; k < 31; ++k)
                    a[k][i][j] = (x >> k) & 1;
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1, x; j <= m; ++j) {
                std::cin >> x;
                for (int k = 0; k < 31; ++k) {
                    b[k][i][j] = (x >> k) & 1;
                    cn[k][i] += b[k][i][j];
                    cm[k][j] += !b[k][i][j];
                }
            }
        for (int k = 0; k < 31; ++k) {
            std::queue<int> qn, qm;
            std::vector<int> tn(n + 1, 1), tm(m + 1, 1);
            for (int i = 1; i <= n; ++i)
                if (!cn[k][i])
                    tn[i] = 0, qn.push(i);
            for (int j = 1; j <= m; ++j)
                if (!cm[k][j])
                    tm[j] = 0, qm.push(j);
            for (; !qn.empty() || !qm.empty(); ) {
                if (!qn.empty()) {
                    int i = qn.front();
                    // printf("delete line %d\n", i);
                    qn.pop();
                    for (int j = 1; j <= m; ++j)
                        if (!b[k][i][j] && !--cm[k][j])
                            tm[j] = 0, qm.push(j);
                }
                else {
                    int j = qm.front();
                    // printf("delete column %d\n", j);
                    qm.pop();
                    for (int i = 1; i <= n; ++i)
                        if (b[k][i][j] && !--cn[k][i])
                            tn[i] = 0, qn.push(i);
                }
            }
            for (int i = 1; i <= n; ++i)
                if (tn[i])
                    for (int j = 1; j <= m; ++j)
                        if (tm[j] && a[k][i][j] != b[k][i][j]) {
                            // printf("k = %d: (%d, %d)\n", k, i, j);
                            goto nosol;
                        }
        }
        std::cout << "Yes\n";
        continue;
    nosol :
        std::cout << "No\n";
    }
    return 0;
}

CF2043F Nim

https://codeforces.com/contest/2043/problem/F

给定 \(m\) 次询问，每次问从 \(a_l\sim a_r\) 选非空子序列使得异或和为 \(0\)，问子序列最小长度、该前提下的方案数。

发现子序列问题可以等价为背包；背包可以合并（即把整区间拆成若干段后，两两信息可以合并）；背包可以放在分治上；

由此，把询问离线下来放在 \(a_{1\sim n}\) 的分治上，每次只处理在 \([l,r]\) 间且跨越 \(mid\) 的询问就可以得到答案。复杂度 \(O(n\cdot v^2\log n)\)。

不要用方案数是否为 \(0\) 来判断是否无解！因为方案数可能是 \(998244353\) 的倍数……

#include <bits/stdc++.h>
const int siz = 63;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    struct _ { int l, r, id; };
    std::vector<_> q(m + 1);
    std::vector<std::pair<int, long long> > res(m + 1, { inf, 0ll });
    for (int i = 1; i <= m; ++i) {
        std::cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    std::function<void(int, int, std::vector<_> &q)> calc = [&](int l, int r, std::vector<_> &q) {
        if (l == r) {
            for (auto [l, r, id] : q)
                if (a[l] == 0)
                    res[id] = { 0, 1ll };
            return;
        }
        int mid = (l + r) >> 1;
        std::vector<_> ql, qr, qm;
        for (; !q.empty(); q.pop_back()) {
            if (q.back().r <= mid)
                ql.push_back(std::move(q.back()));
            else if (q.back().l > mid)
                qr.push_back(std::move(q.back()));
            else
                qm.push_back(std::move(q.back()));
        }
        calc(l, mid, ql), calc(mid + 1, r, qr);
        std::vector<std::vector<int> > f(r - l + 1, std::vector<int> (siz + 1, inf));
        std::vector<std::vector<long long> > g(r - l + 1, std::vector<long long> (siz + 1));
        f[mid - l][a[mid]] = 1ll, g[mid - l][a[mid]] = 1ll;
        for (int i = mid - l - 1; ~i; --i) {
            int k = a[i + l];
            f[i] = f[i + 1], g[i] = g[i + 1];
            if (f[i][k] == 1)
                (++g[i][k]) %= mod;
            else
                f[i][k] = 1, g[i][k] = 1ll;
            for (int j = 0, k = a[i + l]; j <= siz; ++j)
                if (f[i + 1][j ^ k] + 1 < f[i][j])
                    f[i][j] = f[i + 1][j ^ k] + 1, g[i][j] = g[i + 1][j ^ k];
                else if (f[i + 1][j ^ k] + 1 == f[i][j])
                    (g[i][j] += g[i + 1][j ^ k]) %= mod;
        }
        f[mid - l + 1][a[mid + 1]] = 1ll, g[mid - l + 1][a[mid + 1]] = 1ll;
        for (int i = mid - l + 2; i <= r - l; ++i) {
            int k = a[i + l];
            f[i] = f[i - 1], g[i] = g[i - 1];
            if (f[i][k] == 1)
                (++g[i][k]) %= mod;
            else
                f[i][k] = 1, g[i][k] = 1ll;
            for (int j = 0; j <= siz; ++j)
                if (f[i - 1][j ^ k] + 1 < f[i][j])
                    f[i][j] = f[i - 1][j ^ k] + 1, g[i][j] = g[i - 1][j ^ k];
                else if (f[i - 1][j ^ k] + 1 == f[i][j])
                    (g[i][j] += g[i - 1][j ^ k]) %= mod;
        }
        for (auto [ql, qr, id] : qm) {
            // printf("at [%d, %d], mid = %d: ASK [%d, %d]: \n", l, r, mid, ql, qr);
            ql -= l, qr -= l;
            if (f[ql][0] < inf)
                res[id].first = f[ql][0], res[id].second = g[ql][0];
            if (f[qr][0] < res[id].first)
                res[id].first = f[qr][0], res[id].second = g[qr][0];
            else if (f[qr][0] == res[id].first)
                (res[id].second += g[qr][0]) %= mod;
            for (int i = 1; i <= siz; ++i) {
                // printf("  %d[%d]: %d(%lld)  |  %d[%d]: %d(%lld)\n", ql + l, i, f[ql][i], g[ql][i], qr + l, i, f[qr][i], g[qr][i]);
                if (f[ql][i] + f[qr][i] < res[id].first)
                    res[id].first = f[ql][i] + f[qr][i], res[id].second = g[ql][i] * g[qr][i] % mod;
                else if (f[ql][i] + f[qr][i] == res[id].first)
                    (res[id].second += g[ql][i] * g[qr][i]) %= mod;
            }
            if (res[id].first < inf)
                res[id].first = (qr - ql + 1) - res[id].first;
        }
        return;
    };
    calc(1, n, q);
    for (int i = 1; i <= m; ++i)
        if (res[i].first < inf)
            std::cout << res[i].first << ' ' << res[i].second << '\n';
        else
            std::cout << -1 << '\n';
    return 0;
}

贪玩蓝月

https://loj.ac/p/6515

差不多的题：https://atcoder.jp/contests/jag2018summer-day2/tasks/jag2018summer_day2_d，注意加入是按体积单增的

发现断点确定时可以背包 \(O(p)\) 维护插入删除；使用 双栈模拟双端队列 就可以均摊 \(O(pm)\) 实现插入删除。

对于询问，当然可以 \(O(p^2)\) 枚举最值再枚举方案（即枚举一端的贡献）；但复杂度不太美观。考虑倒过来，先 \(O(v)\) 枚举一端贡献，再枚举『能凑出 \([l,r]\) 中的值』的另一端的贡献。这样就发现我们是在求区间最大值；每次询问时构建 ST 表预处理另一端的区间最大值即可。

复杂度 \(O(mq\log q)\)。

#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int m, mod;
    std::cin >> m >> m >> mod;
    std::array<std::vector<std::pair<int, int> >, 2> T;
    std::array<std::vector<std::vector<long long> >, 2> F;
    F[0].emplace_back(mod, -inf), F[1].emplace_back(mod, -inf);
    F[0][0][0] = 0ll, F[1][0][0] = 0ll;
    for (; m--; ) {
        std::string op;
        std::cin >> op;
        if (op[0] == 'I') {
            int v, w;
            std::cin >> v >> w, v %= mod;
            auto &t = T[op[1] == 'G'];
            auto &f = F[op[1] == 'G'];
            t.emplace_back(v, w);
            f.emplace_back(f.back());
            for (int i = (int)f.size() - 1, j = 0; j < mod; ++j)
                if (f[i - 1][(j + mod - v) % mod] + w > f[i][j])
                    f[i][j] = f[i - 1][(j + mod - v) % mod] + w;
        }
        else if (op[0] == 'D') {
            auto &t0 = T[op[1] == 'G'], &t1 = T[op[1] == 'F'];
            auto &f0 = F[op[1] == 'G'], &f1 = F[op[1] == 'F'];
            if (t0.empty()) {
                t1.erase(t1.begin());
                int to = t1.size() / 2;
                std::vector<std::pair<int, int> > (t1.begin(), t1.begin() + to).swap(t0);
                std::reverse(t0.begin(), t0.end());
                std::vector<std::pair<int, int> > (t1.begin() + to, t1.end()).swap(t1);
                f0.resize(1), f1.resize(1);
                for (auto [v, w] : t0) {
                    f0.emplace_back(f0.back());
                    for (int i = (int)f0.size() - 1, j = 0; j < mod; ++j)
                        if (f0[i - 1][(j + mod - v) % mod] + w > f0[i][j])
                            f0[i][j] = f0[i - 1][(j + mod - v) % mod] + w;
                }
                for (auto [v, w] : t1) {
                    f1.emplace_back(f1.back());
                    for (int i = (int)f1.size() - 1, j = 0; j < mod; ++j)
                        if (f1[i - 1][(j + mod - v) % mod] + w > f1[i][j])
                            f1[i][j] = f1[i - 1][(j + mod - v) % mod] + w;
                }
            }
            else
                t0.pop_back(), f0.pop_back();
        }
        else {
            int l, r;
            std::cin >> l >> r;
            auto res(-inf);
            std::vector<std::vector<long long> > st(std::__lg(mod) + 1, std::vector<long long> (mod + 1));
            st[0] = F[1].back();
            for (int j = 1; (1 << j) <= mod; ++j)
                for (int i = 0; i + (1 << j) - 1 < mod; ++i)
                    st[j][i] = std::max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            auto ask = [&](int l, int r) {
                int k = std::__lg(r - l + 1);
                return std::max(st[k][l], st[k][r - (1 << k) + 1]);
            };
            for (int j = 0; j < mod; ++j)
                if (j <= l)
                    res = std::max(res, F[0].back()[j] + ask(l - j, r - j));
                else if (l < j && j <= r)
                    res = std::max({ res, F[0].back()[j] + ask(0, r - j), F[0].back()[j] + ask(l + mod - j, mod - 1) });
                else
                    res = std::max(res, F[0].back()[j] + ask(l + mod - j, r + mod - j));
            std::cout << std::max(-1ll, res) << '\n';
        }
    }
    return 0;
}

APIO2025 转杆

https://www.luogu.com.cn/problem/P12543

总有一天我要让全天下的数学题 DP 题字符串题图论题模拟题数据结构题思维题全部消失

不要把它转化成序列问题来考虑！这对观察到结论没有好处！

考虑 \(n=2\) 的情况，当且仅当垂直时最优。\(n=3\) 时，随便固定其中一条线，发现剩下两条线如果夹角固定，则代价固定；当夹角取 \(90^{\circ}\) 时最优。

于是猜是不是任意一对都要垂直。考虑数归，当前 \(2n\) 对 不知道怎么摆的，反正就是 最优时：

  • 考虑加入第 \(2n+1\) 条；参照 \(n=3\) 的情形，把前 \(2n\) 条任意两两配对，则第 \(2n+1\) 的位置对代价没有任何影响。
  • 考虑加入第 \(2n+2\) 条；相似地，它的位置对前 \(2n\) 条没有任何影响；故需要最大化它和第 \(2n+1\) 条的贡献。取垂直即可。

因此得到任意一对都要垂直。具体怎么调整呢？首先下意识排序；配对方式即将 \(i\) 与 \(\dfrac i+\lfloor \frac n2\rfloor\) 配对；因为能感受到这样影响的线段最少。严谨的证明好像没看到。

#include<bits/stdc++.h>
void energy(int, std::vector<int>);
void rotate(std::vector<int>, int);
void energy(int n, std::vector<int> a) {
    std::vector<int> id(n);
    std::iota(id.begin(), id.end(), 0);
    std::sort(id.begin(), id.end(), [&](int x, int y) { return a[x] < a[y]; });
    for (int i = 0, j = n / 2; i < n / 2; ++i, ++j)
        rotate({ id[j] }, (a[id[i]] + 75000 - a[id[j]]) % 50000);
    return;
}

ABC407E Most Valuable Parentheses

https://atcoder.jp/contests/abc407/tasks/abc407_e

这里有一个很典（可惜我不知道）的 trick：贪心构造最优括号序列。

用优先队列维护，贪心选即可。

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int T;
    for (std::cin >> T; T--; ) {
        int n;
        std::cin >> n;
        std::vector<int> a(2 * n + 1);
        for (int i = 1; i <= 2 * n; ++i)
            std::cin >> a[i];
        long long res = a[1];
        std::priority_queue<int> q;
        for (int i = 2; i < 2 * n; i += 2) {
            q.push(a[i]), q.push(a[i + 1]);
            res += q.top(), q.pop();
        }
        std::cout << res << '\n';
    }
    return 0;
}

言论