2026CSP-J第二轮复赛模拟赛题解

Yuilice

2026-10-21 10:57:39

发布于：浙江

189阅读

0回复

0点赞

题号	题目	完整算法	时间复杂度	空间复杂度
A	三站积分榜	结构体排序	$O(n\log n)$	$O(n)$
B	展板分层	贪心	$O(20\sum n)$	$O(20)$
C	断连充能	动态规划	$O(n)$	$O(1)$
D	三轨信号	动态规划	$O(n)$	$O(1)$

A. 三站积分榜

解题思路

题意分析

每名队员都对应一组相关信息：原始编号、三站成绩、有效成绩。使用结构体保存这些信息，再用结构体数组保存所有队员。排序时整条队员记录一起移动，编号与成绩就能始终对应。

读入第 $i$ 名队员时，把编号记为 $i$ 。先求三站成绩的最小值，再用三站成绩之和减去这个最小值，得到有效成绩。每站最高为 $100$ ，有效成绩最高为 $200$ ，使用 int 就能保存所有成绩和编号。

接下来，关键是写清楚两名队员谁应该排在前面。比较函数 cmp 返回 true，表示第一名队员应排在第二名队员前面。题目的三条规则具有先后顺序，必须先判断优先级更高的条件，只有这一项相同时，才继续比较下一项。

设正在比较的队员为 $x,y$ 。如果两人的有效成绩不同，就由有效成绩决定顺序，成绩大的排在前面；如果有效成绩相同，再比较第三站成绩，第三站成绩大的排在前面；如果这两项都相同，最后比较编号，编号小的排在前面。

例如两名队员的有效成绩分别为 $170$ 和 $160$ ，即使后者第三站成绩更高，也应当由有效成绩为 $170$ 的队员排在前面。只有有效成绩相同，第三站成绩才参与决定顺序。

当两名队员的有效成绩、第三站成绩都相同时，较小编号表示输入时更早出现的队员。原始编号已经存入结构体，排序后仍然按保存的编号比较和输出。

调用 sort，传入结构体数组和比较函数，数组就会按照这三条规则排列。程序使用下标 $1$ 至 $n$ 保存队员，对应的排序区间写为 sort(p + 1, p + n + 1, cmp)。排序完成后，依次输出数组中每名队员的编号和有效成绩。

实现步骤

定义队员结构体，保存编号、三站成绩和有效成绩，并建立结构体数组。
对第 $i$ 名队员，将原始编号记为 $i$ ，用三站成绩总和减去其中的最低分，得到有效成绩。
编写比较函数：有效成绩不同时按有效成绩降序；否则，第三站成绩不同时按第三站成绩降序；两项都相同时按编号升序。
使用 sort 对全部队员排序。
按排序后的顺序输出队员编号和有效成绩。

正确性证明

首先，对于任意队员，算法先求出三站成绩的最小值，再用三站成绩之和减去这个值，恰好符合有效成绩的定义。因此，算法保存的每名队员的有效成绩正确。

下面说明比较函数能正确判断任意两名队员的先后顺序。

如果两人的有效成绩不同，比较函数让有效成绩较高者排在前面，符合第一条排名规则。如果有效成绩相同、第三站成绩不同，比较函数让第三站成绩较高者排在前面，符合第二条规则。如果有效成绩和第三站成绩都相同，比较函数让编号较小者排在前面，符合第三条规则。三种情况覆盖了任意两名不同队员的比较，所以比较函数与题目规定的顺序完全一致。

sort 按照比较函数排列全部队员，因此排序后的数组顺序就是题目要求的排名顺序。结构体保存了每名队员的原始编号及正确的有效成绩，排序时这些信息一起移动，所以依次输出数组中的编号和有效成绩，就是正确答案。

复杂度分析

