[Solution] ABC456 A~F

前记

本次赛时顺利切到 F 题，G 题由于缺乏生成函数的前置知识惨败。有趣的是，这次的题目在背景上都充满了连贯性：A、B 题都和骰子有关，C、D 题都是字符串相邻去重计数，而 E、F、G 题全在讨论如何放假（高桥是有多想放假啊 雾）。

A - Dice

题意

投掷三个骰子，给定一个 x，问三个骰子的点数总和能否为 x。

1≤x≤201 \leq x \leq 20

思路

简单猜想一下，由于每个骰子的点数是 1∼61 \sim 6，3 个骰子的总和范围必然落在 [3,18][3, 18] 的闭区间内，范围以外的点数总和都是无法得到的。

代码部分

1
2
3
4
5
6
7
8
9
void solve( ) {
    int x;
    cin >> x;
    if( x < 3 || x > 18 ) {
        cout << "No" << '\n';
    } else {
        cout << "Yes" << '\n';
    }
}

B - 456

题意

同样给定三个骰子，同时给定三个骰子的六面，问三个骰子恰好是 4 5 6 的概率。

思路

考虑用古典概型计算。由于三个骰子的点数是独立事件，所以可以直接将各自出现的概率相乘。满足点数恰好为 {4,5,6}\{4, 5, 6\} 的排列共有 6 种情况：

(4,5,6)∣(4,6,5)∣(5,4,6)∣(5,6,4)∣(6,4,5)∣(6,5,4)(4,5,6) \mid (4,6,5) \mid (5,4,6) \mid (5,6,4) \mid (6,4,5) \mid (6,5,4)

分别统计每个骰子掷出 4、5、6 的面数，按照这 6 种组合情况累加概率即可。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve( ) {
    for( int i = 1; i <= 3; ++ i ) {
        for( int j = 1; j <= 6; ++ j ) {
            cin >> a[i][j];
            if( a[i][j] == 4 ) cnt[i][4] ++;
            if( a[i][j] == 5 ) cnt[i][5] ++;
            if( a[i][j] == 6 ) cnt[i][6] ++;
        }
    }

    double ans = 0;

	// 216 = 6 * 6 * 6
    ans += cnt[1][4] * cnt[2][5] * cnt[3][6] / 216.0;
    ans += cnt[1][4] * cnt[2][6] * cnt[3][5] / 216.0;

    ans += cnt[1][5] * cnt[2][6] * cnt[3][4] / 216.0;
    ans += cnt[1][5] * cnt[2][4] * cnt[3][6] / 216.0;
    
    ans += cnt[1][6] * cnt[2][4] * cnt[3][5] / 216.0;
    ans += cnt[1][6] * cnt[2][5] * cnt[3][4] / 216.0;

    cout << fixed << setprecision( 10 ) << ans << '\n';
}

C - Not Adjacent

题意

给定一个包含 a b c 的字符串，问，存在多少子串满足相邻两个字符不同。

思路

注意到是子串，因此必定是连续的，假设在某一个区间 [l,r][l,r] 中 Si≠Si+1S_{i} \neq S_{i+1}，那么所有子串都满足条件，个数也就是 len=r−l+1,cnt=(len)∗(len+1)2len = r - l + 1, cnt = \frac{(len)*(len+1)}{2}。

如果 Si==Si+1S_{i} == S_{i+1} 会怎么样呢？根据子串连续性的定义，ii 和 i+1i+1 必定是不能连在一起的，所以分开计算两段的子串个数即可。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve( ) {
    string s;
    cin >> s;
    int n = s.length( );
    ll len = 1, ans = 0;
    for( int i = 1; i < n; i ++ ) {
        if( s[i] != s[i-1] ) {
            len ++;
        } else {
            ans = ( ans + len * (len + 1)  / 2 ) % mod;
            len = 1;
        }
    }
    ans = ( ans + len * (len + 1)  / 2 ) % mod;
    cout << ans << '\n';
}

D - Not Adjacent 2

题意

给定一个包含 a b c 的字符串，问，存在多少子序列满足相邻两个字符不同。

思路

