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

A – Thermometer

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    double x;
    cin >> x;
    if (x < 37.5)
        cout << 3 << endl;
    else if (x < 38)
        cout << 2 << endl;
    else
        cout << 1 << endl;
}

B – Ticket Gate Log

算法：

    贪心。

思路：

    无。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    ll ans = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        if ((i + ans) & 1)
        {
            if (s[i] == 'i')
                ++ans;
        }
        else
        {
            if (s[i] == 'o')
                ++ans;
        }
    }

    if ((s.size() + ans) % 2 == 1)
        ++ans;

    cout << ans << endl;
}

C – Variety Split Easy

算法：

    贪心，\(stl\)。

思路：

    无。

关键代码：

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

    ll ans = 0;
    map<int, int> m, mm;
    for (int i = 0; i < n; ++i)
        ++mm[a[i]];

    for (int i = 0; i < n; ++i)
    {
        --mm[a[i]];
        if (!mm[a[i]])
            mm.erase(a[i]);

        ++m[a[i]];

        ans = max(ans, ll(m.size() + mm.size()));
    }

    cout << ans << endl;
}

D – Cubes

算法：

    数学。

思路：

    原式可转换为\(x ^ 3 – y ^ 3 = (x – y) * (x ^ 2 + y ^ 2 + xy) = n\)

    定义 \(a = (x – y)\)⁽¹⁾，\(b = (x ^ 2 + y ^ 2 + xy)\)⁽²⁾，此时 \(n = ab\)

    那么 \(a ^ 2 = x ^ 2 + y ^ 2 – 2xy\)

    显见 \(a ^ 2 < b\)，那么 \(a ^ 3 < n\)

    枚举 \(a\)，由 \(n,a\) 可得 \(b = n / a\)

    联立 \((1),(2)\) 得 \(3y ^ 3 + 3ay + a^2 – b = 0\)

    通过求根公式求得根，判断根是否为整数即可。

关键代码：

void miyan()
{
    ll n;
    cin >> n;

    for (__int128_t a = 1; a * a * a <= n; ++a)
    {
        if (n % a != 0)
            continue;

        __int128_t b = n / a;
        __int128_t d = 12ll * b - 3ll * a * a;

        if (d < 0)
            continue;

        __int128_t sd = sqrtl(d);

        if (sd * sd != d)
            continue;

        __int128_t y1 = (sd - (3ll * a)) / 6ll;
        __int128_t y2 = (-sd - (3ll * a)) / 6ll;
        __int128_t x1 = a + y1;
        __int128_t x2 = a + y2;
        if (x1 > 0 && y1 > 0 && x1 * x1 * x1 - y1 * y1 * y1 == n)
        {
            cout << (ll)x1 << ' ' << (ll)y1 << endl;
            return;
        }
        if (x2 > 0 && y2 > 0 && x2 * x2 * x2 - y2 * y2 * y2 == n)
        {
            cout << (ll)x2 << ' ' << (ll)y2 << endl;
            return;
        }
    }

    cout << -1 << endl;
}

E – Path Decomposition of a Tree

算法：

    贪心，树。

思路：

    将一颗树分解为 \(n\) 条长度为 \(k\) 的链。

    \(dfs\) 统计每个子树的节点数。

    对于当前 \(u\)：

• 如果其节点数 \(< k\)，其接着寻找的条件需要满足 \(u\) 的子节点数量 \(< 2\)，否则直接输出 \(No\)。*
• 如果其节点数 \(= k\)，且子节点数量 \(< 3\)，可直接划分为一个链，直接删除，既将 \(siz[u] =  0\)，如果子节点数量 \(>= 3\)，就不是一个链，直接输出 \(No\)。
• 如果其节点数 \(> k\)，在保证其子节点都划分完毕的前提下，其必然不成立，直接输出 \(No\)。
• 如果 \(u = 1\) 并且节点数 \(< k\)，直接输出 \(No\)。

    * 证明：

    假设其节点数 \(>= 2\)，由于当前节点数少于 \(k\)，还需接着向上寻找节点以满足 \(k\) 个节点，此时节点数量 \(>= 3\)，不构成链，所以需要满足节点数量 \(< 2\)。

关键代码：

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

    auto No = [&]() -> void
    {
        cout << "No" << endl;
        exit(0);
    };

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

            self(self, v, u);

            if (siz[v])
            {
                ++ch;
                siz[u] += siz[v];
            }
        }

        if (siz[u] < k)
        {
            if (u == 1 || ch > 1)
            {
                No();
            }
        }
        else if (siz[u] == k)
        {
            if (ch > 2)
            {
                No();
            }
            siz[u] = 0;
        }
        else
            No();
    };

    dfs(dfs, 1, 0);

    cout << "Yes" << endl;
}

F – Variety Split Hard

    还没补。