读入并计算全部队员的有效成绩需要 $O(n)$ 时间。比较函数每次只比较固定数量的整数，耗时为 $O(1)$ ，排序需要 $O(n\log n)$ 时间。输出需要 $O(n)$ 时间，因此总时间复杂度为 $O(n\log n)$ 。

结构体数组保存 $n$ 名队员的信息，占用 $O(n)$ 空间；排序过程的辅助空间不超过这一数量级，因此总空间复杂度为 $O(n)$ 。

参考代码

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

struct Node {
    int id;
    int a, b, c;
    int s;
};

Node p[100005];

bool cmp(Node x, Node y) {
    if (x.s != y.s) {
        return x.s > y.s;  // 有效成绩高的排在前面
    }
    if (x.c != y.c) {
        return x.c > y.c;  // 有效成绩相同时，第三站成绩高的排在前面
    }
    return x.id < y.id;  // 前两项都相同时，编号小的排在前面
}

int main() {
    freopen("scoreboard.in", "r", stdin);
    freopen("scoreboard.out", "w", stdout);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].a >> p[i].b >> p[i].c;
        p[i].id = i;  // 编号由输入顺序确定
        int mn = min(p[i].a, min(p[i].b, p[i].c));
        p[i].s = p[i].a + p[i].b + p[i].c - mn;
    }

    sort(p + 1, p + n + 1, cmp);

    for (int i = 1; i <= n; i++) {
        cout << p[i].id << ' ' << p[i].s << '\n';
    }
    return 0;
}

B. 展板分层

解题思路

题意分析

设展示墙宽度为 $W$ ，共需摆放 $n$ 块展板。所有展板的高度都相同，决定能否放进一层的只有宽度。我们逐层摆放展板：每开始一层，剩余宽度设为 $W$ ；然后从最大的宽度开始考虑，当前宽度的展板能放多少块，就放多少块，再继续考虑更小的宽度。

例如墙宽为 $10$ ，剩余展板中有宽度为 $8,4,2$ 的展板。当前层先放一块宽度为 $8$ 的展板，剩余宽度为 $2$ 。宽度为 $4$ 的展板留给后面的层，当前层继续放入宽度为 $2$ 的展板。某种宽度放不下时，仍然要继续检查更小的宽度。

这个贪心策略依赖于展板宽度都是 $2$ 的整数次幂。对于宽度为 $2^p$ 的展板，所有更小的宽度都能整除 $2^p$ 。若一批更小展板的总宽度至少为 $2^p$ ，就一定能从中选出若干块，使宽度之和恰好为 $2^p$ 。因此，可以通过交换一块大展板和若干块小展板，将某个最优方案逐步调整成上述从大到小的摆法。完整的交换过程见正确性证明。

接下来考虑如何快速找到每种宽度的展板。因为 $w_i\le10^6$ ，可能出现的宽度只有 $2^0,2^1,\ldots,2^{19}$ ，共 $20$ 种。使用数组 $\mathrm{cnt}[p]$ ，记录宽度为 $2^p$ 的展板还剩多少块。读入一块展板时，将它的宽度不断除以 $2$ ，直到变为 $1$ ，除法次数就是对应的指数 $p$ 。

设当前层剩余宽度为 $\mathrm{r}$ 。考虑宽度为 $2^p$ 的展板时，当前层最多还能放 $\lfloor\mathrm{r}/2^p\rfloor$ 块，同时也不能超过剩余数量。因此，本次放入的数量为：

$\mathrm{k}=\min\left(\mathrm{cnt}[p],\left\lfloor\frac{\mathrm{r}}{2^p}\right\rfloor\right).$

放入后，将该宽度的剩余数量减少 $\mathrm{k}$ ，当前层剩余宽度减少 $\mathrm{k}\cdot2^p$ ，未摆放的展板总数也减少 $\mathrm{k}$ 。从 $p=19$ 枚举到 $p=0$ 后，当前层摆放结束，答案增加 $1$ 。重复这个过程，直到全部展板放完。

