Photoshoot

题意

给定一个长度为偶数的 $G/H$ 字符串。一次操作可以选择一个偶数长度前缀并反转。

目标是让偶数位置上的 G 尽可能多，并求达到这个目标所需的最少操作次数。

思路

暴力想法

小数据可以把每个字符串看成一个状态，用 BFS 枚举所有偶数长度前缀反转，找出最大得分下的最少步数：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:14
 * update_at: 2026-07-11 13:17
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
string start_s;

int calc_score(string cur) {
    int cnt = 0;
    for (int i = 1; i < n; i += 2) {
        if (cur[i] == 'G') {
            cnt++;
        }
    }
    return cnt;
}

string do_reverse_prefix(string cur, int len) {
    reverse(cur.begin(), cur.begin() + len);
    return cur;
}

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

    cin >> n >> start_s;

    queue<string> q;
    map<string, int> dist;

    q.push(start_s);
    dist[start_s] = 0;

    int best_score = -1;
    int best_steps = 0;

    while (!q.empty()) {
        string cur = q.front();
        q.pop();

        int steps = dist[cur];
        int score = calc_score(cur);
        if (score > best_score || (score == best_score && steps < best_steps)) {
            best_score = score;
            best_steps = steps;
        }

        // 枚举所有偶数长度前缀反转，遍历小数据下所有可达状态。
        for (int len = 2; len <= n; len += 2) {
            string nxt = do_reverse_prefix(cur, len);
            if (dist.count(nxt) == 0) {
                dist[nxt] = steps + 1;
                q.push(nxt);
            }
        }
    }

    cout << best_steps << '\n';

    return 0;
}

这个方法能帮助理解操作，但状态数太大，不能用于满数据。

成对压缩

按 (1,2),(3,4),... 把字符串分组。

一组里面：

GG 和 HH 不提供方向信息，可以忽略；
GH 和 HG 才表示这一组的方向。

官方解析的做法是把这些不同字符组压缩成方向序列，并把连续相同方向合并。

例如样例：

text

1
2
3GG | GH | GH | HG | HH | HG | HG
忽略相同组后：G, G, H, H
合并连续相同方向：G, H

代码里不需要真的建出这个序列，只要扫描每一组。如果 s[i] != s[i+1]，并且 s[i] 和上一段方向不同，就说明出现了一个新段，答案加一。

最后如果压缩序列的末段方向是 H，说明最后这段本来就是 HG，其中 G 已经在偶数位，不需要额外反转，所以答案减一。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:14
 * update_at: 2026-07-11 13:17
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

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

    cin >> n >> s;

    int answer = 0;
    char last = '.';

    // 每两个位置成一组：相同的组无影响，不同的组只关心首字符变化。
    for (int i = 0; i < n; i += 2) {
        if (s[i] != s[i + 1]) {
            if (s[i] != last) {
                answer++;
                last = s[i];
            }
        }
    }

    // 末尾为 H 的最后一段已经天然满足目标，不需要额外反转。
    if (last == 'H') {
        answer--;
    }

    cout << answer << '\n';

    return 0;
}

复杂度

每两个字符处理一次，时间复杂度为 $O(N)$ 。

只保存输入字符串，额外空间复杂度为 $O(1)$ 。

总结

这题的关键是不要直接模拟反转，而是观察偶数长度前缀反转对“两两分组”的影响。

相同字符组可以忽略，连续同方向组可以合并，最终只需要统计压缩后的方向段数。

目录

题意

思路

暴力想法

成对压缩

代码

复杂度

总结