AtCoder Beginner Contest 333

• AtCoder Beginner Contest 333

A

思路

根据题意模拟

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

#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;

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        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

#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;

void solve()
{
    char a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = min(5 - abs(a - b), abs(a - b));
    int y = min(5 - abs(c - d), abs(c - d));

    cout << (x == y ? "Yes" : "No");
}

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

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

    return 0;
}

C

思路

暴搜所有结果，这里使用 set 去重。

也可以使用数组存储后遍历求解

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

#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;

ll a[] = {1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111};
set<ll> ans;

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 12; j++)
        {
            for (int k = 0; k < 12; k++)
            {
                ans.insert(a[i] + a[j] + a[k]);
            }
        }
    }

    int cnt = 0;
    for (auto it : ans)
    {
        cnt++;
        if (cnt == n)
        {
            cout << it;
            break;
        }
    }
}

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

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

    return 0;
}

D

思路

建树，遍历节点 \(1\) 所能访问的所有结点，如果 \(1\) 的子树数量为 \(1\) 则直接删除节点 \(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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#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 = 3e5 + 10;
const int M = 1e5 + 10;

vector<int> g[N];
int n, maxn, cnt;
vector<bool> vis(N);

void bfs(int x)
{
    cnt = 0;
    queue<int> q;
    q.push(x);

    while (!q.empty())
    {
        cnt++;
        int u = q.front();
        q.pop();
        for (auto v : g[u])
        {
            if (!vis[v])
            {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    if (g[1].size() == 1)
        cout << 1;
    else
    {
        vis[1] = true;
        for (auto u : g[1])
        {
            vis[u] = true;
            bfs(u);
            maxn = max(maxn, cnt);
        }
        cout << n - maxn;
    }
}

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

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

    return 0;
}

E

思路

从后面开始遍历，用 map 存出现的怪物的类型以及个数，同时增加携带的药水量也是需要的药水量，前面如果出现这个类型的药水，就减少身上的药水，说明这个类型的药水是这个时候捡起来的。遍历结束后，如果需要的药水量大于 \(0\) 说明无法打败所有的怪物，输出 \(-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
58
59
60
61
62
63
64
65
66

#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;

struct node
{
    int t, x;
};

void solve()
{
    int n;
    cin >> n;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].t >> v[i].x;

    map<int, int> mp;
    vector<int> ansv;
    int cnt = 0, ans = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (v[i].t == 2)
        {
            mp[v[i].x]++;
            cnt++;
            ans = max(ans, cnt);
        }
        else if (v[i].t == 1 && mp[v[i].x])
        {
            mp[v[i].x]--;
            cnt--;
            ansv.push_back(1);
        }
        else if (v[i].t == 1)
            ansv.push_back(0);
    }
    reverse(all(ansv));

    if (cnt)
        cout << -1;
    else
    {
        cout << ans << endl;
        for (auto it : ansv)
            cout << it << ' ';
    }
}

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

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

    return 0;
}

F

思路

待补

Code

1