Educational Codeforces Round 163 (Rated for Div. 2)

A

思路

只有两个相同的字符在一起，才算特殊字符，而三个相同的在一起，中间的不算特殊字符

故特殊字符是两两同时出现的。

当 \(n\) 为奇数时不存在。

当 \(n\) 为偶数时每次出现两个相同的且与上一次不同的字符即可

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    if (n & 1)
    {
        cout << "NO" << '\n';
        return;
    }

    cout << "YES" << '\n';
    for (int i = 0; i < n / 2; i++)
    {
        if (i & 1)
            cout << "AA";
        else
            cout << "BB";
    }
    cout << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B

思路

从后往前判断，因为将一个数拆分只会变小，如果已经比后面的小，拆分的操作不会对后面有影响

如果需要拆分需判断拆分后是否合理

一直记录当前的大小即可

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int now = a[n];
    for (int i = n - 1; i > 0; i--)
    {
        if (a[i] > now)
        {
            if (a[i] / 10 > a[i] % 10 || a[i] % 10 > now)
            {
                cout << "NO" << '\n';
                return;
            }
            else
                now = a[i] / 10;
        }
        else
            now = a[i];
    }
    cout << "YES" << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

C

思路

\(BFS\)

特殊的是每次移动可以看作移动两次，一次是朝四个方向的，一次是按指示方向的

移动两次后再进队

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<vector<char>> a(3, vector<char>(n + 1));
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    vector<vector<bool>> vis(3, vector<bool>(n + 1, false));
    vector<int> dx = {0, 0, 1, -1};
    vector<int> dy = {1, -1, 0, 0};
    queue<pair<int, int>> q;
    q.push({1, 1});
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();

        if (x == 2 && y == n)
        {
            cout << "YES" << '\n';
            return;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > 2 || ny < 1 || ny > n || vis[nx][ny])
                continue;
            vis[nx][ny] = true;

            if (nx == 2 && ny == n)
            {
                cout << "YES" << '\n';
                return;
            }

            if (a[nx][ny] == '<')
                ny--;
            else
                ny++;

            if (nx < 1 || nx > 2 || ny < 1 || ny > n || vis[nx][ny])
                continue;
            vis[nx][ny] = true;

            q.push({nx, ny});
        }
    }
    cout << "NO" << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D

思路

枚举每个长度，判断该长度能不能出现重复的字符串

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    string s;
    cin >> s;
    for (int len = s.size() / 2; len >= 1; len--)
    {
        int cnt = 0;
        for (int i = 0; i + len < s.size(); i++)
        {
            if (s[i] != s[i + len] && s[i] != '?' && s[i + len] != '?')
            {
                cnt = 0;
                continue;
            }
            cnt++;
            if (cnt == len)
            {
                cout << 2 * len << '\n';
                return;
            }
        }
    }
    cout << 0 << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E

思路

因为 \(a[i] - a[j] \ge 1\) 故一组的长度最大为 \(k\) ，而这组的两端的数需要差值为 \(1\) 且和别的数的差值尽可能小故选择中间的两个数。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = i;

    int cnt = 0;
    for (int i = 1; i + k - 1 <= n; i += k)
    {
        cnt++;
        reverse(a.begin() + i, a.begin() + i + k / 2);
        reverse(a.begin() + i + k / 2, a.begin() + i + k);
        for (int j = i; j < i + k; j++)
            b[j] = cnt;
    }
    if (n % k)
    {
        cnt++;
        if (n % k <= k / 2)
        {
            reverse(a.begin() + n - (n % k) + 1, a.end());
        }
        else
        {
            reverse(a.begin() + n - (n % k) + 1, a.begin() + n - (n % k) + 1 + k / 2);
            reverse(a.begin() + n - (n % k) + 1 + k / 2, a.end());
        }
        for (int i = n - (n % k) + 1; i <= n; i++)
            b[i] = cnt;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    cout << '\n';
    cout << cnt << '\n';
    for (int i = 1; i <= n; i++)
        cout << b[i] << ' ';
    cout << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F

思路

待补

Code

1
ACM > 题解 > Codeforces
#算法 #Codeforces
Educational Codeforces Round 163 (Rated for Div. 2)
http://xiaowhang.github.io/archives/1513395789/
作者
Xiaowhang
发布于
2024年3月16日
许可协议