Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）

A - Three Threes

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cout << n;
    }
}

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

    return 0;
}

B - Pentagon

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second

void solve()
{
    string a, b;
    cin >> a >> b;
    int x = 0, y = 0;
    x = abs(a[0] - a[1]);
    y = abs(b[0] - b[1]);
    if (x > 2)
    {
        x = 5 - x;
    }
    if (y > 2)
    {
        y = 5 - y;
    }
    if (x != y)
    {
        puts("No");
    }
    else
    {
        puts("Yes");
    }
}

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

    return 0;
}

C - Repunit Trio

解题思路:

枚举范围内的三数之和，然后排序。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second

void solve()
{
    ll n;
    cin >> n;
    vector<ll> v;
    ll t = 0;
    for (int i = 0; i <= 18; i++)
    {
        t = t * 10 + 1;
        v.push_back(t);
        // cout << t << endl;
    }
    vector<ll> a;
    for (int i = 0; i < 18; i++)
    {
        for (int j = i; j < 18; j++)
        {
            for (int k = j; k < 18; k++)
            {
                a.push_back(v[i] + v[j] + v[k]);
            }
        }
    }
    // cout << a.size() << endl;
    sort(a.begin(), a.end());
    cout << a[n - 1] << endl;
}

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

    return 0;
}

D - Erase Leaves

解题思路:

计算出结点\(1\)的最大子树中的结点个数\(maxs\)，答案为\(n - maxs\)。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if (adj[1].size() == 1)
    {
        cout << 1 << endl;
        return;
    }
    vector<int> dist(n + 1);
    dist[1] = 0;
    int ans = 0;
    auto dfs = [&](auto self, int u, int fa) -> int
    {
        dist[u] = 1;
        for (auto v : adj[u])
        {
            if (v != fa)
            {
                int res = self(self, v, u);
                if (u == 1)
                {
                    ans = max(ans, res);
                }
                dist[u] += res;
            }
        }
        return dist[u];
    };
    dfs(dfs, 1, -1);
    cout << n - ans << endl;
}

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

    return 0;
}

E - Takahashi Quest

解题思路:

先捡起路上所有的药水，如果过程中不会被击败，那么就有解。

从后往前枚举，记录怪兽，路途中遇到药水时，如果有怪兽要击败就捡起，否则不减，记录路途拥有最多药水数。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    vector<int> med(n + 1), mon(n + 1);
    bool f = true;
    vector<pii> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        v[i] = {a, b};
        if (a == 1)
        {
            med[b]++;
        }
        else
        {
            mon[b]++;
        }
        if (mon[b] > med[b])
        {
            f = false;
        }
    }
    if (!f)
    {
        puts("-1");
        return;
    }
    vector<int> ned(n + 1), ans(n + 1, 0);

    for (int i = n; i; i--)
    {
        if (v[i].fi == 1)
        {
            if (ned[v[i].se] > 0)
            {
                ans[i] = 1;
                ned[v[i].se]--;
            }
        }
        else
        {
            ned[v[i].se]++;
        }
    }
    int cur = 0;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i].fi == 1)
        {
            if (ans[i])
            {
                cur++;
                res = max(res, cur);
            }
        }
        else
        {
            cur--;
        }
    }
    cout << res << endl;
    for (int i = 1; i <= n; i++)
    {
        if (v[i].fi == 1)
        {
            cout << ans[i] << ' ';
        }
    }
    cout << endl;
}

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

    return 0;
}