NOTE
比赛链接：Atcoder Beginner Contest 459

A - Hell, World!#

关键词：签到

Code#

1
// Problem: AT ABC459 A
2
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2026  (AtCoder Beginner Contest 459)
3
// URL: https://atcoder.jp/contests/abc459/tasks/abc459_a
4
// Time: 2026-05-23 22:11:25
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30
    string s = "HelloWorld";
31
    for (int i = 0; i < 10; i++)
32
    {
33
        if (i == n - 1)
34
            continue;
35
        cout << s[i];
36
    }
37
}
38

39
int main()
40
{
41
    fastio();
42

43
    int T = 1;
44
    // cin >> T;
45

46
    while (T--)
47
        solve();
48

49
    return 0;
50
}

B - 459#

关键词：签到

Code#

1
// Problem: AT ABC459 B
2
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2026  (AtCoder Beginner Contest 459)
3
// URL: https://atcoder.jp/contests/abc459/tasks/abc459_b
4
// Time: 2026-05-23 22:13:23
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> res;
32

33
    while (n--)
34
    {
35
        string s;
36
        cin >> s;
37

38
        if (s[0] >= 'a' && s[0] <= 'c')
39
            res.emplace_back(2);
40
        else if (s[0] >= 'd' && s[0] <= 'f')
41
            res.emplace_back(3);
42
        else if (s[0] >= 'g' && s[0] <= 'i')
43
            res.emplace_back(4);
44
        else if (s[0] >= 'j' && s[0] <= 'l')
45
            res.emplace_back(5);
46
        else if (s[0] >= 'm' && s[0] <= 'o')
47
            res.emplace_back(6);
48
        else if (s[0] >= 'p' && s[0] <= 's')
49
            res.emplace_back(7);
50
        else if (s[0] >= 't' && s[0] <= 'v')
51
            res.emplace_back(8);
52
        else if (s[0] >= 'w' && s[0] <= 'z')
53
            res.emplace_back(9);
54
    }
55

56
    for (auto i: res)
57
        cout << i;
58
}
59

60
int main()
61
{
62
    fastio();
63

64
    int T = 1;
65
    // cin >> T;
66

67
    while (T--)
68
        solve();
69

70
    return 0;
71
}

C - Drop Blocks#

关键词：思维

思路#

通过记录“历史总增加量”和“全局被消除的层数”，我们可以把每次操作的时间复杂度降到 $O(1)$ 。

a[i]：第 $i$ 个格子历史上总共被放入过多少个积木（不考虑被消除的操作）。

b[k]：目前为止，历史总放入积木数 $\ge k$ 的格子有多少个。

注意：这里是不扣减消除操作的。例如 b[3] = 2 代表有 2 个格子至少被放进过 3 次积木。

h：全局触发了多少次“消除操作”。可以把它理解为“水位线”。

操作 $1$ 的逻辑如下：

a[i]++：给第 $i$ 个格子的历史总数 $+1$ 。
b[a[i]]++：因为第 $i$ 个格子的历史总数到达了 a[i]，所以 ++。
if (b[a[i]] == n) h++;：当所有 $N$ 个格子的积木数都 $\ge 1$ 时，触发“全部格子减 1”。换成历史数据来看，就是当所有 $N$ 个格子的历史总数都 $\ge h + 1$ 时触发消除。由于每次只加 1 个积木，触发消除条件的那一瞬间，必定是目前积木最少的那个格子刚好补齐了短板。所以此时的 a[i] 恰好就是 $h + 1$ 。当 b[a[i]] == n 时，说明 $n$ 个格子历史总数都达到了当前高度，全局消除次数 h 增加 1。

操作 $2$ 的逻辑如下：

题目要求输出当前积木数 $\ge y$ 的格子数量，格子的当前积木数 = 历史总增加量 (a[x]) - 全局消除量 (h)。所以，条件 当前积木数 >= y 等价于 a[x] - h >= y，移项后得到 a[x] >= h + y。所以 b[h + y] 恰好就是“历史总增加量 $\ge h + y$ 的格子数量”

NOTE
由于 h + i 的最大值可以达到 $6 \times 10^5$ ，代码上注意数组要开大点。

Code#

1
// Problem: AT ABC459 C
2
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2026  (AtCoder Beginner Contest 459)
3
// URL: https://atcoder.jp/contests/abc459/tasks/abc459_c
4
// Time: 2026-05-23 22:17:08
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 1e6 + 10;
25

26
int a[N], b[N];
27

28
void solve()
29
{
30
    int n, q;
31
    cin >> n >> q;
32

33
    ll h = 0;
34

35
    while (q--)
36
    {
37
        int op, i;
38
        cin >> op >> i;
39

40
        if (op == 1)
41
        {
42
            a[i]++;
43
            b[a[i]]++;
44
            if (b[a[i]] == n)
45
                h++;
46
        }
47
        else
48
            cout << b[h + i] << endl;
49
    }
50
}
51

52
int main()
53
{
54
    fastio();
55

56
    int T = 1;
57
    // cin >> T;
58

59
    while (T--)
60
        solve();
61

62
    return 0;
63
}

D - Adjacent Distinct String#

关键词：构造，贪心

思路#

能不能成功重排，取决于出现次数最多的那个字符。假如在长度为 $N$ 的字符串中，某个字符出现了 $M$ 次，为了让这个字符不相邻，最优的摆放方式就是隔一个一放，位置只有 $\lfloor (N + 1) / 2 \rfloor$ 个，因此如果所有字符出现的次数最大值 $M > \lfloor (N + 1) / 2 \rfloor$ ，则一定无解。

确认有解后，我们考虑构造方案：

统计并排序：统计每个字符的出现次数，然后按出现次数从大到小对字符进行排序。
先填偶数位：把排序后的字符依次填入新字符串的偶数索引位置（ $0, 2, 4 \dots$ ）。
再填奇数位：当偶数位全部填满后，回到开头，继续把剩下的字符填入奇数索引位置（ $1, 3, 5 \dots$ ）。

Code#

1
// Problem: AT ABC459 D
2
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2026  (AtCoder Beginner Contest 459)
3
// URL: https://atcoder.jp/contests/abc459/tasks/abc459_d
4
// Time: 2026-05-23 22:51:34
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    string s;
29
    cin >> s;
30
    int n = s.length();
31

32
    // pair<出现次数, 字符>
33
    vector<pair<int, char>> cnt(26);
34
    for (int i = 0; i < 26; i++)
35
        cnt[i] = {0, i + 'a'};
36

37
    for (char c: s)
38
        cnt[c - 'a'].first++;
39

40
    sort(cnt.begin(), cnt.end(), greater<pair<int, char>>());
41

42
    if (cnt[0].first > (n + 1) / 2)
43
    {
44
        cout << "No" << endl;
45
        return;
46
    }
47

48
    string res(n, ' ');
49
    int idx = 0;
50

51
    for (int i = 0; i < 26; i++)
52
    {
53
        while (cnt[i].first > 0)
54
        {
55
            res[idx] = cnt[i].second;
56
            cnt[i].first--;
57
            idx += 2;
58

59
            // 如果偶数位填满了，回到开头填奇数位
60
            if (idx >= n)
61
                idx = 1;
62
        }
63
    }
64

65
    cout << "Yes" << endl << res << endl;
66
}
67

68
int main()
69
{
70
    fastio();
71

72
    int T = 1;
73
    cin >> T;
74

75
    while (T--)
76
        solve();
77

78
    return 0;
79
}