这题把条件放宽到了“子序列”。子序列允许中间有字符跳过（不连续），但必须保持原有的先后顺序。这是一道典型的计数类 DP。为什么会想到用 DP 呢？

  • 子序列性质：当我们按顺序扫描字符串，对于当前位置的字符 S[i]S[i]，它是否能合法地接在某个已有的子序列后面，仅仅取决于该子序列的最后一个字符是什么。
  • 无后效性：一旦确定了以某种字符结尾的子序列数量，我们不需要关心这些子序列内部的具体构成。

我们定义状态 fafa：当前以 'a' 结尾的合法子序列总数， fb,fcfb, fc 同理。由于子序列不要求连续，因此转移也不要求连续，所以当前 S[i]S[i] 可以接到任何一个结尾不为 S[i]S[i] 的子序列后面。状态转移为 fa=(fb+fc+1)fa = (fb + fc + 1)，这个 +1 是因为它本身也可以是一个子序列。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve( ) {
    string s;
    cin >> s;
    int n = s.length( );

    ll fa = 0, fb = 0, fc = 0;
    for( int i = 0; i < n; i ++ ) {
        if( s[i] == 'a' ) {
            ll cnt = (fb + fc + 1) % mod;
            fa = (fa + cnt) % mod;
        } else if( s[i] == 'b' ) {
            ll cnt = (fa + fc + 1) % mod;
            fb = (fb + cnt) % mod;
        } else {
            ll cnt = (fa + fb + 1) % mod;
            fc = (fc + cnt) % mod;
        }
    }
    cout << (fa + fb + fc) % mod << '\n';
}

E - Endless Holidays

题意

有 NN 个城市，MM 条双向道路。一个星期有 WW 天。 每个城市都有自己的假期安排。高桥每天可以选择 留在该城市 或者 相邻的城市。 问：高桥能否从第 11 天，找到一种策略，使得他永远在放假。（羡慕了）

N≤105,M≤105,W≤10N \leq 10^5, M \leq 10^5, W \leq 10。

思路

这也是一道典题，典型的分层图建模 + 判环。

为什么是分层图？在一般的图论中，节点就是纯粹的“城市”。而在这道题中，限制高桥行动的不仅有“空间”（他在哪个城市），还有“时间”（今天是星期几，不同城市的放假情况不同）。所以，不能单纯只用“城市”来作为图的节点，必须把“时间”维度也扩展进去。

接着我们通过数据规模验证，发现 W≤10W\leq10，完美满足条件。所以我们就用一个二维状态来表示一个节点 (u,d)(u, d)，在城市 uu，今天是第 dd 天。由于有 NN 个城市，WW 天，所以整个图就有 N×WN \times W 个节点，也就是把图分成了 WW 层，这就是所谓的分层图。

说完分层图的节点之后，考虑如何连边。由于每天可以不移动或者去相邻的城市，而且我们要找的路线是每天都是放假，如果当前城市明天的状态是放假，就可以连一条指向明天该城市的有向边；如果相邻城市的明天是放假，也连一条有向边。注意边一定是有向边，因为时间不可逆。

建模完成后，回归问题本质。题目要求能“永远”放假，在一个只有 N×WN \times W 个有限节点的有向图里走无限步，根据鸽巢原理，意味着路径必定走入了一个环！ 所以我们只需要在建好的图上做一遍 DFS 搜环即可。给每个到达的点打上访问标记（正在访问 / 已访问完毕），如果在搜索过程中碰到“正在访问”的节点，就说明成功找到了环。

当然也可以用 BFS，或者拓扑排序（因为这是个有向图），如果拓完还有多余的点，那就说明有环，具体证明不展开了。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
vector< int > adj[maxn];
string s[maxn];
// 0 not visited | 1 visiting | 2 visited
// 我这里没开二维数组，用一维压缩了状态 (u, d) -> u * w + d
int vis[maxn * 10];
int n, m, w;

