中等题目 Practice

2025-02-22

暂无标签

看似日期是 22/02/2025，实际上正文的第一个字直到 27/11/2025 才落下来

Colorful Segments

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

出现了线段和方案数要素，是很显然的线段树优化 DP
先按左端点排序
记 \(f_{i,0/1}\) 为，最右侧的右端点为 \(i\)，且颜色为 \(0/1\) 的方案数，那么对于一条线段 \((l,r,0)\) 有转移：

\[ f_{\max(i,r),0}\gets f_{i,0}\\ f_{r,0}\gets f_{i,1} \quad (i<l) \]

分类讨论 max 的取值情况，线段树优化即可。
p.s. 发现此处可以离散化，（虽然并不需要），需要注意区间问题离散化时，只需要离散化左闭右开的两个点，就只有二倍常数了。

#include <bits/stdc++.h>
#define int long long
const int maxn = 2e5 + 5;
const int mod = 998244353;
struct { int l, r; long long u[2], d[2]; } t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
    t[p].u[0] = t[p].u[1] = 0;
    t[p].d[0] = t[p].d[1] = 1ll;
    t[p].l = l, t[p].r = r;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    bld(lt, l, mid), bld(rt, mid + 1, r);
    return;
}
int add(int x, int v) {
    if ((x += v) >= mod)
        x -= mod;
    return x;
}
void pushval(int p, int d0, int d1) {
    (t[p].d[0] *= d0) %= mod;
    (t[p].d[1] *= d1) %= mod;
    (t[p].u[0] *= d0) %= mod; // 一开始 u 开成 int 爆炸了，检查了半天没检查到这里
    (t[p].u[1] *= d1) %= mod; // Luogu 你什么时候能出 Diagnostics？
    return;
}
void pushdown(int p) {
    pushval(lt, t[p].d[0], t[p].d[1]);
    pushval(rt, t[p].d[0], t[p].d[1]);
    t[p].d[0] = t[p].d[1] = 1ll;
    return;
}
void add(int p, int x, int k, int v) {
    t[p].u[k] = add(t[p].u[k], v);
    assert(t[p].u[k] < mod);
    if (t[p].l == t[p].r)
        return;
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid)
        add(lt, x, k, v);
    else
        add(rt, x, k, v);
    return;
}
void upd(int p, int l, int r, int k) {
    if (l <= t[p].l && t[p].r <= r) {
        if (k == 0)
            pushval(p, 2, 1);
        else
            pushval(p, 1, 2);
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        upd(lt, l, r, k);
    if (r > mid)
        upd(rt, l, r, k);
    t[p].u[0] = add(t[lt].u[0], t[rt].u[0]);
    t[p].u[1] = add(t[lt].u[1], t[rt].u[1]);
    assert(t[p].u[0] < mod);
    assert(t[p].u[1] < mod);
    return;
}
int ask(int p, int l, int r, int k) {
    if (l <= t[p].l && t[p].r <= r)
        return t[p].u[k];
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1, res = 0;
    if (l <= mid)
        res = ask(lt, l, r, k);
    if (r > mid)
        res = add(res, ask(rt, l, r, k));
    assert(res < mod);
    return res;
}
#undef lt
#undef rt
signed 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);
    auto stime = std::chrono::steady_clock::now();
#endif
    int T;
    for (std::cin >> T; T--; ) {
        int n;
        std::cin >> n;
        struct node { int l, r, c; };
        std::vector<int> l(1);
        std::vector<node> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i].l >> a[i].r >> a[i].c;
            l.push_back(a[i].l), l.push_back(++a[i].r);
        }
        std::sort(l.begin() + 1, l.end());
        l.erase(std::unique(l.begin() + 1, l.end()), l.end());
        int m = (int)l.size() - 1;
        for (int i = 1; i <= n; ++i) {
            a[i].l = std::lower_bound(l.begin() + 1, l.end(), a[i].l) - l.begin();
            a[i].r = std::lower_bound(l.begin() + 1, l.end(), a[i].r) - l.begin() - 1;
        }
        std::sort(a.begin() + 1, a.end(), [&](node &x, node &y) { return x.l < y.l; });
        bld(1, 0, m), add(1, 0, 0, 1);
        for (int i = 1; i <= n; ++i) {
            add(1, a[i].r, a[i].c, add(ask(1, 0, a[i].r, a[i].c), ask(1, 0, a[i].l - 1, !a[i].c)));
            upd(1, a[i].r + 1, m, a[i].c);
        }
        std::cout << add(t[1].u[0], t[1].u[1]) << '\n';
    }
