AtCoder Beginner Contest 329

A

思路

循环输出，用空格分隔字符串 \(S\) 中的每个字符。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << s[i];
    }

    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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    sort(all(v), greater<int>());

    for (int i = 0; i < n; i++)
    {
        if (v[i] != v[0])
        {
            cout << v[i];
            return 0;
        }
    }

    return 0;
}

C

思路

记录每个字母连续出现的最大长度，最后累加即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    int n;
    string s;
    cin >> n >> s;

    int cnt = 0;
    char now = s[0];
    vector<int> v(30);
    for (int i = 0; i < n; i++)
    {
        if (s[i] == now)
            cnt++;
        else
        {
            v[now - 'a'] = max(v[now - 'a'], cnt);
            now = s[i];
            cnt = 1;
        }
    }
    v[now - 'a'] = max(v[now - 'a'], cnt);

    int ans = 0;
    for (int i = 0; i < 26; i++)
        if (v[i])
            ans += v[i];
    cout << ans;

    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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1);

    int maxn = 0, max_index = 0;
    while (m--)
    {
        int x;
        cin >> x;

        v[x]++;
        if (v[x] > maxn || (v[x] == maxn && x < max_index))
        {
            maxn = v[x];
            max_index = x;
        }
        cout << max_index << endl;
    }

    return 0;
}

E

思路

DFS模拟覆盖的过程，找到 \(S\) 中完整的字符串 \(T\) ，将其用 \(\%\) 覆盖，说明此处可以是任意的字符，然后向左向右搜索是否还能凑出字符串 \(T\) 。操作完成后字符串 \(S\) 应该会被还原成全是 \(\%\) 的字符串，如果不是则说明无法匹配。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int n, m;
string s, t;

void dfs(int l, int r)
{
    for (int i = l; i < r; i++)
        s[i] = '%';

    for (int k = 1; k < m; k++)
    {
        if (l - k < 0)
            break;

        bool flag = true;
        int cnt = 0;
        for (int i = 0; i < m; i++)
        {
            if (s[l - k + i] == '%')
                cnt++;
            if (s[l - k + i] != t[i] && s[l - k + i] != '%' || cnt == m)
            {
                flag = false;
                break;
            }
        }

        if (flag)
            dfs(l - k, l - k + m);
    }

    for (int k = 1; k < m; k++)
    {
        if (r + k > n)
            break;

        bool flag = true;
        int cnt = 0;
        for (int i = 0; i < m; i++)
        {
            if (s[l + k + i] == '%')
                cnt++;
            if ((s[l + k + i] != t[i] && s[l + k + i] != '%') || cnt == m)
            {
                flag = false;
                break;
            }
        }
        if (flag == true)
            dfs(l + k, l + k + m);
    }
}

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

    cin >> n >> m >> s >> t;

    while (s.find(t) != string::npos)
    {
        int p = s.find(t);
        dfs(p, p + m);
    }

    for (int i = 0; i < n; i++)
    {
        if (s[i] != '%')
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";

    return 0;
}

F

思路

通过 std::set 进行去重。

当我们要合并两个箱子时, 我们要选择把球数少的箱子倒进球数多的箱子。

但是题目已经限定倒入的方向为 \(a\) 倒入 \(b\) 中，我们可以通过一个 swap() 来交换两个箱子，通过 set[i] 表示 \(i\) 号箱子的具体情况

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;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    int n, m;
    cin >> n >> m;

    vector<set<int>> st(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        st[i].insert(x);
    }

    while (m--)
    {
        int a, b;
        cin >> a >> b;

        if (st[a].size() > st[b].size())
            swap(st[a], st[b]);

        st[b].insert(all(st[a]));
        st[a].clear();

        cout << st[b].size() << endl;
    }

    return 0;
}
ACM > 题解 > AtCoder
#算法 #AtCoder
AtCoder Beginner Contest 329
http://xiaowhang.github.io/archives/280002889/
作者
Xiaowhang
发布于
2023年11月19日
许可协议