NOTE
比赛链接：Atcoder Beginner Contest 456

A - Dice#

关键词：签到

思路#

显然三个骰子可以扔出的点数满足 $3 \leqslant x \leqslant 18$ 。

Code#

1
// Problem: AT ABC456 A
2
// Contest: AtCoder - AtCoder Beginner Contest 456
3
// URL: https://atcoder.jp/contests/abc456/tasks/abc456_a
4
// Time: 2026-05-03 12:12:03
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
int main()
22
{
23
    int x;
24
    cin >> x;
25

26
    if (x >= 3 && x <= 18)
27
        cout << "Yes" << endl;
28
    else
29
        cout << "No" << endl;
30

31
    return 0;
32
}

B - 456#

关键词：暴力，签到

思路#

总共有 216 种情况，暴力枚举判断即可。

Code#

1
// Problem: AT ABC456 B
2
// Contest: AtCoder - AtCoder Beginner Contest 456
3
// URL: https://atcoder.jp/contests/abc456/tasks/abc456_b
4
// Time: 2026-05-03 12:12:04
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 6;
20

21
int a[3][N];
22

23
int main()
24
{
25
    for (int i = 0; i < 3; i++)
26
        for (int j = 0; j < 6; j++)
27
            cin >> a[i][j];
28

29
    int res = 0;
30
    for (int i = 0; i < 6; i++)
31
        for (int j = 0; j < 6; j++)
32
            for (int k = 0; k < 6; k++)
33
            {
34
                if ((a[0][i] == 4 && a[1][j] == 5 && a[2][k] == 6) || (a[0][i] == 4 && a[1][j] == 6 && a[2][k] == 5) ||
35
                    (a[0][i] == 5 && a[1][j] == 4 && a[2][k] == 6) || (a[0][i] == 5 && a[1][j] == 6 && a[2][k] == 4) ||
36
                    (a[0][i] == 6 && a[1][j] == 4 && a[2][k] == 5) || (a[0][i] == 6 && a[1][j] == 5 && a[2][k] == 4))
37
                    res++;
38
            }
39
    cout << fixed << setprecision(10) << 1.0 * res / 216 << endl;
40
    return 0;
41
}

C - Not Adjacent#

关键词：思维、模拟

思路#

如果存在 $S_i=S_{i+1}$ 的位置，这两个字符不能同时选取，因此答案可以通过在第 $i$ 个与第 $i+1$ 个字符之间分割，计算每个块的数量并求和得到。

1
 If S = abbcabcbaaabc
2
    ab|bcabcba|a|abc
3
    3 +  28 + 1 + 6 = 38

Code#

1
// Problem: AT ABC456 C
2
// Contest: AtCoder - AtCoder Beginner Contest 456
3
// URL: https://atcoder.jp/contests/abc456/tasks/abc456_c
4
// Time: 2026-05-03 12:12:05
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20
const int mod = 998244353;
21

22
int main()
23
{
24
    string s;
25
    cin >> s;
26

27
    int n = (int) s.size();
28

29
    ll res = 0, idx = 0;
30

31
    for (int i = 0; i < n; i++)
32
    {
33
        if (s[i] == s[i + 1] || i + 1 == n)
34
        {
35
            res += (ll) (i - idx + 1) * (i - idx + 2) / 2;
36
            idx = i + 1;
37
        }
38
    }
39

40
    cout << res % mod << endl;
41
    return 0;
42
}

D - Not Adjacent 2#

关键词：DP，统计子序列

思路#

在构建子序列时，当我们想要把当前字符（比如 a）加入到某个现有的子序列末尾时，我们只关心这个现有的子序列，最后一个字符是什么。这就提示我们，必须把 DP 的状态按照“以什么字符结尾”来进行分类。

因为字符集只有 a, b, c 三个字符，我们可以只维护三个变量：

$dp[a]$ ：表示目前为止，以字符 a 结尾的合法子序列数量。
$dp[b]$ ：表示目前为止，以字符 b 结尾的合法子序列数量。
$dp[c]$ ：表示目前为止，以字符 c 结尾的合法子序列数量。

假设我们现在从左到右遍历字符串，当前遇到了一个字符 a，我们该如何更新这三个变量呢？

对于以 a 结尾的子序列，它的来源有四部分：

旧的序列：之前已经构成的以 a 结尾的子序列。因为我们是“子序列”提取，我们可以选择不把当前这个 a 纳入进来，所以原来的 $dp[a]$ 个子序列依然存在且合法。
自立门户：当前这个字符 a 自己单独组成一个长度为 1 的子序列 "a"。这贡献了 $1$ 个。
接在 b 后面：把当前字符 a 接在所有合法的、以 b 结尾的子序列后面，构成了新的以 a 结尾的子序列。这贡献了 $dp[b]$ 个。
接在 c 后面：把当前字符 a 接在所有合法的、以 c 结尾的子序列后面。这贡献了 $dp[c]$ 个。

把它们加起来，遇到字符 a 时，新的 $dp[a]$ 的状态转移方程就是：

$dp_{new}[a] = dp_{old}[a] + 1 + dp_{old}[b] + dp_{old}[c]$

而此时，因为当前字符是 a，它并没有产生新的以 b 或 c 结尾的子序列，所以有：

