NOTE
比赛链接：Educational Codeforces Round 189 (Rated for Div.2)

A - A Number Between Two Others#

关键词：暴力，签到

Code#

1
// Problem: CF 2225 A
2
// Contest: Codeforces - Educational Codeforces Round 189 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2225/problem/A
4
// Time: 2026-05-16 14:36:37
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
    ll x, y;
29
    cin >> x >> y;
30

31
    for (ll i = x; i <= y; i += x)
32
    {
33
        if (i % x == 0 && y % i != 0)
34
        {
35
            cout << "YES" << endl;
36
            return;
37
        }
38
    }
39

40
    cout << "NO" << endl;
41
}
42

43
int main()
44
{
45
    fastio();
46

47
    int T = 1;
48
    cin >> T;
49

50
    while (T--)
51
        solve();
52

53
    return 0;
54
}

B - Alternating String#

关键词：思维

思路#

题目要求最终的字符串交替，也就是任意的两个字符都不能相同。假如存在 $s_i = s_{i + 1}$ ，我们就说这里存在一个冲突。

题目要求选定一个子串，必须将其位置反转，并且可以选择性地将字符反转。

我们发现，进行这样的操作，不会改变子串内部和外部的冲突数量情况，只会改变边界处。

这就意味着一次操作最多可以消除两个冲突。

Code#

1
// Problem: CF 2225 B
2
// Contest: Codeforces - Educational Codeforces Round 189 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2225/problem/B
4
// Time: 2026-05-16 15:15:59
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

31
    int res = 0;
32
    for (int i = 1; i < s.size(); i++)
33
    {
34
        if (s[i] == s[i - 1])
35
            res++;
36
    }
37
    // cout << res << endl;
38

39
    cout << (res <= 2 ? "YES" : "NO") << endl;
40
}
41

42
int main()
43
{
44
    fastio();
45

46
    int T = 1;
47
    cin >> T;
48

49
    while (T--)
50
        solve();
51

52
    return 0;
53
}

C - Red-Black Pairs#

关键词：DP

思路#

这是一个多米诺骨牌覆盖模型，具体结论如下：

在 $2 \times n$ 的网格中，任何一种无缝隙的骨牌铺法，都可以被拆解为以下两种基础单元的堆叠：

竖放（ $2 \times 1$ 单元）：占用 $1$ 列，上下两个格子配成一对。
横放（ $2 \times 2$ 单元）：占用 $2$ 列，上下两行各用两个 $1 \times 2$ 的横向骨牌（因为如果你只放一个横骨牌，剩下的缺口必然填不满，只能上下都横放，凑成一个 $2 \times 2$ 的方块）。

设 $dp[i]$ 表示完美处理完前 $i$ 列所需的最小修改次数。

当我们在第 $i$ 列时，只面临两种决策：

决策 A：第 $i$ 列单独竖放

我们要把第一行的 $a_i$ 和第二行的 $b_i$ 强行配成一对。
- 如果它们颜色本来就相同，代价是 $0$ ；如果不同，我们得改掉其中一个，代价是 $1$ 。
- 这种情况下的最小总代价是：dp[i-1] + (a[i] != b[i])。
决策 B：第 $i-1$ 列和第 $i$ 列横放

我们要把 $a_{i-1}$ 和 $a_i$ 配对，同时把 $b_{i-1}$ 和 $b_i$ 配对。
- 对于第一行，如果 $a_{i-1} \neq a_i$ ，代价 $+1$ 。
- 对于第二行，如果 $b_{i-1} \neq b_i$ ，代价 $+1$ 。
- 这种情况下的最小总代价是：dp[i-2] + (a[i-1] != a[i]) + (b[i-1] != b[i])。

两种决策取最小值即可。注意当 $i = 1$ 时会引发数组越界。

Code#

1
// Problem: CF 2225 C
2
// Contest: Codeforces - Educational Codeforces Round 189 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2225/problem/C
4
// Time: 2026-05-16 15:39:42
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
    string a, b;
32
    cin >> a >> b;
33

34
    a = " " + a, b = " " + b;
35

36
    vector<int> dp(n + 1, inf);
37
    dp[0] = 0;
38

39
    dp[1] = dp[0] + (a[1] != b[1]);
40

41
    for (int i = 2; i <= n; i++)
42
        dp[i] = min(dp[i - 1] + (a[i] != b[i]), dp[i - 2] + (a[i - 1] != a[i]) + (b[i - 1] != b[i]));
43

44
    cout << dp[n] << endl;
45
}
46

47
int main()
48
{
49
    fastio();
50

51
    int T = 1;
52
    cin >> T;
53

54
    while (T--)
55
        solve();
56

57
    return 0;
58
}

D - Exceptional Segments#

关键词：异或运算

思路#

NOTE
详见笔记本中的数学章节，写了前缀异或和的性质。

根据异或运算的性质，任意一段区间 $[l, r]$ 的连续异或和可以表示为：

$\bigoplus_{i=l}^r i = P(r) \oplus P(l-1)$

题目要求这段区间的异或和为 $0$ ，这就意味着：

$P(r) \oplus P(l-1) = 0 \implies P(r) = P(l-1)$

题目等价于让我们在 $L \in [0, x-1]$ 和 $r \in [x, n]$ 这两个独立的区间内，寻找有多少对 $(L, r)$ 能够满足 $P(L) = P(r)$ 。

显然 $P(L) = P(r)$ 当且仅当它们都取到了常数值，也就是 $0$ 或 $1$ 。

目标值同为 $0$ ：

要让 $P(L) = 0$ ，条件是 $L \equiv 3 \pmod 4$ 或 $L = 0$ 。
要让 $P(r) = 0$ ，条件是 $r \equiv 3 \pmod 4$ 。

目标值同为 $1$ ：

要让 $P(L) = 1$ ，条件是 $L \equiv 1 \pmod 4$ 。
要让 $P(r) = 1$ ，条件是 $r \equiv 1 \pmod 4$ 。

Code#

1
// Problem: CF 2225 D
2
// Contest: Codeforces - Educational Codeforces Round 189 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2225/problem/D
4
// Time: 2026-05-16 17:19:37
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
const ll mod = 998244353;
26

27
void solve()
28
{
29
    ll n, x;
30
    cin >> n >> x;
31

32
    ll l0 = 1 + x / 4;
33
    ll l1 = (x + 2) / 4;
34

35
    ll r0 = (n + 1) / 4 - x / 4;
36
    ll r1 = (n + 3) / 4 - (x + 2) / 4;
37

38
    ll res = (l0 % mod) * (r0 % mod) % mod;
39
    res = (res + (l1 % mod) * (r1 % mod) % mod) % mod;
40

41
    cout << res << endl;
42
}
43

44
int main()
45
{
46
    fastio();
47

48
    int T = 1;
49
    cin >> T;
50

51
    while (T--)
52
        solve();
53

54
    return 0;
55
}