巅峰赛35题解

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

题目编号	题目标题	难度
T1	午枫的电路谜题	普及-
T2	小安的括号调整	普及/提高-
T3	午枫的图书馆	普及/提高-
T4	小枫的排列谜题	普及/提高-
T5	小枫的密码锁	普及+/提高
T6	小枫的三角形游戏	普及+/提高

T1 午枫的电路谜题

题目大意

每个灯连接两个开关，灯的状态等于这两个开关被“翻转”的次数奇偶性（即两个开关状态之和 $\bmod 2$）。

例如某个灯连接两个开关：

• 若它们都是 $0$ 或都是 $1$，则该灯为关闭；
• 若一个是 $0$，一个是 $1$，则该灯为开启。

问题转化为：将 $2n$ 个开关两两配对，使得每对的异或结果（是否不同）决定灯是否亮。

题目思路

这题的关键在于理解灯的状态。每个灯连接两个开关，而灯是否亮取决于这两个开关被翻转的次数之和的奇偶性，其实就是这两个开关状态的异或值。

所以问题变成：把 $2n$ 个数分成 $n$ 对，每一对如果是 $(0,1)$ 或 $(1,0)$，这一对贡献一个亮灯；如果是 $(0,0)$ 或 $(1,1)$，这一对贡献 $0$。

设数组中 $1$ 的个数是 $cnt$，那么 $0$ 的个数就是 $2n - cnt$。

先考虑最大值。为了让亮灯数量最多，我们应该尽量多配出 $(0,1)$ 对。显然最多能配 $min(cnt, 2n-cnt)$ 对这样的组合。

再考虑最小值。我们希望尽量避免 $(0,1)$，也就是尽量把相同的配在一起：$(0,0)$ 和 $(1,1)$。能做到的最大数量分别是 $\lfloor \frac{cnt}{2} \rfloor$ 和 $\lfloor \frac{2n-cnt}{2} \rfloor$。剩下如果还有无法配的，就必须产生 $(0,1)$。

最终可以发现，最少亮灯数就是 $cnt \% 2$。

因此答案为：

• 最少：$cnt \% 2$
• 最多：$min(cnt, 2n - cnt)$

参考代码

#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;

        int cnt = 0;
        for (int i = 0; i < 2 * n; i++) {
            int x;
            cin >> x;
            if (x == 1) cnt++;
        }

        int mn = cnt % 2;
        int mx = min(cnt, 2 * n - cnt);

        cout << mn << " " << mx << '\n';
    }

    return 0;
}

T2 小安的括号调整

题意简述

给定一个长度为 $2N$ 的括号串 $S$，可以交换任意两个字符（代价 $A$）或替换单个字符（代价 $B$），求将其变为合法括号序列的最小总代价。

解题思路