题目保证每块展板的宽度都不超过 $W$ 。只要还有展板，每个新层就至少能放入一块，所以最多会开出 $n$ 层，循环一定能够结束。

部分分说明：

测试点 $1\sim3$ （一份输入中 $\sum n\le10^3$ ）：可以先将展板宽度从大到小排序，记录每块是否已放置。每开一层就完整扫描一次数组，将尚未放置且能放下的展板依次放入，最多扫描 $n$ 层，每组数据的时间复杂度为 $O(n^2)$ 。
测试点 $4\sim12$ （一份输入中 $\sum n\le10^5$ ）：统计 $20$ 种宽度的剩余数量，每层从大到小批量放置展板。每组数据的时间复杂度为 $O(20n)$ ，能够处理全部数据。

实现步骤

对每组数据，将宽度计数数组 $\mathrm{cnt}$ 清零。
遍历每块展板的宽度，求出对应的指数 $p$ ，将 $\mathrm{cnt}[p]$ 增加 $1$ 。
将未摆放展板数设为 $n$ ，答案设为 $0$ 。只要还有展板，就新开一层，并将该层剩余宽度设为 $W$ 。
从 $p=19$ 到 $p=0$ ，计算当前宽度能放入的数量 $\mathrm{k}$ ，更新宽度计数、该层剩余宽度和未摆放展板数。
枚举完所有宽度后，将答案增加 $1$ 。所有展板放完后，输出该组答案。

正确性证明

首先证明一个关于宽度的引理：设 $s$ 是 $2$ 的整数次幂，一批展板的宽度都是小于 $s$ 的 $2$ 的整数次幂。如果它们的宽度之和至少为 $s$ ，则能从中选出若干块，使总宽度恰好为 $s$ 。

证明时，将两块宽度相同的展板临时合并为一个宽度翻倍的整体，不断执行这一操作。每个整体都对应原来的一组展板，且这些组互不重叠。如果得到了宽度为 $s$ 的整体，其对应的原展板就是所需的集合。如果始终没有得到这样的整体，那么最终每种小于 $s$ 的宽度至多剩下一个整体，它们的总宽度最多为 $1+2+4+\cdots+s/2=s-1$ ，与原总宽度至少为 $s$ 矛盾。因此引理成立。临时合并仅用于证明，并不改变实际摆放规则。

下面证明：对于任意一批尚未摆放的展板，存在一个最优方案，使它的第一层与贪心算法所选的展板宽度和数量完全相同。

取一个最优方案，按照宽度从大到小调整它的第一层。设当前考虑的宽度为 $s$ ，所有大于 $s$ 的展板数量已经与贪心第一层一致。这些较大展板占用的宽度确定以后，贪心会放入尽可能多的宽度为 $s$ 的展板。原方案第一层中这种展板的数量不会超过贪心数量，因为两者受到相同的剩余容量和展板总数限制。

如果原方案第一层中的宽度为 $s$ 的展板还不够，就从其他某一层取来一块宽度为 $s$ 的展板。这样的展板一定存在，因为贪心数量不超过当前这批展板中宽度为 $s$ 的总数量。

设移动前第一层的空余宽度为 $F$ ，其中所有小于 $s$ 的展板的总宽度为 $B$ 。由于第一层还能在贪心目标中增加一块宽度为 $s$ 的展板，必有 $F+B\ge s$ 。如果 $F\ge s$ ，直接移入即可。如果 $F<s$ 且 $B\ge s$ ，根据引理，可以从第一层选出总宽度恰好为 $s$ 的小展板；如果 $F<s$ 且 $B<s$ ，就选出第一层的全部小展板，此时它们与原空余位置合起来至少能腾出宽度 $s$ 。

后两种情况中，将选出的小展板移到提供大展板的那一层，再将这块宽度为 $s$ 的展板移入第一层。移出的小展板总宽度不超过 $s$ ，能够放进另一层腾出的空间；第一层也腾出了足够空间。这个交换保持了每层合法，不增加层数，也不会改变第一层中已经确定的较大展板数量。

