〔补题〕2025 钉耙编程春季联赛（1）

（赛中+补题记录）

不是题解，更多是做题心得与评价。

做完前三题看剩下的题都没人过，就先切了 10。

1001 签到

签到不谈。

1006 密码

以为都是正数，没枚举 WA 了一次。

正解是枚举所有可能情形，塞进 map 里。答案是 map 值为 1 的那个。

int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
    array<int, 3> a;
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    vector<int> res;
    do {
        if (((a[2] - a[0]) % a[1] == 0) && ((a[2] - a[0]) / a[1] >= 0)) {
            res.push_back((a[2] - a[0]) / a[1]);
        }
    } while (next_permutation(a.begin(), a.end()));
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    for (auto x : res) {
        mp[x]++;
    }
}
int res = -1;
for (auto& [k, v] : mp) {
    if (v == n) {
        res = k;
    }
}
cout << res << endl;

1007 分配宝藏（博弈模板）

海盗分金，经典中的经典，这题是弱化版。

奇数位不给，偶数位给 1 个取得信任。

1005 航线（最短路）

建有向图跑 Dijkstra 最短路。有点分层图的感觉。

int n, m;
cin >> n >> m;
const int N = 4 * n * m;
vector<vector<pair<int, int>>> E(N);
auto Dijkstra = [&](int s) {
    vector vis(N, 0);
    vector dis(N, inf);
    dis[s] = 0;
    priority_queue<pair<ll, int>> Q;
    Q.push({ 0, s });
    while (!Q.empty()) {
        auto [_, u] = Q.top();
        Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [w, v] : E[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ -dis[v], v });
            }
        }
    }
    return dis;
};
vector mp(n, vector<int>(m));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> mp[i][j];
    }
}
auto change = [&](int x, int y, int o) {
    return ((x * m + y) * 4) + o;
};
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (i > 0) {
            E[change(i - 1, j, 1)].push_back({ mp[i][j], change(i, j, 1) });
        }
        if (j > 0) {
            E[change(i, j - 1, 0)].push_back({ mp[i][j], change(i, j, 0) });
        }
        if (i < n - 1) {
            E[change(i + 1, j, 3)].push_back({ mp[i][j], change(i, j, 3) });
        }
        if (j < m - 1) {
            E[change(i, j + 1, 2)].push_back({ mp[i][j], change(i, j, 2) });
        }
    }
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        int x;
        cin >> x;
        for (int o = 0; o < 4; o++) {
            E[change(i, j, o)].push_back({ x, change(i, j, (o + 1) % 4) });
            E[change(i, j, o)].push_back({ x, change(i, j, (o + 3) % 4) });
        }
    }
}
cout << (Dijkstra(0)[change(n - 1, m - 1, 1)] + mp[0][0]) << endl;

1010 返航（基环树上数据结构）

我勒个大力数据结构，初见端倪。（其实也没有很大力，和之前多校相比算码量小的了）

基环树有两种经典做法，一是环 + 触角，二是树 + 边。考虑树易于维护，我们选择后者。

要么不走多出来那条边$s-t$，要么走那条边。不走的话是树上有向路径最大子段和，线段树即可维护。走的话有点复杂，需要讨论是$u-t-s-v$ 还是$u-s-t-v$，还是压根儿走不到环上。判断方式是路径长度（这个可以积累）。

auto res = tree.query_path(u, v).val;  // 不走多出来那条
int utvs = tree.dist(u, t) + tree.dist(v, s);
int usvt = tree.dist(u, s) + tree.dist(v, t);
if (usvt < utvs) {   // 用路径长度判断走哪
    info l = tree.query_path(u, s);
    info r = tree.query_path(t, v);
    res = max(res, (l + r).val);
} else if (utvs < usvt) {
    info l = tree.query_path(u, t);
    info r = tree.query_path(s, v);
    res = max(res, (l + r).val);
}
res = max(0ll, res);  // WA
ans ^= res;      

剩下的事情就是大力维护。时间复杂度大概是$\operatorname{O}[(n+q)\log n]$。

完整代码：

#include <bits/stdc++.h>

#define cerr(x) cerr << #x << " == " << (x) << endl;
#define cerrr(x, y) cerr << #x << " == " << (x) << ", " << #y << " == " << (y) << endl;
#define cern cerr << endl;

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using ulll = unsigned __int128;

constexpr ll N = 1e5 + 8;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

template<class info>
struct SMT {
    int L, R, p, pcnt;
    using pii = struct { info f, b; };
    vector<pii> t;
    vector<int> ls, rs;

    SMT() {
        init(0, 0);
        t.resize(N << 2);
        ls.resize(N << 2);
        rs.resize(N << 2);
    }

    void init(int l, int r) {
        L = l, R = r;
        p = pcnt = 0;
    }