bool dfs( int uid ) {
    vis[uid] = 1;

	// 解码出一维状态里对应的 u, d
    int u = uid / w;
    int d = uid % w;
    int nxt = (d + 1) % w;

    // 停留原地
    if( s[u][nxt] == 'o' ) {
        int vid = u * w + nxt;
        if( vis[vid] == 1 ) return 1;
        if( vis[vid] == 0 ) if( dfs( vid ) ) return 1;
    }

    // 去相邻城市
    for( int v : adj[u] ) {
        if( s[v][nxt] == 'o' ) {
            int vid = v * w + nxt;
            if( vis[vid] == 1 ) return 1;
            if( vis[vid] == 0 ) if( dfs( vid ) ) return 1;
        }
    }
    vis[uid] = 2;
    return 0;
}

void solve( ) {
    cin >> n >> m;

    for( int i = 0; i < n; ++ i ) adj[i].clear( );

    for( int i = 0; i < m; ++ i ) {
        int u, v; cin >> u >> v;
	    // 使用 0-index 是为了方便后续压缩成一维状态时的除法和取模运算
        u --, v --;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    cin >> w;
    for( int i = 0; i < n; ++ i ) cin >> s[i];

    int tot = n * w;
    fill( vis, vis + tot, 0 );

    for( int i = 0; i < n; ++ i ) {
	    // 从每个第一天就放假的城市出发
        if( s[i][0] == 'o' ) {
            int stid = i * w + 0;
            if( vis[stid] == 0 ) {
                if( dfs( stid ) ) {
                    cout << "Yes" << '\n';
                    return;
                }
            }
        }
    }
    cout << "No" << '\n';
    return;
}

F - Plan Holidays

题意

高桥想安排 NN 天的假期。最开始都不是假期。操作1：花 AiA_i 的代价让第 ii 天变成假期。 操作2：如果第 i−1i-1 天和第 i+1i+1 天都是假期，那么可以免费让第 ii 天变成假期。问：要制造一个长度至少为 KK 的连续假期，最少需要多少代价？

N,K≤2e5N, K \leq 2e5

思路

根据数据范围 N≤2×105N \leq 2 \times 10^5 盲猜，这题只能用 O(Nlog⁡N)O(N \log N)、O(Nlog⁡K)O(N \log K) 带 Log 的写法，或者干脆是 O(N)O(N)。

进一步分析，如果要构造一段完美的连续假期，这段区间有什么特殊的性质吗？手搓几个小样例会发现以下三个关键性质：

  1. 端点必须买：区间的两端没有办法通过相邻元素的条件来免费白嫖。
  2. 不能有连续的不买：如果有连续两天都不买，它们会互相卡住，导致谁也无法免费变成假期。
  3. 只需要考虑区间长度为 KK 和 K+1K + 1 即可。

第三个性质的观察源于第一个样例： 5 2 // 3 1 4 1 5 // res = 2 在这个样例中，可以买下 [2,4][2,4] 两天，然后 [3][3] 就免费了，直接凑出了长度为 3 的区间。再往后推导，考察更长的区间（比如 K+2K+2）有意义吗？其实并没有。任何 ≥K+2\geq K+2 的合法区间，我们都可以通过去掉最边缘的元素，无损降级转换成 KK 和 K+1K + 1 长度的情况，且代价不会变得更劣。

接下来开始正式推导了

解法零 DP O(NK)O(NK) - TLE

由于每个点只有 买 和 不买 两种状态，且 当前状态只与上一个点的状态 有关，性质 2，这显然是个动态规划。

记 dp[0]dp[0] 为当前点不买（前一个点必须买），dp[1]dp[1] 为当前点必须买。那么很显然就能推导出这个状态转移方程（递推式）：

dp[i][0]=dp[i−1][1]dp[i][1]=min⁡(dp[i−1][0],dp[i−1][1])+a[i]\begin{align} dp[i][0] &= dp[i-1][1] \\ dp[i][1] &= \min( dp[i-1][0], dp[i-1][1] ) + a[i] \end{align}

基于上述逻辑，我们很容易写出一个枚举起点的 O(NK)O(NK) 暴力 DP，但由于状态数过多，自然就 TLE 了。那么，如何优化呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve( ) {
    cin >> n >> k;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    ll ans = inf;

    for( int l = 1; l <= n - k + 1; ++ l ) {
        // k days
        ll dp0 = inf, dp1 = a[l];
        for( int i = l + 1; i <= l + k - 1; ++ i ) {
            ll nxtdp0 = dp1;
            ll nxtdp1 = min( dp0, dp1 ) + a[i];
            dp0 = nxtdp0;
            dp1 = nxtdp1;
        }
        ans = min( ans, dp1 );

        // k + 1 days
        if( l + k <= n ) {
            int i = l + k;
            ll nxtdp0 = dp1;
            ll nxtdp1 = min( dp0, dp1 ) + a[i];
            dp0 = nxtdp0;
            dp1 = nxtdp1;
        }
        ans = min( ans, dp1 );
    }

    cout << ans << '\n';
}
解法一：DDP（矩阵线段树） O(Nlog⁡N)O(N \log N)

为什么会想到 DDP？ -- 核心在于矩阵加速 -- 观察上面的 DP 转移，我们发现，随着窗口不断向右滑动，针对同一个数组 AA，我们在反复执行完全相同的一组递推转移方程。就像斐波那契数列那样，这种反复的带有递推关系的方程，我们的直觉大概会告诉我们，能不能用矩阵来加速递推呢？

接着引入广义矩阵乘法，常规的矩阵乘法是 Ci,j=∑(Ai,k×Bk,j)C_{i,j} = \sum(A_{i,k} \times B_{k,j})，但是在我们的转移方程中，核心操作是取 min 和 加法 +，我们可以把常规乘法里的 + 用 min 替代，常规乘法里的 * 用 + 替代，即 Ci,j=min⁡k(Ai,k+Bk,j)C_{i,j} = \min_{k} (A_{i,k} + B_{k,j})。

数学上可以证明这样定义的矩阵乘法是满足 结合律 的，而说到结合律，你会想到什么数据结构来维护呢？答案是 线段树。

然后构建状态矩阵，我们将状态写成列向量 [dp[i][0]dp[i][1]]\begin{bmatrix} dp[i][0] \\ dp[i][1] \end{bmatrix}。 尝试构造一个 2×22 \times 2 的转移矩阵 MiM_i，使得：

[dp[i][0]dp[i][1]]=Mi⊗[dp[i−1][0]dp[i−1][1]]\begin{bmatrix} dp[i][0] \\ dp[i][1] \end{bmatrix} = M_i \otimes \begin{bmatrix} dp[i-1][0] \\ dp[i-1][1] \end{bmatrix}

根据原方程：

dp[i][0]=min⁡(∞+dp[i−1][0],0+dp[i−1][1])dp[i][1]=min⁡(a[i]+dp[i−1][0],a[i]+dp[i−1][1])\begin{align} dp[i][0] = \min(\infty + dp[i-1][0], 0 + dp[i-1][1]) \\ dp[i][1] = \min(a[i] + dp[i-1][0], a[i] + dp[i-1][1]) \end{align}

可以通过待定系数法求解这个转移矩阵 MiM_{i}。

Mi=[∞0a[i]a[i]]M_i = \begin{bmatrix} \infty & 0 \\ a[i] & a[i] \end{bmatrix}

既然有了状态转移矩阵，要求某一段区间 [L+1,R−1][L+1, R-1] 的 DP 结果，其实就是求这段区间对应的矩阵连乘积！由于矩阵乘法满足结合律，我们可以建一棵线段树，每个节点维护对应区间的 MiM_i 连乘积。

枚举左端点 LL（强制买 ALA_L），右端点 RR（强制买 ARA_R），中间部分的转移代价只需要 O(log⁡N)O(\log N) 的时间在线段树上查询矩阵乘积，就可以将复杂度从 O(NK)O(NK) 降维到 O(Nlog⁡N)O(N \log N) 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;
const ll inf = 1e18;

ll a[maxn], n, k;

struct Mat {
    ll m[2][2];
    Mat( ) { m[0][0] = m[0][1] = m[1][0] = m[1][1] = inf; }
} tr[maxn << 2];

Mat merge( const Mat &a, const Mat &b ) {
    Mat res;
    for( int i = 0; i < 2; ++ i ) {
        for( int j = 0; j < 2; ++ j )
            for( int k = 0; k < 2; ++ k ) {
                if( a.m[i][k] == inf || b.m[k][j] == inf ) continue;
                res.m[i][j] = min( res.m[i][j], a.m[i][k] + b.m[k][j] );
            }
    }
    return res;
}

#define ls u << 1
#define rs u << 1 | 1

void build( int u, int l, int r ) {
    if( l == r ) {
        tr[u].m[0][0] = inf;
        tr[u].m[0][1] = 0;
        tr[u].m[1][0] = a[l];
        tr[u].m[1][1] = a[l];
        return;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
    tr[u] = merge( tr[ls], tr[rs] );
}

Mat query( int u, int l, int r, int ql, int qr ) {
    if( ql <= l && r <= qr ) return tr[u];
    int mid = ( l + r ) >> 1;
    if( qr <= mid ) return query( ls, l, mid, ql, qr );
    if( ql > mid ) return query( rs, mid + 1, r, ql, qr );
    return merge( query( ls, l, mid, ql, qr ), query( rs, mid + 1, r, ql, qr ) );
}

void solve( ) {
    cin >> n >> k;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    
    build( 1, 1, n );
    ll ans = inf;
    
    int len = k;
    for( int l = 1; l <= n - len + 1; ++ l ) {
        int r = l + len - 1;
        if( r == l ) {
            ans = min( ans, a[l] );
            continue;
        }
        if( r - l <= 1 ) {
            ans = min( ans, a[l] + a[r] );
            continue;
        }
        Mat T = query( 1, 1, n, l + 1, r - 1 );
        ll res = min( T.m[1][1], T.m[0][1] ) + a[l] + a[r];
        ans = min( ans, res );
    }

    len = k + 1;
    for( int l = 1; l <= n - len + 1; ++ l ) {
        int r = l + len - 1;
        if( r == l ) {
            ans = min( ans, a[l] );
            continue;
        }
        if( r - l <= 1 ) {
            ans = min( ans, a[l] + a[r] );
            continue;
        }
        Mat T = query( 1, 1, n, l + 1, r - 1 );
        ll res = min( T.m[1][1], T.m[0][1] ) + a[l] + a[r];
        ans = min( ans, res );
    }

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

int main( ) {
    cin.tie( 0 )->sync_with_stdio( 0 );
    int _t = 1; cin >> _t;
    while( _t -- ) solve( );
    return 0;
}
解法二：双栈模拟队列 —— 复杂度 O(N)O(N)

该做法理论可行，题解中也有提到，但受限于本人理解水平有限，不能详细展开讲解，见谅。理论就是用滑动窗口的思想，然后用前缀积来处理区间。

既然我们是在做一个 “定长滑动窗口” 的矩阵连乘，我们可以把线段树的 O(log⁡N)O(\log N) 优化掉。 这里有一个很经典的 Trick：使用两个栈来模拟一个滑动窗口。

  1. 我们维护两个栈 S1S_1 和 S2S_2。S1S_1 用于在队尾压入元素，S2S_2 用于从队头弹出元素。
  2. 栈内不仅存元素本身，还顺便存下该栈底到当前元素的矩阵前缀积。
  3. 当窗口滑动需要弹出队头时，如果 S2S_2 有元素，直接弹出；如果 S2S_2 为空，就把 S1S_1 的元素全部倒腾到 S2S_2 中，并在倒入的过程中重新计算 S2S_2 的矩阵前缀积。
  4. 窗口的整体矩阵乘积 = S2S_2 的栈顶前缀积 ⊗\otimes S1S_1 的栈顶前缀积。

由于每个矩阵最多入栈 2 次、出栈 2 次，均摊后矩阵乘法的次数是 O(1)O(1) 的，这样就能把复杂度优化成 O(N)O(N)。

新题解 > ABC
[Solution] ABC456 A~F
http://miqiu.space/posts/90bd9ef3/
作者
Miqiu
发布于
2026年5月4日
许可协议