重复交换，可以让第一层中宽度为 $s$ 的展板数量达到贪心数量。再依次处理更小的宽度，就得到一个层数仍然最优、第一层与贪心完全一致的方案。

最后，对展板数量作归纳。没有展板时，算法使用 $0$ 层，显然最优。有展板时，设最优层数为 $H$ 。由上述交换过程，可以选取一个最优方案，使第一层恰好采用贪心摆法，其余展板在剩下的 $H-1$ 层中能够放完。第一层至少放入一块展板，所以剩余展板数量更少；由归纳假设，贪心处理剩余展板时使用的层数不超过 $H-1$ 。于是算法总共不超过 $H$ 层。算法给出的摆放始终合法，层数也不可能小于最优值 $H$ ，因此算法恰好使用最少层数。

复杂度分析

每块展板最多除以 $2$ 共 $19$ 次，统计宽度数量需要 $O(20n)$ 时间。每层枚举 $20$ 种宽度，最多开出 $n$ 层，所以摆放过程需要 $O(20n)$ 时间。每组数据的总时间复杂度为 $O(20n)$ ；设一份输入中所有展板数量之和为 $N=\sum n$ ，总时间复杂度为 $O(20N)$ 。

计数数组固定包含 $20$ 个元素，其他变量数量固定，额外空间复杂度为 $O(20)$ ，即常数空间。

参考代码

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

int main() {
    freopen("stable.in", "r", stdin);
    freopen("stable.out", "w", stdout);

    int t;
    cin >> t;
    while (t--) {
        int n, W;
        cin >> n >> W;
        int cnt[20] = {0};  // 每组重新统计各个宽度的展板数量

        for (int i = 0; i < n; i++) {
            int w;
            cin >> w;
            int p = 0;
            while (w > 1) {
                w /= 2;
                p++;
            }
            cnt[p]++;  // 原宽度为 2 的 p 次方
        }

        int rem = n;
        int ans = 0;
        while (rem > 0) {
            int r = W;  // 开始摆放新的一层
            for (int p = 19; p >= 0; p--) {
                int w = 1 << p;
                int k = min(cnt[p], r / w);
                cnt[p] -= k;  // 当前宽度能放多少块，就放多少块
                r -= k * w;
                rem -= k;
            }
            ans++;
        }

        cout << ans << '\n';
    }
    return 0;
}

C. 断连充能

解题思路

题意分析

设共有 $n$ 个装置，第 $i$ 个装置的能量为 $a_i$ 。每个装置只有选和不选两种决定，因此可以先考虑枚举所有选择方案。对于一个方案，检查是否存在连续三个都被选择的装置；如果方案合法，就计算能量总和并更新答案。一共有 $2^n$ 个方案，每个方案最多检查 $n$ 个装置，时间复杂度为 $O(n2^n)$ 。这个方法适用于 $n\le5$ 的子任务，但无法处理 $n=200000$ 的数据。

为了减少重复计算，按照从左到右的顺序处理装置。处理完前 $i$ 个装置后，下一个装置能不能选择，取决于当前末尾已经连续选择了几个装置。如果末尾连续选择了 $2$ 个，下一个就必须跳过；如果末尾连续选择了 $0$ 个或 $1$ 个，下一个仍然可以选择。

因此，把所有合法方案按照“末尾连续选择的数量”分成三类。令 $f_0,f_1,f_2$ 分别表示处理完当前前缀后，末尾连续选择 $0$ 个、 $1$ 个、 $2$ 个装置时，能够获得的最大能量总和。末尾连续选择 $0$ 个，表示当前最后一个装置没有被选择；末尾连续选择 $1$ 个，表示最后一个选择了，前一个没有选择；末尾连续选择 $2$ 个，表示最后两个都选择了。