    void init(int p) {
        t[p] = { info(),info() };
        ls[p] = rs[p] = 0;
    }

    #define mid ((L+R)>>1)
    #define leaf (R-L<2)
    #define curr p,L,R
    #define lson ls[p],L,mid
    #define rson rs[p],mid,R
    #define self p,int L,int R

    void push_up(int& p) {
        t[p].f = t[ls[p]].f + t[rs[p]].f;
        t[p].b = t[rs[p]].b + t[ls[p]].b;
    }

    // 单点修改
    void modify(int& self, int x, const info& d) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].f.apply(d), t[p].b.apply(d);
        if (x < mid) modify(lson, x, d);
        else modify(rson, x, d);
        return push_up(p);
    }
    void modify(int x, const info& d) {
        return modify(curr, x, d);
    }

    // 查询[l,r)
    pii query(int& self, int l, int r) {
        if (l <= L && R <= r) return t[p];
        if (r <= mid) return query(lson, l, r);
        if (mid <= l) return query(rson, l, r);
        pii les = query(lson, l, r), res = query(rson, l, r);
        return { les.f + res.f, res.b + les.b };
    }
    pii query(int l, int r) {
        if (l >= r) return { info(),info() };
        return query(curr, l, r);
    }
};

struct info {
    ll sum{ 0 };       // 区间和
    ll lval{ -inf };   // 左边界必选的最大区间和
    ll rval{ -inf };   // 右边界必选的最大区间和
    ll val{ -inf };    // 无限制的最大区间和
    void apply(const info& o)& {
        sum = lval = rval = val = o.sum;
    }
    friend info operator + (const info& l, const info& r) {
        info res;
        res.lval = max(l.lval, l.sum + r.lval);
        res.rval = max(r.rval, r.sum + l.rval);
        res.sum = l.sum + r.sum;
        res.val = max({ l.val, r.val, l.rval + r.lval });
        return res;
    }
};

struct TREE {
    int n, unix;
    vector<vector<int>> E;
    vector<int> p, dep, siz, top, dfn, dfnR, seq;
    SMT<info> smt;

    TREE() {

    }
    TREE(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        E.assign(n, {});
        p.assign(n, -1);
        dep.resize(n);
        siz.resize(n);
        top.resize(n);
        dfn.resize(n);
        dfnR.resize(n);
        seq.resize(n);
        unix = 0;
        smt.init(0, n);  // 线段树初始化
    }

    void add(int u, int v) {
        E[u].push_back(v);
        E[v].push_back(u);
    }

    void work(int s = 0) {
        top[s] = s;
        dep[s] = 0;
        p[s] = -1;
        dfs1(s);
        dfs2(s);
    }

    void dfs1(int u) {
        if (p[u] != -1) {
            E[u].erase(find(E[u].begin(), E[u].end(), p[u]));
        }
        siz[u] = 1;
        for (auto& v : E[u]) {  // 必须加引用
            p[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[E[u][0]]) {
                swap(v, E[u][0]);
            }
        }
    }

    void dfs2(int u) {
        seq[dfn[u] = unix++] = u;
        for (auto& v : E[u]) {
            top[v] = v == E[u][0] ? top[u] : v;
            dfs2(v);
        }
        dfnR[u] = unix;  // 欧拉序：seq[dfnR[u] = unix++] = u;
    }

    // u,v的最近公共祖先
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) u = p[top[u]];
            else v = p[top[v]];
        }
        return dep[u] > dep[v] ? v : u;
    }

    // u到v的路径长度
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    // 查询u-v路径
    info query_path(int u, int v) {  // op=1 不包含lca
        info les, res;
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                les = les + smt.query(dfn[top[u]], dfn[u] + 1).b;
                u = p[top[u]];
            } else {
                res = smt.query(dfn[top[v]], dfn[v] + 1).f + res;
                v = p[top[v]];
            }
        }
        if (dep[u] > dep[v]) {
            les = les + smt.query(dfn[v], dfn[u] + 1).b;
        } else {
            res = smt.query(dfn[u], dfn[v] + 1).f + res;
        }
        return les + res;
    }

    // 修改u节点
    void modify_node(int u, const info& d) {
        smt.modify(dfn[u], d);
    }
};

struct DSU {
    vector<int> p, siz;
    