#ifndef ONLINE_JUDGE
    std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
    return 0;
}

Bardzo Ulubiony Ciąg

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

忽略无序、不重的条件，怎么统计这样的三元组？

考虑前缀和 + 差分，相当于选出六个点，前三个点和后三个的和相等，只需要枚举一次三元组，装到桶里，再枚举一次即可。
但是满足 \(l\le r\) 似乎十分困难！这里的处理方法是，把 \((l_1, r_1, l_2)\) 丢进桶，这样限制就从三个减少成了一个，就可以前缀和优化了。
关于去重，参考 BZOJ 3771 的容斥，钦定至少相等的区间个数即可。

对于形如 \((i,i,i)\) 的三元组，找 0 区间个数即可。

对于形如 \((i,i,j)\) 的三元组，直接桶计即可。~~好冷的谐音梗~~
关于这里消序的问题：

A 无序，B 无序，C 有序，但 C 中 A 无序，B 部分有序，最后要求无序。

让 C 减去无序的 A 和部分有序化的 B 再消序即可。这么说来所有让人困惑的消序问题其实都长这样。

#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);
    auto stime = std::chrono::steady_clock::now();
#endif
    int n;
    std::cin >> n;
    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> s[i], s[i] += s[i - 1];
    const int Mb = 2e7, Mc = 3e7;
    std::vector<int> b1(2 * Mb + 1), b2(2 * Mb + 1), c(2 * Mc + 1);
    auto A = 0ll, B = 0ll, C = 0ll;
    for (int l1 = 1; l1 <= n; ++l1) {
        for (int r1 = l1; r1 <= n; ++r1) {
            if (s[r1] - s[l1 - 1] == 0)
                ++A;
            B += b2[Mb - (s[r1] - s[l1 - 1])];
            B += b1[Mb - 2 * (s[r1] - s[l1 - 1])];
            ++b1[Mb + s[r1] - s[l1 - 1]], ++b2[Mb + 2 * (s[r1] - s[l1 - 1])];
        }
    }
    for (int l2 = 1; l2 <= n; ++l2) {
        for (int l1 = 1; l1 <= n; ++l1)
            for (int r1 = l1; r1 <= n; ++r1)
                ++c[Mc + s[r1] - s[l1 - 1] - s[l2 - 1]];
        for (int l3 = 1; l3 <= n; ++l3)
            for (int r3 = l3; r3 <= n; ++r3)
                C += c[Mc - s[l2] - s[r3] + s[l3 - 1]];
    }
    std::cout << (C - 3 * B - A) / 6 << '\n';
#ifndef ONLINE_JUDGE
    std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
    return 0;
}

Flip it and Stick it

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

\(|T|\le 3\)，结合数据范围，乍一看是分讨题，看看能不能直接分讨了
对于 \(|T|=1\)，check \(S\) 中是否含这个字符即可。
对于 \(|T|=2\) 且 \(T_1\ne T_2\)，check \(S\) 中是否有两种字符即可。
对于 \(|T|=2\) 且 \(T_1=T_2\)，发现有意义的 reverse 操作的两个端点，一定一个是 00 的中间，另一个是 11 的中间。

不妨假设 \(T\) 为 00，那么要求 11 的个数不少于 00 的个数 \(-1\)（\(S\) 最后形如 01010），答案为 00 个数。
对于 \(|T|=3\) 且 \(T_1\ne T_3\)，假设 \(T\) 为 001，发现只需要找到每一段 00000 + 11101011（即不包含连续 2 个 0），做 reverse 即可（第一段 0 需要大于等于 2）。

\(T\) 为 011 只需倒过来处理。
对于 \(|T|=3\) 且 \(T_1\ne T_2\)，假设 \(T\) 为 010，最后序列一定 0 在一边，1 在另一边。