这三个状态已经足够决定后续选择是否合法。对于末尾连续选择数量相同的两个方案，之后可以接上的选择完全相同；能量较小的方案，无论接上哪种后续选择，都不会优于能量较大的方案。因此，每一类只保留最大的能量总和，就能保留得到最优答案所需的信息。

假设已经处理完前 $i-1$ 个装置，三个旧状态为 $f_0,f_1,f_2$ ，当前装置的能量为 $a_i$ 。用 $g_0,g_1,g_2$ 保存处理完第 $i$ 个装置后的新状态。

如果不选择第 $i$ 个装置，末尾连续选择的数量变为 $0$ 。前面无论属于哪一类，都可以跳过当前装置，而且总能量不变，因此

$g_0=\max(f_0,f_1,f_2).$

如果选择第 $i$ 个装置，并使末尾恰好连续选择 $1$ 个，那么第 $i-1$ 个装置必须没有选择，前一状态只能是 $f_0$ ，因此

$g_1=f_0+a_i.$

如果选择第 $i$ 个装置，并使末尾恰好连续选择 $2$ 个，那么前一状态必须恰好连续选择了 $1$ 个，即来自 $f_1$ ，因此

$g_2=f_1+a_i.$

当 $f_1$ 不可达时， $g_2$ 也不可达。不能从 $f_2$ 继续选择当前装置，因为这会出现三个连续选择的装置。

三个新状态必须全部根据旧状态计算完成，再同时替换旧状态。如果刚算出 $g_0$ 就覆盖 $f_0$ ，随后计算 $g_1$ 时用到的就是已经处理过当前装置的状态，破坏了转移的含义。使用两组变量，可以明确区分处理当前装置前后的状态。

开始时还没有处理任何装置，只有一个都不选的方案，因此初始化为

$f_0=0,\qquad f_1=f_2=-\infty.$

这里的 $-\infty$ 表示不存在这种选择方案。代码用 long long 最小值的四分之一作为负无穷标记，它远小于任何合法能量总和；不可达的 $f_1$ 不参与加法，保证负无穷标记不会变成一个普通状态值。选择这个标记也避免直接使用最小整数参与算术时产生下溢。

每次跳过当前装置时，都可以继承之前的空选方案。因此， $f_0$ 始终至少为 $0$ ，全部装置能量为负数时，也会得到正确答案 $0$ 。

处理完全部装置后，合法方案的末尾连续选择数量只能是 $0$ 、 $1$ 或 $2$ ，答案为

$\max(f_0,f_1,f_2).$

每一轮只依赖上一轮的三个状态，可以使用滚动动态规划，只保存这三个值。装置的能量也可以一边读入一边处理。

部分分说明：

子任务 $1$ （ $1\le n\le5$ ）：枚举全部 $2^n$ 种选择方案，检查是否存在连续三个都被选择的装置，统计合法方案的能量总和并取最大值。每个方案需要 $O(n)$ 时间，总时间复杂度为 $O(n2^n)$ 。
子任务 $2$ （完整数据， $1\le n\le200000$ 、 $-10^9\le a_i\le10^9$ ）：使用末尾连续选择数量为 $0$ 、 $1$ 、 $2$ 的三个状态进行滚动动态规划，时间复杂度为 $O(n)$ ，可以处理全范围数据。

实现步骤

将状态 $f_0$ 初始化为 $0$ ，将 $f_1,f_2$ 初始化为负无穷，表示这两类方案还不存在。
从左到右遍历装置，设当前装置的能量为 $x$ ，用三个旧状态的最大值计算不选当前装置的新状态 $g_0$ 。
计算 $g_1=f_0+x$ ；如果 $f_1$ 可达，再计算 $g_2=f_1+x$ ，否则保持 $g_2$ 为负无穷。
三个新状态全部计算完成后，再令 $f_0=g_0$ 、 $f_1=g_1$ 、 $f_2=g_2$ ，继续处理下一个装置。
处理完全部装置后，输出三个状态的最大值。