$dp_{new}[b] = dp_{old}[b]$ ， $dp_{new}[c] = dp_{old}[c]$

同理，如果遇到了字符 b 或 c，只需要把上面的公式替换一下字母即可。

Code#

1
// Problem: AT ABC456 D
2
// Contest: AtCoder - AtCoder Beginner Contest 456
3
// URL: https://atcoder.jp/contests/abc456/tasks/abc456_d
4
// Time: 2026-05-03 12:12:06
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20
const int mod = 998244353;
21

22
ll res;
23

24
int main()
25
{
26
    string s;
27
    cin >> s;
28

29
    ll dp[3] = {0, 0, 0};
30

31
    for (char c: s)
32
    {
33
        if (c == 'a')
34
            dp[0] = (dp[0] + dp[1] + dp[2] + 1) % mod;
35
        else if (c == 'b')
36
            dp[1] = (dp[0] + dp[1] + dp[2] + 1) % mod;
37
        else
38
            dp[2] = (dp[0] + dp[1] + dp[2] + 1) % mod;
39
    }
40

41
    ll res = (dp[0] + dp[1] + dp[2]) % mod;
42
    cout << res << endl;
43

44
    return 0;
45
}

E - Endless Holidays#

关键词：思维，图论，判断环

思路#

TIP
由于可以选择留在当前的城市，所以在建图时需要把每个点自身加进图里（自环）。

既然 Takahashi 每天都在移动或停留，我们可以用一个二元组 (u, d) 来表示他当前的状态：u 表示当前所在的城市，d 表示当前是星期几（为便于取模从 0 开始）。考虑这个状态图中的有效状态与转移过程：

有效状态：只有当 S[u][d] == 'o' 时，这个状态才是合法的（因为必须是节假日）。
状态转移：如果高桥今天在 (u, d)，明天他可以去任何一个相邻的城市 v（或者留在 u）。那么就会有一条从 (u, d) 指向 (v, (d + 1) % W) 的有向边。当然，前提是目标状态也必须是合法的。

假如他想要永远移动下去，就意味着必须要找一条无限长的路径，也就是图中存在环。

NOTE
怎么判断图里有没有环？我们可以用一种“反向拓扑排序”思想：不断剪除死胡同。

我们统计每个合法状态的出度，即它能走到多少个合法的明天状态。

如果某个状态的出度为 0，说明它是个死胡同，走到这里就结束了，我们把它从图里删掉。

删除它之后，可能会导致指向它的那些状态也变成死胡同（出度减 1）。如果它们出度也变成了 0，就继续删。

如果我们能把图里所有的有效状态都删光，说明处处都是死胡同，输出 No。

如果最后还有状态没被删掉，说明它们形成了环，输出 Yes。

Code#

1
// Problem: AT ABC456 E
2
// Contest: AtCoder - AtCoder Beginner Contest 456
3
// URL: https://atcoder.jp/contests/abc456/tasks/abc456_e
4
// Time: 2026-05-03 12:12:07
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 1e5 + 10;
20

21
void solve()
22
{
23
    int n, m, w;
24
    cin >> n >> m;
25

26
    vector<vector<int>> adj(n + 1);
27

28
    for (int i = 0; i < m; i++)
29
    {
30
        int u, v;
31
        cin >> u >> v;
32
        adj[u].push_back(v), adj[v].push_back(u);
33
    }
34

35
    for (int i = 1; i <= n; i++)
36
        adj[i].push_back(i);
37

38
    cin >> w;
39

40
    vector<string> s(n + 1);
41
    for (int i = 1; i <= n; i++)
42
        cin >> s[i];
43

44
    // out[u][d] 表示状态 (u, d) 有多少个合法的下一个状态
45
    vector<vector<int>> out(n + 1, vector<int>(w, 0));
46
    int valid_states = 0;
47

48
    for (int u = 1; u <= n; u++)
49
        for (int d = 0; d < w; d++)
50
            if (s[u][d] == 'o')
51
            {
52
                valid_states++;
53
                int nxt = (d + 1) % w;
54
                for (int v: adj[u])
55
                {
56
                    if (s[v][nxt] == 'o')
57
                        out[u][d]++;
58
                }
59
            }
60

61
    queue<pii> q;
62
    for (int u = 1; u <= n; u++)
63
        for (int d = 0; d < w; d++)
64
            if (s[u][d] == 'o' && out[u][d] == 0)
65
                q.push({u, d});
66

67
    int removed = 0;
68
    while (!q.empty())
69
    {
70
        auto [u, d] = q.front();
71
        q.pop();
72

73
        removed++;
74

75
        int prev_d = (d - 1 + w) % w;
76
        for (int v: adj[u])
77
        {
78
            if (s[v][prev_d] == 'o')
79
            {
80
                out[v][prev_d]--;
81
                if (out[v][prev_d] == 0)
82
                    q.push({v, prev_d});
83
            }
84
        }
85
    }
86

87
    if (removed < valid_states)
88
        cout << "Yes" << endl;
89
    else
90
        cout << "No" << endl;
91
}
92

93
int main()
94
{
95
    ios::sync_with_stdio(false);
96
    cin.tie(0);
97

98
    int T;
99
    cin >> T;
100

101
    while (T--)
102
        solve();
103

104
    return 0;
105
}