    DSU(int n) : p(n + 1), siz(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    
    int find(int x) {
        while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool uno(int x, int y) {
        x = find(x), y = find(y);
        if (same(x, y)) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
TREE tree;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int J;
    cin >> J;

    while (J--) {
        int n, q;
        cin >> n >> q;

        tree.init(n);

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

        DSU dsu(n);
        int s = -1;
        int t = -1;
        for (int i = 0; i < n; i++) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            if (dsu.uno(u, v)) {
                tree.add(u, v);
            } else {
                s = u;
                t = v;
            }
        }

        tree.work();
        for (int u = 0; u < n; u++) {
            tree.modify_node(u, { a[u] });
        }

        ll ans = 0;
        while (q--) {
            char op;
            cin >> op;

            if (op == 'Q') {
                int u, v;
                cin >> u >> v;
                u--;
                v--;
                auto res = tree.query_path(u, v).val;  // 不走多出来那条
                int utvs = tree.dist(u, t) + tree.dist(v, s);
                int usvt = tree.dist(u, s) + tree.dist(v, t);
                if (usvt < utvs) {   // 用路径长度判断走哪
                    info l = tree.query_path(u, s);
                    info r = tree.query_path(t, v);
                    res = max(res, (l + r).val);
                } else if (utvs < usvt) {
                    info l = tree.query_path(u, t);
                    info r = tree.query_path(s, v);
                    res = max(res, (l + r).val);
                }
                res = max(0ll, res);  // WA
                ans ^= res;
            } else {
                int u, x;
                cin >> u >> x;
                u--;
                tree.modify_node(u, { x });
            }
        }
        cout << ans << endl;        
    }

    return 0;
}

1004 海浪（双指针，UPSOLVE）

题解、代码 by @余叹之

原题需要寻找$[x, y]$ 区间内满足存在$h_B$ ，使$(h_{i−1}​−h_B​)⋅(h_i​−h_B​)<0$ 全部成立的$[l + 1, r]$ ，使$r - l + 1$ （即长度）最大。

即给出海浪定义，寻找询问区间内最长的海浪长度。

可以使用3个ST表来解决这个问题。

Hint1

令$\operatorname{lo}_i = \min(a[i], a[i - 1])$ ，$\operatorname{hi}_i = \max(a[i], a[i - 1])$
条件区间内$(h_{i−1}​−h_B​)⋅(h_i​−h_B​)<0$ 可转化为$\max\limits_{l+1 \leqslant i \leqslant r}\lbrace \operatorname{lo}_{i} \rbrace \leqslant \min\limits_{l+1 \leqslant i \leqslant r}\lbrace \operatorname{hi}_{i} \rbrace$，
故可以创建 2 个 ST 表来记录这段信息。

// 要求在[l, r] 区间内，对所有的[l + 1, r] MaxLo < MinHi;
RMQ<int, less<>> Min(hi);
RMQ<int, greater<>> Max(lo);

Hint2

可以通过双指针的方式预处理对于每一个点而言作为端点的最长海浪长度和对应端点下标。

举例来说，对于左端点$x$ 而言，我们可以通过$R[x]$ 求得以$x$ 为$l$ 的对应最长海浪右端点$r$， 此时我们会发现，如果有一条海浪的右端点$nx$ 在$r$ 的右侧，其最长海浪的左端点不可能要比$x$ 的位置更靠左，否则$r$ 至少应该被更新至$nx$， 不满足$nx > r$ 的条件。

即最长海浪可能会交错，但绝对不可能被包含。（因为较短的被包含的海浪可以更新至长海浪处）

故海浪的端点是具有单调性质的，可以通过双指针求得。

// 对每个右端点双指针求最左边的满足海浪的端点
vector<int> L(n);       // 右端点对应的左端点
vector<int> R(n);       // 左端点对应的右端点
vector<int> ansRtoL(n); // 右端点对应的最长海浪长度
for (int l = 0, r = 0; r < n; r++) {
    while (l < r && Max(l, r) >= Min(l, r)) {
        l++;
    }
    L[r] = l;
    ansRtoL[r] = r - l + 1;
}

Hint3

对于询问区间$[x, y]$ 来说，（这里把$x$,$y$ 叫做顶点好了）我们可以把海浪分成带顶点（左，右）的和中间的两种。

当左顶点$x$ 为最长海浪的一端时，我们可以通过$R[x]$ 直接定位该海浪，并和$y$ 取$min$ 来确定真正的海浪右端点$ry$ 。而由Hint2所得，接下来我们只需要查找以$[ry, y]$ 区间内的点为右端点的最长的海浪长度。这个区间内所有的左端点都不会比左顶点$x$ 更小，故全部符合题意，只需要知道其数值即可，这就是第三个ST表。

RMQ<int, greater<>> ans(ansRtoL);

同时我们发现以右顶点为端点的海浪也已经被这第二个区间所考虑到了，所以这样的考虑是完备的。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x3f3f3f3f;

template <class T, class Cmp = less<T>> // greater:最大值 less:最小值
struct RMQ {  // 存的是值
    static constexpr int D = 30;
    const Cmp cmp = Cmp();
    vector<T> t[D + 1];

    explicit RMQ(vector<T>& a) {
        const int n = a.size();
        t[0] = a;
        for (int d = 1; d <= __lg(n); d++) {
            t[d].resize(n);
            for (int i = 0; i + (1 << d) <= n; ++i) {
                t[d][i] = min(t[d - 1][i], t[d - 1][i + (1 << (d - 1))], cmp);
            }
        }
    }

    T operator()(int l, int r) {  // [l, r)
        if (l >= r) return max(inf, -inf, cmp);
        int d = __lg(r - l);
        return min(t[d][l], t[d][r - (1 << d)], cmp);
    }
};

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n), lo(n), hi(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i < n; i++) {
            lo[i - 1] = min(a[i], a[i - 1]);
            hi[i - 1] = max(a[i], a[i - 1]);
        }
        // 要求在[l, r] 区间内，对所有的[l + 1, r] MaxLo < MinHi;
        RMQ<int, less<>> Min(hi);
        RMQ<int, greater<>> Max(lo);
        // 对每个右端点双指针求最左边的满足海浪的端点
        vector<int> L(n);       // 右端点对应的左端点
        vector<int> R(n);       // 左端点对应的右端点
        vector<int> ansRtoL(n); // 右端点对应的最长海浪长度
        for (int l = 0, r = 0; r < n; r++) {
            while (l < r && Max(l, r) >= Min(l, r)) {
                l++;
            }
            L[r] = l;
            ansRtoL[r] = r - l + 1;
        }
        for (int l = n - 1, r = n - 1; l >= 0; l--) {
            while (l < r && Max(l, r) >= Min(l, r)) {
                r--;
            }
            R[l] = r;
        }
        ll res = 0;
        RMQ<int, greater<>> ans(ansRtoL);
        for (int i = 1; i <= q; i++) {
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            int ans1 = min(R[l], r) - l + 1;
            int ans2 = ans(min(R[l], r) + 1, r + 1);
            res = (res + 1ll * max(ans1, ans2) * i) % mod; // 一定一定一定要加ll
        }
        cout << res << endl;
    }
    return 0;
}