正确性证明

证明在处理完前 $i$ 个装置后，对于每个 $j\in\{0,1,2\}$ ，状态 $f_j$ 都等于所有末尾连续选择 $j$ 个装置的合法方案中的最大能量总和；如果这一类方案不存在，对应状态为负无穷。

当 $i=0$ 时，还没有处理任何装置。只有一个都不选择的方案，能量为 $0$ ，末尾连续选择数量为 $0$ 。因此 $f_0=0$ 、 $f_1=f_2=-\infty$ ，结论成立。

假设处理完前 $i-1$ 个装置后结论成立，考虑第 $i$ 个装置。

若不选择第 $i$ 个装置，则新的末尾连续选择数量为 $0$ 。此前任意合法方案都可以直接跳过它，所以新状态的最优值为 $g_0=\max(f_0,f_1,f_2)$ 。

若选择第 $i$ 个装置，且新的末尾连续选择数量为 $1$ ，则此前末尾连续选择数量必须为 $0$ ；反过来，任意属于 $f_0$ 的合法方案选择当前装置后，都恰好属于这一类。因此新状态的最优值为 $g_1=f_0+a_i$ 。

若选择第 $i$ 个装置，且新的末尾连续选择数量为 $2$ ，则此前末尾连续选择数量必须为 $1$ ；任意属于 $f_1$ 的合法方案选择当前装置后，都恰好属于这一类。因此当 $f_1$ 可达时，新状态的最优值为 $g_2=f_1+a_i$ ；否则这一类方案不存在。

此前末尾连续选择数量为 $2$ 的方案，继续选择当前装置会违反限制，因此不能产生合法的新状态。上述三个转移覆盖了处理完前 $i$ 个装置后的全部合法方案，而且各自取到了对应类别中的最优值，归纳结论成立。

处理完全部 $n$ 个装置后，所有合法方案都属于这三类之一，空选方案也被保留。因此，输出 $\max(f_0,f_1,f_2)$ 就是满足要求的最大能量总和。

复杂度分析

每个装置只进行常数次比较和加法，时间复杂度为 $O(n)$ 。

算法只保存三个旧状态、三个新状态及少量变量，读入能量后立即处理，空间复杂度为 $O(1)$ 。

参考代码

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

int main() {
    freopen("chargebreak.in", "r", stdin);
    freopen("chargebreak.out", "w", stdout);

    int n;
    cin >> n;

    // 答案可能达到 2×10^14，状态值需要使用 long long。
    long long neg = numeric_limits<long long>::lowest() / 4;
    long long f0 = 0;
    long long f1 = neg;
    long long f2 = neg;

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;

        // 三个新状态都由处理当前装置之前的旧状态计算。
        long long g0 = max(f0, max(f1, f2)); // 不选当前装置。
        long long g1 = f0 + x;             // 末尾连续选择 1 个。
        long long g2 = neg;
        if (f1 != neg) {
            g2 = f1 + x;                  // 末尾连续选择 2 个。
        }

        f0 = g0;
        f1 = g1;
        f2 = g2;
    }

    cout << max(f0, max(f1, f2)) << '\n';
    return 0;
}

D. 三轨信号

解题思路

题意分析

设共有 $n$ 天，第 $i$ 天三种模式的基础分分别为 $a_i,b_i,c_i$ 。每天有三种选择，最直接的做法是枚举全部 $3^n$ 种安排。可以用深度优先搜索依次决定每天的模式，选择时加上当天基础分，再减去与前一天有关的切换费用。在搜索过程中累计得分，枚举完全部天数后更新答案。这种方法适合天数很少的情况，但无法处理 $n=100000$ 的数据。

观察切换规则可以发现，决定第 $i$ 天的得分变化时，只需要知道第 $i-1$ 天选了什么模式。更早几天的模式，只通过已经累积的得分影响答案。