一次 reverse 可以让段数减少 2，但序列首尾不一定相异，花一次 reverse 让这点成立即可。
otherwise，设 \(T\) 为 000，参考 00 的处理方式，发现一次 reverse 的价值是找一个 1 过来分段。

故最好情况下只需统计把所有连续 0 切成 \(\le 3\) 的段需要的 1 个数。

但当 1 不够用时反而需要对 0 进行合并，比如 1 的个数只能允许 \(a\) 个长度为 \(1\) 的 0 段出现，但序列中初始就有 \(>a\) 个长度为 \(1\) 的 0 段。这个时候只需要进行 0 的内部调剂，消耗的次数即为相比 \(a\) 多出的个数，然后再用 1 分段。

很容易发现因为每次操作的收益都是一样的，所以大概率是对的，就不实现了……

Painting Fence Posts S

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

笑话：2 月真的做过

经典套路：看看是本行 / 本列第奇数 / 偶数个点，看看应该往前还是往后连边
二分找到目标路径，看看顺时针还是逆时针走，剩下的就是正常前缀和维护了

实则大模拟，不再吃一遍了，直接贴 2 月的代码

今年二月的时候还不太喜欢封装，自己给自己找事了属于是

#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 n, m;
    std::cin >> m >> n;
    std::vector<int> l;
    struct __ { long long x, y; };
    std::vector<__> a(n + 1), b(1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i].x >> a[i].y;
        l.push_back(a[i].x);
        l.push_back(a[i].y);
        b.push_back(a[i]);
    }
    struct _ { long long sx, sy, tx, ty; };
    std::vector<_> q(m + 1);
    for (int i = 1; i <= m; ++i) {
        std::cin >> q[i].sx >> q[i].sy >> q[i].tx >> q[i].ty;
        l.push_back(q[i].sx), l.push_back(q[i].sy);
        l.push_back(q[i].tx), l.push_back(q[i].ty);
        b.push_back({ q[i].sx, q[i].sy });
        b.push_back({ q[i].tx, q[i].ty });
    }
    std::sort(l.begin() + 1, l.end());
    l.erase(std::unique(l.begin() + 1, l.end()), l.end());
    int tot = (int)l.size() - 1;
    std::vector<int> id(n + 2 * m + 1);
    std::vector<long long> dis(n + 2 * m + 2);
    std::vector<std::vector<std::pair<long long, int> > > gx(tot + 1), gy(tot + 1), ax(tot + 1), ay(tot + 1);
    for (int i = 1; i <= n; ++i) {
        a[i].x = std::lower_bound(l.begin() + 1, l.end(), a[i].x) - l.begin();
        a[i].y = std::lower_bound(l.begin() + 1, l.end(), a[i].y) - l.begin();
        gx[a[i].x].emplace_back(a[i].y, i);
        gy[a[i].y].emplace_back(a[i].x, i);
        ax[a[i].x].emplace_back(a[i].y, i);
        ay[a[i].y].emplace_back(a[i].x, i);
    }
    for (int i = 1; i <= m; ++i) {
        q[i].sx = std::lower_bound(l.begin() + 1, l.end(), q[i].sx) - l.begin();
        q[i].sy = std::lower_bound(l.begin() + 1, l.end(), q[i].sy) - l.begin();
        ax[q[i].sx].emplace_back(q[i].sy, n + 2 * i - 1);
        ay[q[i].sy].emplace_back(q[i].sx, n + 2 * i - 1);
        q[i].tx = std::lower_bound(l.begin() + 1, l.end(), q[i].tx) - l.begin();
        q[i].ty = std::lower_bound(l.begin() + 1, l.end(), q[i].ty) - l.begin();
        ax[q[i].tx].emplace_back(q[i].ty, n + 2 * i);
        ay[q[i].ty].emplace_back(q[i].tx, n + 2 * i);
    }
    for (int i = 1; i <= tot; ++i) {
        std::sort(gx[i].begin(), gx[i].end());
        std::sort(gy[i].begin(), gy[i].end());
        std::sort(ax[i].begin(), ax[i].end());
        std::sort(ay[i].begin(), ay[i].end());
    }
    int cnt = 0;
    long long sx = 0, sy = 0;
    std::vector<int> tab(n + 2 * m + 1);
    for (int i = 1; i <= tot; ++i)
        if (!ax[i].empty()) {
            sx = i, sy = ax[i].front().first;
            for (int j = 0; j < (int)ax[i].size() && ax[i][j].first == sy; ++j)
                id[ax[i][j].second] = ++cnt, tab[cnt] = ax[i][j].second;
            break;
        }
    auto getdis = [&](int i, int j) {
        return std::abs(b[i].x - b[j].x) + std::abs(b[i].y - b[j].y);
    };
    for (bool now = 0; cnt < n + 2 * m; now ^= 1) {
        if (now == 0) {
            int sj = std::lower_bound(gx[sx].begin(), gx[sx].end(), std::make_pair((long long)sy, 0)) - gx[sx].begin();
            if (sj & 1) {
                int pj = std::lower_bound(ax[sx].begin(), ax[sx].end(), std::make_pair((long long)sy, 0)) - ax[sx].begin() - 1;
                sy = gx[sx][--sj].first;
                for (; ~pj && ax[sx][pj].first >= sy; --pj) {
                    id[ax[sx][pj].second] = ++cnt, tab[cnt] = ax[sx][pj].second;
                    dis[cnt] = dis[cnt - 1] + getdis(tab[cnt], tab[cnt - 1]);
                }
            }
            else {
                int pj = std::lower_bound(ax[sx].begin(), ax[sx].end(), std::make_pair((long long)sy + 1, 0)) - ax[sx].begin();
                sy = gx[sx][++sj].first;
                for (; pj < (int)ax[sx].size() && ax[sx][pj].first <= sy; ++pj) {
                    id[ax[sx][pj].second] = ++cnt, tab[cnt] = ax[sx][pj].second;
                    dis[cnt] = dis[cnt - 1] + getdis(tab[cnt], tab[cnt - 1]);
                }
            }
        }
        else {
            int si = std::lower_bound(gy[sy].begin(), gy[sy].end(), std::make_pair((long long)sx, 0)) - gy[sy].begin();
            if (si & 1) {
                int pi = std::lower_bound(ay[sy].begin(), ay[sy].end(), std::make_pair((long long)sx, 0)) - ay[sy].begin() - 1;
                sx = gy[sy][--si].first;
                for (; ~pi && ay[sy][pi].first >= sx; --pi) {
                    if (!id[ay[sy][pi].second]) {
                        id[ay[sy][pi].second] = ++cnt, tab[cnt] = ay[sy][pi].second;
                        dis[cnt] = dis[cnt - 1] + getdis(tab[cnt], tab[cnt - 1]);
                    }
                }
            }
            else {
                int pi = std::lower_bound(ay[sy].begin(), ay[sy].end(), std::make_pair((long long)sx + 1, 0)) - ay[sy].begin();
                sx = gy[sy][++si].first;
                for (; pi < (int)ay[sy].size() && ay[sy][pi].first <= sx; ++pi) {
                    if (!id[ay[sy][pi].second]) {
                        id[ay[sy][pi].second] = ++cnt, tab[cnt] = ay[sy][pi].second;
                        dis[cnt] = dis[cnt - 1] + getdis(tab[cnt], tab[cnt - 1]);
                    }
                }
            }
        }
    }
    dis[n + 2 * m + 1] = dis[n + 2 * m] + getdis(tab[n + 2 * m], tab[1]);
    std::vector<int> d(n + 2 * m + 2);
    for (int i = n + 1; i <= n + 2 * m; i += 2) {
        int s = id[i], t = id[i + 1];
        if (s > t)
            std::swap(s, t);
        if (dis[t] - dis[s] < dis[s] + dis[n + 2 * m + 1] - dis[t]) {
            for (; s - 1 && dis[s] == dis[s - 1]; --s);
            for (; t + 1 <= n + 2 * m && dis[t] == dis[t + 1]; ++t);
            ++d[s], --d[t + 1];
        }
        else {
            for (; s + 1 <= n + 2 * m && dis[s] == dis[s + 1]; ++s);
            for (; t - 1 && dis[t] == dis[t - 1]; --t);
            ++d[1], --d[s + 1], ++d[t];
        }
    }
    std::partial_sum(d.begin() + 1, d.end(), d.begin() + 1);
    for (int i = 1; i <= n; ++i)
        std::cout << d[id[i]] << '\n';
    return 0;
}