1009 切割木材（按值转移 dp，UPSOLVE）

好题，少见的按值转移 dp。

最关键的点是注意到题目中那一坨等于 Or - And，所以值不同的 dp 至多$\operatorname{O}(m)$ 个。按值 dp 转移，时间复杂度$\operatorname{O}(nm)$。

可能需要增强布尔代数的化简能力（或是瞪眼能力）。

int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
vector<ll> g(1ll << m);
for (auto& x : g) {
    cin >> x;
}
ll dp = 0;
map<array<int, 2>, ll> mp;
for (int i = 0; i < n; i++) {
    if (mp.count({ a[i], a[i] })) {
        mp[{ a[i], a[i] }] = max(mp[{ a[i], a[i] }], dp);
    } else {
        mp[{ a[i], a[i] }] = dp;
    }
    dp = -inf;
    map<array<int, 2>, ll> nmp;
    for (auto [key, val] : mp) {
        auto [Or, And] = key;
        Or |= a[i];
        And &= a[i];
        dp = max(dp, val + g[Or - And]);
        if (nmp.count({ Or, And })) {
            nmp[{ Or, And }] = max(nmp[{ Or, And }], val);
        } else {
            nmp[{ Or, And }] = val;
        }
    }
    mp = nmp;
}
cout << dp << endl;

1002 船长（减少 DP 转移量，UPSOLVE）

比赛构成二叉树。设碰不到为 dp，转移方程 dp[x] = (dp[l] + dp[r]) / 2，其中$l,r$ 分别是$x$ 的左右儿子。只转移有用的部分，复杂度从$\operatorname{O}(n)$ 降至$\operatorname{O}(k\log k)$。

赛时用 std::map 存 dp 一直 TLE，似乎只能用 std::vector 存，不能多 log。

ll n, k, p;
cin >> n >> k >> p;
p--;
n--;
vector<pair<int, Z>> dp(k);
for (auto& [k, v] : dp) {
    cin >> k;
    k--;
}
sort(dp.begin(), dp.end());
Z res = 1;
for (int bit = 0; bit < 30; bit++) {
    vector<pair<int, Z>> ndp;
    for (auto [k, v] : dp) {
        if (k == n && k % 2 == 0) {
            ndp.push_back({ k >> 1, v });
        } else if ((p >> 1) == (k >> 1)) {
            res *= v;
        } else {
            if (!ndp.empty() && ndp.back().first == k >> 1) {
                ndp.back().second += (v - 1) * inv2;
            } else {
                ndp.push_back({ k >> 1, (v + 1) * inv2 });
            }
        }
    }
    swap(dp, ndp);
    n >>= 1;
    p >>= 1;
}
cout << res << endl;