假设有两种前 $i-1$ 天的安排，它们最后一天都选 A，但累计得分不同。此后接上完全相同的安排时，两者获得的后续基础分、支付的后续切换费用都相同。因此，原本得分较低的安排始终不会更优，可以只保留得分较高的安排。对于以 B、C 结尾的安排，也分别保留一个最大得分。

于是，按最后一天的模式分类，只需要维护三个动态规划状态。令 $f_i^A$ 表示前 $i$ 天全部安排完，并且第 $i$ 天选择 A 时的最大累计得分； $f_i^B$ 和 $f_i^C$ 分别表示最后一天选择 B、C 的对应最优值。

第一天没有切换费用，因此初始化为

$f_1^A=a_1,\qquad f_1^B=b_1,\qquad f_1^C=c_1.$

对于第 $i$ 天，如果今天选 A，昨天可能选 A、B 或 C。昨天选 A 时保持不变，不扣费用；昨天选 B 时，需要扣除 B 到 A 的费用 $ba_i$ ；昨天选 C 时，需要扣除 C 到 A 的费用 $ca_i$ 。再加上今天的基础分 $a_i$ ，得到

$f_i^A=a_i+\max\left(f_{i-1}^A,\ f_{i-1}^B-ba_i,\ f_{i-1}^C-ca_i\right).$

同理，今天选 B 时，需要考虑 A 到 B、保持 B、C 到 B 三种情况：

$f_i^B=b_i+\max\left(f_{i-1}^A-ab_i,\ f_{i-1}^B,\ f_{i-1}^C-cb_i\right).$

今天选 C 时，需要考虑 A 到 C、B 到 C、保持 C 三种情况：

$f_i^C=c_i+\max\left(f_{i-1}^A-ac_i,\ f_{i-1}^B-bc_i,\ f_{i-1}^C\right).$

计算当天状态时，只会用到前一天的三个状态，因此可以用三个变量滚动保存。代码中用 f0、f1、f2 分别保存以 A、B、C 结尾的旧状态，用 g0、g1、g2 保存新状态。先使用旧值计算三个新值，等三个新值都算完后，再一起替换旧值。如果算出新的 A 状态后就立即覆盖旧值，接下来计算 B、C 状态时就可能混入当天状态，破坏转移关系。

处理完全部 $n$ 天后，最后一天可以是任意模式，所以答案为

$\max\left(f_n^A,f_n^B,f_n^C\right).$

这些状态都要求已经为前面每一天选择了模式，因此即使累计得分为负数，也必须保留实际得到的最优值，不能用 $0$ 表示放弃安排。多天基础分和切换费用的累加会超出 int 范围，状态、基础分、费用以及转移中的差值统一使用 long long。

部分分说明：

子任务 $1$ （ $1\le n\le 5$ ）：枚举每天的三种模式，共 $3^n$ 种安排，逐一计算基础分与切换费用，取最大值。
子任务 $2$ （完整数据， $1\le n\le 100000$ ）：按最后一天的模式维护三个状态，使用线性动态规划，并用滚动变量将额外空间压到常数。

实现步骤

用第一天的三个基础分分别初始化三个状态；第一天不扣除切换费用。
从第二天开始，依次处理当天的三个基础分和六个有方向的切换费用。
使用前一天的三个状态，分别计算当天以 A、B、C 结尾的三个最大累计得分。
三个新值全部算完后，再统一替换三个旧状态，继续处理下一天。
处理完第 $n$ 天后，输出三个状态中的最大值。

正确性证明

对已处理的天数 $i$ 进行归纳，证明算法保存的三个状态分别等于前 $i$ 天以 A、B、C 结尾的最大累计得分。

当 $i=1$ 时，只有一天，每种结尾模式对应唯一的选择。第一天没有切换费用，因此三个状态分别等于 $a_1,b_1,c_1$ ，与定义一致。

