链接：https://atcoder.jp/contests/abc428

A – Grandma’s Footsteps

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int s, a, b, x;
    cin >> s >> a >> b >> x;

    ll ans = 0;
    while (x)
    {
        int t = min(x, a);
        ans += t * s;
        x -= t;

        if (x)
        {
            x = max(0, x - b);
        }
    }

    cout << ans << endl;
}

B – Most Frequent Substrings

算法：

    模拟，\(stl\)。

思路：

    无。

关键代码：

void miyan()
{
    int n, k;
    string s;
    cin >> n >> k >> s;

    map<string, int> m;
    for (int i = 0; i < n - k + 1; ++i)
        ++m[s.substr(i, k)];

    int ans = 0;
    for (auto [x, y] : m)
        ans = max(ans, y);

    cout << ans << endl;
    for (auto [x, y] : m)
        if (ans == y)
            cout << x << ' ';

    cout << endl;
}

C – Brackets Stack Query

算法：

    前缀和，括号序列。

思路：

    括号序列性质：将 '(' 转换为 \(1\)，')' 转换为 \(-1\)，那么一个好的括号序列，其前缀和时时刻刻都不小于 \(0\)，且最终前缀和等于 \(0\)。

关键代码：

void miyan()
{
    int Q;
    cin >> Q;

    vector<int> res(Q + 1, 0);
    int idx = 1;
    int cnt = 0;
    while (Q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            char c;
            cin >> c;

            if (c == '(')
            {
                res[idx] = res[idx - 1] + 1;
                ++idx;
            }
            else
            {
                res[idx] = res[idx - 1] - 1;
                ++idx;
            }

            if (res[idx - 1] < 0)
                ++cnt;
        }
        else
        {
            if (res[idx - 1] < 0)
                --cnt;
            --idx;
        }

        if (res[idx - 1] == 0 && cnt == 0)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

D – 183184

算法：

    模拟。

思路：

    无。

关键代码：

ll pow10[20];
void init()
{
    pow10[0] = 1;
    for (int i = 1; i < 20; ++i)
        pow10[i] = pow10[i - 1] * 10;
}

void miyan()
{
    ll c, d;
    cin >> c >> d;

    int l = to_string(c + 1).size();
    int r = to_string(c + d).size();
    ll ans = 0;
    for (int i = l; i <= r; ++i)
    {
        ll L = c * (pow10[i] + 1ll) + max(1ll, pow10[i - 1] - c);
        ll R = c * (pow10[i] + 1ll) + min(d, pow10[i] - 1ll - c);

        L = ceill(sqrtl(L));
        R = sqrtl(R);

        ans += max(0ll, R - L + 1ll);
    }

    cout << ans << endl;
}

E – Farthest Vertex

算法：

    模拟。

思路：

    树的直径性质：对于任意结点 \(u\)，距离 \(u\) 最远的结点 \(v\) 一定是任意一条树的直径的一个端点。

    找出左右端点编号最大的直径，定义左右端点为 \(x,y\)。

    那么距离 \(u\) 最远且编号最大的节点就是：

• \(distx[u] > disty[u]\): 输出 \(x\)；
• \(distx[u] > disty[u]\): 输出 \(y\)；
• \(distx[u] == disty[u]\): 输出 \(max(x, y)\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto get = [&](int start) -> vector<int>
    {
        vector<int> dist(n + 1, 0);
        auto dfs = [&](auto &&self, int u, int f) -> void
        {
            dist[u] = dist[f] + 1;
            for (auto &v : g[u])
            {
                if (v == f)
                    continue;

                self(self, v, u);
            }
        };

        dfs(dfs, start, 0);
        return dist;
    };

    int x = 1;
    auto dist = get(x);
    for (int i = 1; i <= n; ++i)
    {
        if ((dist[i] > dist[x]) || (dist[i] == dist[x] && i > x))
            x = i;
    }

    auto dist_x = get(x);

    int y = x;
    for (int i = 1; i <= n; ++i)
    {
        if ((dist_x[i] > dist_x[y]) || (dist_x[i] == dist_x[y] && i > y))
            y = i;
    }

    auto dist_y = get(y);

    for (int i = 1; i <= n; ++i)
    {
        if (dist_x[i] > dist_y[i])
            cout << x << endl;
        else if (dist_x[i] < dist_y[i])
            cout << y << endl;
        else
            cout << max(x, y) << endl;
    }
}

F – Pyramid Alignment

    还没补。