[JLOI2008] 提示问题

题意

给出一行由字母、标点和空格组成的答案字符串。

要求按题目规定，输出第 1、2、3 个提示。

提示的变化只针对字母位置，标点和空格保持不变。

思路

这题就是按规则直接模拟。

最直接的教学版写法如下：

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
70
71
72
73
74
75
76
77
78
79// brute.cpp：按题面三步规则逐步生成三个提示，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

string s;
string hint1, hint2, hint3;

bool is_letter(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool is_vowel(char ch) {
    return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
           ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
}

int round_nearest(int x, int y) {
    return (x + y / 2) / y;
}

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

    getline(cin, s);

    hint1 = s;
    int letter_cnt = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            hint1[i] = '.';
            letter_cnt++;
        }
    }

    hint2 = hint1;
    int show_first = round_nearest(letter_cnt, 3);
    int passed_letters = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            passed_letters++;
            if (passed_letters <= show_first) {
                hint2[i] = s[i];
            }
        }
    }

    hint3 = hint2;
    bool has_hidden_vowel = false;
    passed_letters = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            passed_letters++;
            if (passed_letters > show_first && is_vowel(s[i])) {
                hint3[i] = s[i];
                has_hidden_vowel = true;
            }
        }
    }

    if (!has_hidden_vowel) {
        hint3 = hint1;
        int show_two_third = round_nearest(letter_cnt * 2, 3);
        passed_letters = 0;
        for (int i = 0; i < (int) s.size(); i++) {
            if (is_letter(s[i])) {
                passed_letters++;
                if (passed_letters <= show_two_third) {
                    hint3[i] = s[i];
                }
            }
        }
    }

    cout << hint1 << '\n';
    cout << hint2 << '\n';
    cout << hint3 << '\n';
    return 0;
}

先生成第一个提示：所有字母都变成 .。

接着统计总字母数 letter_cnt，按字母顺序：

第二个提示显示前 round(letter_cnt / 3) 个字母；
第三个提示优先在剩余字母里显示元音；
如果剩余部分一个元音也没有，就改成从第一个提示出发，显示前 round(2 * letter_cnt / 3) 个字母。

整个过程都只需要线性扫描字符串。

代码

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
70
71
72
73
74
75
76
77
78
79#include <bits/stdc++.h>
using namespace std;

string s;

bool is_letter(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool is_vowel(char ch) {
    return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
           ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
}

int round_nearest(int x, int y) {
    return (x + y / 2) / y;
}

string hint1, hint2, hint3;

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

    getline(cin, s);

    hint1 = s;
    int letter_cnt = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            hint1[i] = '.';
            letter_cnt++;
        }
    }

    hint2 = hint1;
    int show_first = round_nearest(letter_cnt, 3);
    int passed_letters = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            passed_letters++;
            if (passed_letters <= show_first) {
                hint2[i] = s[i];
            }
        }
    }

    hint3 = hint2;
    bool has_hidden_vowel = false;
    passed_letters = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (is_letter(s[i])) {
            passed_letters++;
            if (passed_letters > show_first && is_vowel(s[i])) {
                hint3[i] = s[i];
                has_hidden_vowel = true;
            }
        }
    }

    if (!has_hidden_vowel) {
        hint3 = hint1;
        int show_two_third = round_nearest(letter_cnt * 2, 3);
        passed_letters = 0;
        for (int i = 0; i < (int) s.size(); i++) {
            if (is_letter(s[i])) {
                passed_letters++;
                if (passed_letters <= show_two_third) {
                    hint3[i] = s[i];
                }
            }
        }
    }

    cout << hint1 << '\n';
    cout << hint2 << '\n';
    cout << hint3 << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

总结

这题的关键是：

按字母计数，不按所有字符计数；
第三个提示要先尝试“剩余元音”，没有元音时再走备用规则。

[JLOI2008] 提示问题

目录

题意

思路

代码

复杂度

总结