假设处理完第 $i-1$ 天时，三个状态均已正确。考虑第 $i$ 天选择 A 的任意合法安排，前一天的模式一定是 A、B、C 中的一种。

如果前一天是 A，则今天不扣切换费用，最优得分为 $f_{i-1}^A+a_i$ 。如果前一天是 B，则今天扣除 $ba_i$ ，最优得分为 $f_{i-1}^B-ba_i+a_i$ 。如果前一天是 C，则今天扣除 $ca_i$ ，最优得分为 $f_{i-1}^C-ca_i+a_i$ 。根据归纳假设，这三种情况下使用的前一天状态都是各自类别中的最优值，且每一种转移都对应合法安排。三种情况覆盖了今天选择 A 的所有安排，因此取最大值恰好得到 $f_i^A$ 。

今天选择 B、C 时，同样按昨天的三种模式分类，并扣除对应方向的切换费用，就能分别得到正确的 $f_i^B,f_i^C$ 。算法先算出全部新状态，再替换旧状态，因此三条转移都基于正确的第 $i-1$ 天状态，归纳结论成立。

处理完第 $n$ 天后，每一种合法安排都以 A、B、C 中的一种模式结束。三个状态覆盖了所有合法安排，取其中最大值就是题目要求的最大最终得分。

复杂度分析

每天计算三个状态，每个状态只比较三个来源，因此总时间复杂度为 $O(n)$ 。

输入逐天读取，只保存前一天和当天的三个状态及当前输入的常数个数值，因此额外空间复杂度为 $O(1)$ 。

参考代码

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

int main() {
    freopen("signalswitch.in", "r", stdin);
    freopen("signalswitch.out", "w", stdout);

    int n;
    cin >> n;

    // 得分会跨多天累加，使用 long long 保存。
    // 第一天没有前一天，因此直接以三个基础分初始化。
    long long f0, f1, f2;
    cin >> f0 >> f1 >> f2;

    for (int i = 2; i <= n; i++) {
        long long a, b, c;
        long long ab, ac, ba, bc, ca, cb;
        cin >> a >> b >> c >> ab >> ac >> ba >> bc >> ca >> cb;

        // 三个旧状态都表示前一天结束后的最优得分。
        // 转入 A 要使用 B -> A 和 C -> A 对应的费用。
        long long g0 = a + max(f0, max(f1 - ba, f2 - ca));
        long long g1 = b + max(f0 - ab, max(f1, f2 - cb));
        long long g2 = c + max(f0 - ac, max(f1 - bc, f2));

        // 全部新状态算完后，再一起替换旧状态。
        f0 = g0;
        f1 = g1;
        f2 = g2;
    }

    // 最后一天可以选择任意一种模式。
    cout << max(f0, max(f1, f2)) << '\n';
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 7

暴力出奇迹，结果TLE
难度是什么，红黄红红吗

5天前来自上海
4
- MC_轩秦张—mcjs.link
  回复
  暴力出奇迹，结果TLE
  我觉得是红黄黄绿
  
  5天前来自浙江
  4
- 暴力出奇迹，结果TLE
  回复
  MC_轩秦张—mcjs.link
  后面两题明明很简单
  
  4天前来自上海
  3
- MYJ888
  回复
  MC_轩秦张—mcjs.link
  我觉得是红黄橙黄
  
  昨天来自浙江
  3
无名(本人，有关必回）
1

5天前来自浙江
2
稻中人
2

5天前来自浙江
2
稻中人
1

5天前来自浙江
2
florr--sftkFH.io
我跟你差不多，为什么4000ms TLE

昨天来自江苏
1
- florr--sftkFH.io
  回复
  florr--sftkFH.io
  对不起，没写freopen
  
  昨天来自江苏
  0
wl威龙
1

4天前来自浙江
0
干拉小子
3

4天前来自浙江
0