官方题解|巅峰赛26题解

hopebetter

2025-10-13 19:44:41

发布于：浙江

57阅读

0回复

0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	奇怪的齿轮	入门
T2	奇怪的数组	普及-
T3	奇怪的数学	普及/提高-
T4	奇怪的探针	普及+/提高
T5	奇怪的树	普及+/提高
T6	奇怪的集市	普及+/提高

T1 奇怪的齿轮

题目大意

在一个 $h \times w$ 的网格平面上每个格子可以放一个齿轮或者留空

若两个放了齿轮的格子相邻即共享一条边它们会啮合且啮合齿轮的转向必须相反

一次放置被称为合理当且仅当已放置的所有齿轮可以被赋予顺时针或逆时针的方向使每一对相邻齿轮的方向相反

只区分放与不放不把具体顺逆视为不同方案

求合理放置的总数输出对 $998244353$ 取模后的结果

题解思路

网格按上下左右相邻建边是棋盘图的子图因而天然二分

任意选取的格子诱导出的子图仍是二分图总能给黑白两侧分别赋相反方向

于是每个格子都是独立的二元选择

答案等于 $2^{ h \times w}$ 次方取模 $998244353$

注意 $h \times w$ 可能会爆 $ll$

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

const i64 MOD = 998244353;

i64 qpow(i64 a, i64 e){
    i64 r = 1;
    while (e){
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long h, w;
    cin >>h >> w; 
 
    const i64 mods = MOD - 1;
    i64 e = ( (h % mods) * (w % mods) ) % mods;
    cout << qpow(2, e) << '\n';
    return 0;
}

T2 奇怪的数组

题目大意

给定长度为 $n$ 的整数数组 $a=(a_1,a_2,\dots,a_n)$ 。需要按原下标顺序将其拆成两条单调不降链：存在标记 $c_i\in\{1,2\}$ 使得

$i<j,\ c_i=c_j=1 \;\Rightarrow\; a_i\le a_j,\qquad i<j,\ c_i=c_j=2 \;\Rightarrow\; a_i\le a_j.$

判断是否存在可行划分。多组数据。

题解思路

维护两条链的末尾值 $t_1,t_2$ （初始为 $-\infty$ ），从左到右扫描每个 $x=a_i$ ：

若 $x\ge t_1$ 且 $x\ge t_2$ ，将 $x$ 放入末尾更大的那条链，即令 $t_k\gets x$ 其中 $k=\arg\max\{t_1,t_2\}$ ；
否则若仅有一条满足（如 $x\ge t_1$ 或 $x\ge t_2$ ），放入可行的那条并更新末尾；
否则两条都接不上，无解。

该贪心等价于耐心排序在 $k=2$ 时的最少堆判定。时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

参考代码

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

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

    int t;
    cin>>t;
   
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        long long tail1 = LLONG_MIN;
        long long tail2 = LLONG_MIN;
        bool ok = true;

        for (long long x : a) {
            if (x >= tail1 && x >= tail2) {
                if (tail1 >= tail2) tail1 = x;
                else tail2 = x;
            } else if (x >= tail1) {
                tail1 = x;
            } else if (x >= tail2) {
                tail2 = x;
            } else {
                ok = false;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

T3 奇怪的数组

题目大意

给定一个初始数组 $A=\{a_1,\dots,a_n\}$ 。允许无限次执行操作：从当前数组中选取两个数 $u,v$ ，把 $u\ \mathbf{AND}\ v$
或 $u\ \mathbf{OR}\ v$ 的结果插回数组。给出 $q$ 次询问，每次给定一个数 $x$ ，判断是否存在一系列操作
，使得最终数组中出现 $x$ 。只需回答 Yes / No。

数值按 64 位带符号整型读入与运算；建议测试数据非负且不超过 $2^{60}-1$ 。

题解思路

把每个整数视为 0/1 位向量。允许的操作只有逐位的 $\text{AND}$ 与 $\text{OR}$ ，因此闭包是一个单调布尔代数
。关键在于：要让目标数 $x$ 的某一位 $j$ 最终为 1，在整个构造过程中所有进行 $\text{AND}$ 的中间数在位 $j$ 上都必须为
1，否则这一位会被清零。

基于此定义

$F_j \;=\; \bigwedge_{\ a_i:\ (a_i)_j=1}\ a_i,$

即把所有第 $j$ 位为 1 的原始数逐位与起来得到的掩码。若没有任何 $a_i$ 在位 $j$ 上为 1，则位 $j$ 不可获得。

对一个查询 $x>0$ ，令

$M(x)\;=\;\bigvee_{\,j:\ (x)_j=1} F_j.$

这代表在“保证 $x$ 的每个所需位始终为 1”的前提下，不可避免地会被携带上的最小附带位集合。于是有如下充要条件：

必要性：若最终得到 $x$ ，则对每个 $j\in \text{bits}(x)$ ，整个过程中所有与运算的参与者在位 $j$ 都为 1，因此 $x$
必定包含 $F_j$ 的所有 1 位，合起来得到 $x \supseteq M(x)$ 。若 $M(x)$ 在某些位上多于 $x$ ，这些多出来的 1
是无论如何都无法“去掉”的，故不可达。
充分性：可以先把具有位 $j$ 的所有原始数逐位与，构造出每个 $F_j$ ，再把这些 $F_j$ 逐位或起来得到 $M(x)$ 。若 $M(x)=x$ ，则确实可达。

对 $x=0$ 的特判：要把所有位都变成 0，只能不断做与运算，极小值是全体按位与

$A_{\text{all}}\,=\,\bigwedge_{i=1}^n a_i.$

当且仅当 $A_{\text{all}}=0$ 时，能得到 0。

复杂度分析

预处理 $F_j$ 与 $A_{\text{all}}$ 的时间 $O(n\cdot B)$ ，单次查询 $O(B)$ ，其中 $B=61$ ；总复杂度 $O((n+q)\cdot 61)$
，空间 $O(61)$ 。

参考代码

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

 

int main() {
    int n, q;
    cin >> n >> q;
    i64 all = ~0ll;
    vector<i64> f(70, ~0ll);
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        for (int j = 0; j <= 60; j++) {
            if ((x >> j) & 1) {
                f[j] &= x;
            }
        }
        all &= x;
    }

    for (int i = 1; i <= q; i++) {
        i64 x;
        cin >> x;
        if (x == 0) {
            if (all == 0) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            i64 ans = 0;
            for (int j = 0; j <= 60; j++) {
                if ((x >> j) & 1) ans |= f[j];
            }
            if (ans == x) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

T4

题目大意

给定一个长度为 $n$ 的排列。对若干内点 $i$ （ $2\le i\le n-1$ ）给出局部要求：

P：位置 $i$ 必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中严格最大；
V：位置 $i$ 必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中严格最小；
.：该处无要求。

求满足全部要求的排列个数，对 $998244353$ 取模。多组数据。

题解思路

快速可行性检查
若存在相邻的两位都被标记且相同（PP 或 VV），必然矛盾，答案为 0。
从三元极值到二元不等式
P 在 $i$ 处意味着 $a_{i-1}<a_i$ 且 $a_{i+1}<a_i$ ；
V 在 $i$ 处意味着 $a_{i-1}>a_i$ 且 $a_{i+1}>a_i$ 。
可将这些三元约束折算到相邻两点之间的“上升/下降”要求，并用数组 $c$ 标记到位置 $i$ 的插入方向：

令 $c[i]=1$ 表示新放的 $a_i$ 应当大于上一位（下降到当前，上一位更小）；
令 $c[i]=2$ 表示新放的 $a_i$ 应当小于上一位；
无要求则 $c[i]=0$ 。

插入式 DP（名次法）
令 $f_i[j]$ 表示用 $\{1,\ldots,i\}$ 构成长度为 $i$ 的前缀，且第 $i$ 个数在前 $i$ 个中的相对名次为第 $j$ 小的方案数。
用前缀和 $pre_i[j]=\sum_{k=1}^j f_i[k]$ 优化转移，初值 $f_1[1]=1$ 。
转移到第 $i$ 位：

若 $c[i]=1$ （“前一位 < 当前”）：上一名次 $k\in[j,i-1]$
$\Rightarrow f_i[j]=pre_{i-1}[i-1]-pre_{i-1}[j-1]$ 。
若 $c[i]=2$ （“前一位 > 当前”）：上一名次 $k\in[1,j-1]$
$\Rightarrow f_i[j]=pre_{i-1}[j-1]$ 。
若无要求：上一名次任意
$\Rightarrow f_i[j]=pre_{i-1}[i-1]$ 。
答案为 $\sum_{j=1}^n f_n[j]=pre_n[n]$ 。为节省空间，使用滚动数组。

复杂度分析

双层循环 $i=1\ldots n,\ j=1\ldots i$ ，每步 $O(1)$ 转移，总时间 $O(n^2)$ ；空间 $O(n)$ 。

参考代码

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

const i64 mod = 998244353;

i64 add(i64 x, i64 y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
}

i64 sub(i64 x, i64 y) {
    x -= y;
    if (x < 0) x += mod;
    return x;
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;

    for (int i = 1; i < n; i++) {
        if (s[i] != '.' && s[i + 1] != '.') {
            if (s[i] == s[i + 1]) {
                cout << 0 << '\n';
                return;
            }
        }
    }
    vector<int> c(n + 1);
    for (int i = 1; i < n; i++) {
        if (s[i] != '.') {
            if (s[i] == 'P') {
                c[i] = 1;
                c[i + 1] = 2;
            } else {
                c[i] = 2;
                c[i + 1] = 1;
            }
        }
    }

    vector<vector<i64>> f(2, vector<i64>(n + 1, 0));
    vector<vector<i64>> pre(2, vector<i64>(n + 1, 0));

    int cur = 1 & 1;
    f[cur][1] = 1;
    pre[cur][1] = 1;

    for (int i = 2; i <= n; i++) {
        cur = i & 1;
        int prv = (i - 1) & 1;

        pre[cur][0] = 0;
        for (int j = 1; j <= i; j++) {
            if (c[i] == 1)
                f[cur][j] = sub(pre[prv][i - 1], pre[prv][j - 1]);
            else if (c[i] == 2)
                f[cur][j] = pre[prv][j - 1];
            else
                f[cur][j] = pre[prv][i - 1];

            pre[cur][j] = add(pre[cur][j - 1], f[cur][j]);
        }
    }

    cout << pre[n & 1][n] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

T5 题解

题目大意

多次询问“以某点为根的整棵子树里，出现次数 ≥ T 的颜色有多少种”。朴素每次扫子树会超时。

题解思路

核心做法：DSU on tree（重儿子保留）

先 DFS 求每个点的子树大小与重儿子。
处理某点 u 时：
1. 先递归处理所有轻儿子并清空它们的贡献；
2. 再处理重儿子并“保留”它的贡献；
3. 把 u 自己和所有轻儿子的整棵子树颜色“加回到”重儿子已保留的桶里；
4. 现在桶里正好是 u 的整棵子树，可以回答 u 的所有询问；
5. 若 u 是轻分支，处理完就清空；若是重分支，保留给父亲复用。
  这样保证每个节点的颜色只被加入/删除少数次，整体近似 $O(n \log n)$ 。

如何快速回答“≥ T”

维护两层计数：
- cnt[color]：当前桶里该颜色出现了几次；
- freq[t]：出现次数恰为 t 的颜色种数。
当某个颜色次数增减时，同时把它在 freq 里的位置移动一格。
询问“≥ T”的数量，就是把 freq[T..n] 的和求出来即可。
用 Fenwick（树状数组）维护 freq 的前缀和，区间求和就变成两次前缀相减，单次 $O(\log n)$ 。

正确性直觉

DSU 的“先轻后重、重保留、轻合并”让你在处理 u 时，数据结构里恰好放着 u 子树的全部节点颜色；
freq 记录“每个出现次数上有多少颜色”，问“≥ T”直接查后缀和，自然正确。

复杂度

预处理 DFS： $O(n)$
DSU 合并 + Fenwick 更新：约 $O(n \log^2 n)$
q 次询问： $O(q \log n)$

代码

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

template<typename T>
class FenwickTree {
    int n;
    vector<T> tree;

public:
    FenwickTree(int size = 0) { reset(size); }

    void reset(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    void add(int pos, T x) {
        if (pos <= 0) return;
        while (pos <= n) {
            tree[pos] += x;
            pos += pos & -pos;
        }
    }

    T prefix_sum(int pos) const {
        T ans = 0;
        while (pos > 0) {
            ans += tree[pos];
            pos -= pos & -pos;
        }
        return ans;
    }

    T range_sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l - 1); }
};

struct Tree {
    int n, q;
    vector<int> col, cnt, sz, son, fa, ans;
    FenwickTree<int> fenwick;
    vector<vector<int> > edge;
    vector<vector<pair<int, int> > > ask;
    vector<char> big;
    int tot = 0, cols = 0;

    Tree(int n, int q): n(n), q(q), col(n + 1), cnt(n + 1, 0), sz(n + 1, 1), son(n + 1, -1), fa(n + 1, -1),
                        ans(q + 1, 0), fenwick(n), edge(n + 1), ask(n + 1), big(n + 1, 0) {
    }

    void add_edge(int u, int v) {
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    int add_ask(int u, int T) {
        ask[u].push_back({T, ++tot});
        return tot;
    }

    void dfs1(int u, int p = -1) {
        fa[u] = p;
        sz[u] = 1;
        son[u] = -1;
        int best = 0;
        for (int v: edge[u]) {
            if (v == p) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > best) {
                best = sz[v];
                son[u] = v;
            }
        }
    }

    void add_color(int c) {
        int t = cnt[c];
        if (t > 0) fenwick.add(t, -1);
        else cols++;
        cnt[c] = ++t;
        fenwick.add(t, +1);
    }

    void remove_color(int c) {
        int t = cnt[c];
        fenwick.add(t, -1);
        --t;
        if (t == 0) cols--;
        cnt[c] = t;
        if (t > 0) fenwick.add(t, +1);
    }

    void add_tree(int u) {
        add_color(col[u]);
        for (int v: edge[u]) {
            if (v == fa[u] || big[v]) continue;
            add_tree(v);
        }
    }

    void remove_tree(int u) {
        remove_color(col[u]);
        for (int v: edge[u]) {
            if (v == fa[u] || big[v]) continue;
            remove_tree(v);
        }
    }

    void dsu(int u, int p, bool keep) {
        for (int v: edge[u]) if (v != p && v != son[u]) dsu(v, u, false);
        if (son[u] != -1) {
            dsu(son[u], u, true);
            big[son[u]] = 1;
        }
        add_tree(u);
        for (auto [T,id]: ask[u]) {
            if (T <= 1) ans[id] = fenwick.range_sum(1, n);
            else if (T > n) ans[id] = 0;
            else ans[id] = fenwick.range_sum(T, n);
        }
        if (son[u] != -1) big[son[u]] = 0;
        if (!keep) remove_tree(u);
    }
};

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

    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];

    Tree solver(n, q);
    for (int i = 1; i <= n; i++) solver.col[i] = c[i];

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }
    for (int i = 0; i < q; i++) {
        int u, T;
        cin >> u >> T;
        solver.add_ask(u, T);
    }

    solver.dfs1(1, -1);
    solver.dsu(1, -1, true);

    for (int i = 1; i <= q; i++) cout << solver.ans[i] << '\n';
    return 0;
}

T6

题目大意

给定一张有向图，点编号 $1\ldots n$ 。你可以从任意点出发行走：

若沿边 $u\to v$ 移动，且 $u,v$ 同属同一强连通分量（即同一“环”内），则本次移动无需费用；
否则需要支付该边的费用；
你有 $p$ 张代金券，可用于任意 $p$ 条需要付费的边，使其费用记为 0；
第一次访问某个点可获得该点的收益，多次访问不重复计收益；
可自由选择起点与路径。给定初始资金 $w$ 。

问通过合理选择起点、路径与代金券使用策略，最多能获得多少资金。

题解思路

缩点：用 Tarjan 求强连通分量，将同一 SCC 的点合并为一个点，节点权为该 SCC 内所有点收益之和。只有跨 SCC 的边保留其费用。缩点后得到 DAG。
DAG 上 DP：允许从任意 SCC 启动，进入即领取该 SCC 的汇总收益；跨边行走时
- 不用券：资金 $\gets$ 资金 $-$ 边费 $+$ 目标 SCC 汇总收益；
- 用券：资金 $\gets$ 资金 $+$ 目标 SCC 汇总收益，券数 $-1$ 。
  对 DAG 拓扑顺序进行转移，状态为 $(\text{SCC}, \text{剩余券数})$ ，取最大值。
答案：所有状态中的最大资金。

复杂度分析

Tarjan 缩点 $O(n+m)$ ；DAG 上 DP 约为 $O((S+E)\cdot(p+1))$ ，其中 $S,E$ 为缩点后点边数。

参考代码

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

using i64 = long long;


#define  re(x) freopen(x , "r" , stdin)
#define  wr(x) freopen(x , "w" , stdout)
#define  de(x) freopen(x , "w" , stderr)

#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42
#endif
#include <bits/stdc++.h>

struct SCC {
    vector<int> dfn, low;
    vector<int> instack;
    vector<vector<pair<int, i64> > > graph;
    stack<int> st;
    vector<i64> w;
    int tot;
    int sccs;
    vector<int> id;
    vector<i64> scc_w;
    vector<vector<int> > scc;
    vector<vector<pair<int, i64> > > scc_graph;
    vector<int> scc_du;
    int n;

    SCC(int n, vector<i64> &w)
        : n(n), dfn(n + 1, -1), low(n + 1, 0), instack(n + 1, 0),
          graph(n + 1), w(w), tot(0), sccs(0), id(n + 1, 0) {
    }

    void add_edge(int u, int v, i64 ww) {
        graph[u].emplace_back(v, ww);
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++tot;
        st.push(u);
        instack[u] = 1;

        for (auto [nx, _]: graph[u]) {
            if (dfn[nx] == -1) {
                dfs(nx);
                low[u] = min(low[u], low[nx]);
            } else if (instack[nx]) {
                low[u] = min(low[u], dfn[nx]);
            }
        }

        if (low[u] == dfn[u]) {
            ++sccs;
            while (true) {
                int x = st.top();
                st.pop();
                instack[x] = 0;
                id[x] = sccs;
                if (x == u) break;
            }
        }
    }

    void run() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == -1) dfs(i);
        }

        scc.assign(sccs + 1, {});
        scc_w.assign(sccs + 1, 0);
        for (int i = 1; i <= n; i++) {
            scc[id[i]].push_back(i);
            scc_w[id[i]] += w[i];
        }

        scc_graph.assign(sccs + 1, {});
        scc_du.assign(sccs + 1, 0);
        for (int u = 1; u <= n; u++) {
            for (auto [v, cost]: graph[u]) {
                if (id[u] != id[v]) {
                    scc_graph[id[u]].emplace_back(id[v], cost);
                    scc_du[id[v]]++;
                }
            }
        }
    }

    i64 dp(i64 ww, int pp) {
        vector<vector<i64> > f(sccs + 1, vector<i64>(pp + 1, -1e18));
        queue<int> q;

        for (int i = 1; i <= sccs; i++) {
            f[i][pp] = ww + scc_w[i];
            if (scc_du[i] == 0) q.push(i);
        }

        i64 mx = ww;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto [v, cost]: scc_graph[u]) {
                scc_du[v]--;
                for (int j = 0; j <= pp; j++)
                    if (f[u][j] > -1e17) {
                        f[v][j] = max(f[v][j], f[u][j] - cost + scc_w[v]);
                        if (j > 0)
                            f[v][j - 1] = max(f[v][j - 1], f[u][j] + scc_w[v]);
                    }
                if (scc_du[v] == 0) q.push(v);
            }
            for (int j = 0; j <= pp; j++)
                mx = max(mx, f[u][j]);
        }
        return mx;
    }
};


int main() {
    int n, m, w, p;
    cin >> n >> m >> w >> p;

    vector<i64> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    SCC scc(n, arr);

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        scc.add_edge(u, v, w);
    }
    scc.run();
    i64 ans = scc.dp(w, p);
    cout << ans << endl;
}