赛博乐园 / cyberland

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

发现只需要关注最后一个经过的 0，所以把起点和所有 0 点拿来跑多源最短路
考虑 2 的限制，想到 DP / 分层图之类。\(K\) 很大，但大得很没意义，因为最多减 \(70\) 次就已经超过精度限制了。

故把 \(K\) 和 \(70\) 取 min 然后分层图上 Dij 即可。

感觉因为 dis 会减小，相当于负权边，Dij 真的正确吗？从分层图的角度来看，同一层之间是完全没问题的。

分层图上 Dij 即可。

#include <bits/stdc++.h>
double solve(int n, int m, int k, int t, std::vector<int> x, std::vector<int> y, std::vector<int> w, std::vector<int> op) {
    op.insert(op.begin(), 0), ++t;
    k = std::min(k, 70);
    std::vector<std::vector<std::pair<int, int> > > g(n + 1);
    for (int i = 0; i < m; ++i) {
        ++x[i], ++y[i];
        if (x[i] != t)
            g[x[i]].emplace_back(y[i], w[i]);
        if (y[i] != t)
            g[y[i]].emplace_back(x[i], w[i]);
    }
    {
        std::vector<int> vis(n + 1);
        std::vector<double> dis(n + 1, 1e18);
        std::priority_queue<std::pair<double, int> > q;
        q.emplace(dis[1] = 0, 1);
        for (; !q.empty(); ) {
            int x = q.top().second;
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (auto [i, w] : g[x]) 
                if (dis[i] > dis[x] + w) {
                    dis[i] = dis[x] + w;
                    q.emplace(-dis[i], i);
                }
        }
        if (dis[t] == 1e18)
            return -1;
        for (int i = 1; i <= n; ++i)
            if (op[i] == 0 && dis[i] == 1e18)
                op[i] = 1;
    }
    std::priority_queue<std::pair<int, std::pair<double, int> > > q;
    std::vector<std::vector<int> > vis(k + 1, std::vector<int> (n + 1));
    std::vector<std::vector<double> > dis(k + 1, std::vector<double> (n + 1, 1e18));
    for (int i = 1; i <= n; ++i)
        if (i == 1 || !op[i])
            q.emplace(0, std::make_pair(dis[0][i] = 0., i));
    for (; !q.empty(); ) {
        int t = -q.top().first, x = q.top().second.second;
        q.pop();
        if (vis[t][x])
            continue;
        vis[t][x] = 1;
        for (auto [i, w] : g[x]) {
            if (dis[t][i] > dis[t][x] + w) {
                dis[t][i] = dis[t][x] + w;
                q.emplace(-t, std::make_pair(-dis[t][i], i));
            }
            if (t != k && op[i] == 2 && dis[t + 1][i] > (dis[t][x] + w) / 2.) {
                dis[t + 1][i] = (dis[t][x] + w) / 2.;
                q.emplace(-(t + 1), std::make_pair(-dis[t + 1][i], i));
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= k; ++i)
        res = std::min(res, dis[i][t]);
    return res;
}
#ifndef ONLINE_JUDGE
int main() {
    std::freopen("rsub1_01.in", "r", stdin);
    std::freopen(".out", "w", stdout);
    auto stime = std::chrono::steady_clock::now();
    int T;
    for (std::cin >> T; T--; ) {
        int n, m, k, h;
        std::cin >> n >> m >> k >> h;
        std::vector<int> x(m), y(m), w(k), arr(n);
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
        for (int i = 0; i < m; ++i)
            std::cin >> x[i] >> y[i] >> w[i];
        std::cout << std::fixed << std::setprecision(12) << solve(n, m, k, h, x, y, w, arr) << '\n';
    }
    std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s\n";
    return 0;
}
#endif

言论

学习笔记：FWT

杂题选谈