首先去掉 $S$ 中所有能够匹配的括号对。具体做法是：从左到右扫描，维护当前未匹配的左括号数，遇到 ( 则记录，遇到 ) 且存在未匹配的左括号时就消去一对。这样剩下的是一个形如 ))...)((...( 的串，即若干个右括号后接若干个左括号。设剩余串中左括号数为 $L$，右括号数为 $R$。

这些剩余的括号无法互相匹配，必须通过操作消除。每消除一对 ()（即一个多余右括号和一个多余左括号）的最小代价是 $\min(A, 2B)$，因为可以用一次交换（代价 $A$）或两次替换（代价 $2B$）。如果某一种括号有剩余（全是左括号或全是右括号），则它们只能两两配对，每对需要两次替换，代价 $2B$，若剩余奇数个则还需额外 $2B$。按照这个思路计算代价即可。

参考代码

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

int main() {
    long long N, A, B;
    string S;
    cin >> N >> A >> B >> S;
    
    string st;
    int cnt = 0;
    for (char c : S) {
        if (c == '(') {
            cnt++;
            st += '(';
        } else {
            if (cnt > 0) {
                cnt--;
                st.pop_back();
            } else {
                st += ')';
            }
        }
    }
    
    long long L = 0, R = 0;
    for (char c : st) {
        if (c == '(') L++;
        else R++;
    }
    
    long long ans = 0;
    if (L > 0 && R > 0 && A < 2 * B) {
        long long p = min(L, R);
        ans += p / 2 * A;
        if (p % 2 == 1) ans += A;
        L -= p;
        R -= p;
    }
    
    ans += L / 2 * B + R / 2 * B;
    if (L % 2 == 1) ans += 2 * B;
    
    cout << ans << endl;
    return 0;
}

T3 午枫的图书馆

题意简述

有 $N$ 张书桌环形排列，第 $i$ 张书桌和第 $i+1$ 张之间有一把椅子（第 $N$ 张与第 $1$ 张之间为第 $N$ 把椅子）。$N$ 个同学按排列 $P$ 的顺序依次取椅子：每人优先取自己惯用手同侧的椅子（如果该侧椅子还在），否则取另一侧，若两侧都无则失败。给定字符串 $S$ 表示某些同学的惯用手固定为 L 或 R，其余可任选。求有多少种给 ? 指定 L/R 的方式，使得最终每人恰好拿到一把椅子。

解题思路

观察发现，每个同学的取椅决策只与其两侧椅子的剩余情况有关。由于环形结构，最终每人拿到一把椅子等价于：按顺序处理时，每个人至少有一侧椅子可用，且整个流程结束时椅子恰好被取完。这是一个经典的环形匹配问题，实际上只有当所有同学按顺序“抢占”椅子时，每个人的惯用手选择必须与椅子被取走的顺序相匹配。

将椅子视为位置 $1$ 到 $N$，其中椅子 $i$ 位于书桌 $i$ 和 $i+1$ 之间。同学 $i$（即坐在书桌 $i$ 的人）能取到的椅子是 $i-1$（左侧）或 $i$（右侧，其中 $i=N$ 时右侧为 $1$ 号椅子）。按排列 $P$ 的顺序，每个人会优先选择自己惯用手对应的那侧椅子。要使最后全部椅子被取走，本质上需要排列 $P$ 与惯用手的选择构成一个无冲突的定向匹配。

第一次扫描：对于每个同学 $p_i$，检查其右侧椅子 $p_i \% n + 1$ 是否被标记，若被标记则说明右侧已无，再看左侧 $p_i$ 是否被标记：若两侧都已标记则失败；若两侧都空且该同学为 ?，则有两种选择（乘 2）；否则只能取未被标记的一侧。扫描结束后标记取走的椅子。第二次扫描对称处理，将左右交换。两种方向对应了环上两种可能的“旋转”匹配方式，相加即为总方案数。

参考代码

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

const int mod = 998244353;
int n, p[200005];
bool tk[200005];
string s;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    cin >> s;
    s = " " + s;
    
    int ans = 0;
    
    // 第一次扫描：优先取右侧（R 倾向）
    int sum = 1;
    memset(tk, 0, sizeof(tk));
    for (int i = 1; i <= n; i++) {
        if (tk[p[i]] || tk[p[i] % n + 1]) {
            if (s[p[i]] == '?') sum = sum * 2 % mod;
        } else {
            if (s[p[i]] == 'R') { sum = 0; break; }
        }
        tk[p[i]] = 1;
    }
    ans = (ans + sum) % mod;
    
    // 第二次扫描：优先取左侧（L 倾向）
    sum = 1;
    memset(tk, 0, sizeof(tk));
    for (int i = 1; i <= n; i++) {
        if (tk[p[i]] || tk[p[i] % n + 1]) {
            if (s[p[i]] == '?') sum = sum * 2 % mod;
        } else {
            if (s[p[i]] == 'L') { sum = 0; break; }
        }
        tk[p[i] % n + 1] = 1;
    }
    ans = (ans + sum) % mod;
    
    cout << ans << endl;
    return 0;
}

T4 小枫的排列谜题

题意简述

给定一个长度为 $n$ 的排列 $p$，求满足 $a<b<c<d$ 且 $p_a < p_c$ 且 $p_b > p_d$ 的四元组 $(a,b,c,d)$ 的数量。

解题思路

枚举中间的两个位置 $b$ 和 $c$（$b < c$）。对于固定的 $b,c$，需要统计左边满足 $a < b$ 且 $p_a < p_c$ 的 $a$ 的数量，以及右边满足 $d > c$ 且 $p_d < p_b$ 的 $d$ 的数量，两者相乘累加。由于 $n \le 5000$，可以用 $O(n^2)$ 预处理或直接枚举。

更高效的做法是：先预处理 $dp[i]$ 表示 $i$ 右边比 $p_i$ 小的数的个数。然后从左到右枚举 $c$，维护左侧比 $p_c$ 小的数的个数和对应贡献，动态更新并累加。

参考代码

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

const int N = 5005;
int a[N], dp[N], s[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            dp[i] = 0;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (a[i] > a[j]) dp[i]++;
            }
        }
        
        long long ans = 0;
        for (int c = 1; c <= n; c++) {
            for (int b = 1; b <= c; b++) {
                if (a[b] > a[c]) dp[b]--;
            }
            s[0] = 0;
            for (int i = 1; i <= c; i++) {
                s[i] = s[i - 1] + dp[i];
            }
            for (int b = 1; b < c - 1; b++) {
                if (a[b] < a[c]) {
                    ans += s[c - 1] - s[b];
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

T5 小枫的密码锁

题意简述

密码长度为 $N$，每位可填 $1$ 到 $M$。对每个数字 $B$，要求任意两个 $B$ 之间的闭区间内必须至少出现一次 $X_B$。求合法密码数，对 $998244353$ 取模。

解题思路

考虑每个数字 $B$ 出现后，在下次出现之前必须见到 $X_B$，这类似一种“依赖”关系。将每个数字是否还在等待其依赖数字的状态压缩成 $M$ 位二进制。初始时，所有数字都未出现，但为了处理边界，设初始状态为所有数字都“已满足”（即全 $1$）。用 $dp[i][mask]$ 表示前 $i$ 位后，当前哪些数字正在等待其依赖数字的状态。填入数字 $j$ 时，只有当 $j$ 当前不处于等待状态（即 $mask$ 中 $j$ 位为 $1$）时才能填入。填入后，$j$ 变为等待状态（因为它下次出现需要 $X_j$），同时 $j$ 的出现会满足所有依赖 $j$ 的数字（即 $X_B = j$ 的那些 $B$），将它们从等待状态中清除。用 $mask[j]$ 表示填入 $j$ 后可以清除的集合，转移为 $dp[i+1][(mask \oplus (1<<j-1)) | mask[j]] += dp[i][mask]$。答案即为 $\sum dp[N][mask]$。

参考代码

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

long long n, m, mask[12], dp[11451][1024];
const long long mod = 998244353;

int main() {
    cin>>m>>n;
    for (long long i = 1; i <= m; i++) {
        long long x;
        cin>>x;
        mask[x] |= 1 << (i - 1);
    }
    dp[0][(1 << m) - 1] = 1;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j <= m; j++) {
            for (long long k = 0; k < (1 << m); k++) {
                if ((k >> (j - 1)) & 1) {
                    long long &res = dp[i + 1][(k ^ (1 << (j - 1))) | mask[j]];
                    res += dp[i][k];
                    res %= mod;
                }
            }
        }
    }
    long long ans = 0;
    for (long long i = 0; i < (1 << m); i++) {
        ans += dp[n][i];
        ans %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}

T6 小枫的三角形游戏

题意简述

正 $n$ 边形顶点有权值 $a_i$，每次选三个未选过的顶点构成三角形，且三角形内部不能与已有三角形重叠，得分增加三个顶点权值乘积。求最大总得分。

解题思路

合法三角形集合对应多边形的一种三角剖分。设 $dp[i][j]$ 表示顶点 $i$ 到 $j$ 按顺序构成的子多边形（边数 $\ge 2$）能获得的最大得分。转移时考虑顶点 $i$ 和 $j$ 之间的边，有两种情况：

1. 在子多边形中取一个三角形 $(i,j,k)$，则多边形被分成 $(i+1,k-1)$ 和 $(k+1,j-1)$ 两部分，加上三角形贡献，即 $dp[i][j] = \max\{dp[i+1][k-1] + dp[k+1][j-1] + a_i a_j a_k\}$。
2. 不取与边 $(i,j)$ 相关的三角形，而是将多边形分成两段，即 $dp[i][j] = \max\{dp[i][k] + dp[k+1][j]\}$。

取所有情况的最大值即可。最终答案为 $dp[1][n]$。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 410;

long long a[N];
long long dp[N][N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int len = 3; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j - 1] + a[i] * a[j] * a[k]);
            }
            for (int k = i; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
        }
    }
    cout << dp[1][n] << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}