A

签到题

判断第二个字符和第三个字符是否相等即可。

void solve()
{
    std::string s;
    std::cin >> s;
    if (s[1] == s[2])
        std::cout << "Yes\n";
    else
        std::cout << "No\n";
}

B

平面几何

平面上两点中点公式：。

void solve()
{
    std::array<std::pair<int, int>, 3> as;
    for (auto& [a, b] : as)
    {
        std::cin >> a >> b;
    }

    if (as[0].first * 2 == as[1].first + as[2].first &&
        as[0].second * 2 == as[1].second + as[2].second)
        std::cout << 1 << '\n';
    if (as[1].first * 2 == as[0].first + as[2].first &&
        as[1].second * 2 == as[0].second + as[2].second)
        std::cout << 2 << '\n';
    if (as[2].first * 2 == as[1].first + as[0].first &&
        as[2].second * 2 == as[1].second + as[0].second)
        std::cout << 3 << '\n';
}

C

给出一个排列，改变某些数的值使得有半数以上的数相等，代价为两数之差的绝对值。

任意选取一段长度为 的数值区间（非原数组区间），将该数值区间内所有数均变为该区间的中位数。

例：

7
7 6 5 4 3 2 1

选取区间 ，将所有数变为 或者 。

得到

7 6 5 3 3 3 3

void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> as(n);
    for (auto& a : as)
    {
        std::cin >> a;
    }

    for (auto& a : as)
    {
        if (a <= (n + 1) / 2)
            a = ((n + 1) / 2 + 1) / 2;
    }
    for (auto a : as)
    {
        std::cout << a << ' ';
    }
    std::cout << '\n';
}

D

一颗无根树去掉任意一个节点后，其余相连各部分节点数量均为奇数，求符合条件的节点数量。

任意选取一点作为根，进行 DFS：

每个节点接受所有子树的节点个数，如果有任意子树节点数为偶数，该节点不合法；

用总节点数减去子树节点数之和以及当前节点，得到父节点所在区域节点数，若父节点存在且父节点所在区域节点数为偶数，该节点不合法；

否则该节点合法，累加答案。

最后将当前节点为根的树的节点数量返回给父节点。

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

    int ans{ 0 };
    auto dfs = [n, &tree, &ans](auto&& dfs, int u, int last) -> int
    {
        bool ok{ true };
        int sum{ 0 };
        for (int v : tree[u])
        {
            if (v == last)
                continue;
            int count{ dfs(dfs, v, u) };
            if (count % 2 == 0)
                ok = false;
            sum += count;
        }
        if (sum + 1 != n && (n - sum - 1) % 2 == 0)
            ok = false;
        if (ok)
            ++ans;
        return sum + 1;
    };
    dfs(dfs, 1, 0);
    std::cout << ans << '\n';
}

E

给出一个由 0 1 2 组成的字符串，每次选取任意两个 1，其中一个删除，其中一个变为 2，直到 1 的个数小于 无法操作。

按 1 的个数分奇偶进行讨论：

  • 偶数个 1：

    所有 1 都要被操作。

    将 1 删除一定不比将 1 变成 2 得到的后缀串字典序大，因此将前一半的 1 删除，后一半 1 变为 2。

  • 奇数个 1：

    会剩下一个 1 无法操作。判断哪一个 1 不操作，剩下的偶数个 1 按照偶数做法进行操作。

    当出现字串 12 时，不对该 1 进行操作，否则字典序一定变大。字串有多个时选取第一个。

    如果没有出现该字串，形如 1x 的字串只有 10 和 11。删除使字典序减小，改变使字典序增大。因此将前一半的 1 删除，后一半 1 变为 2，中间的一个不操作。

void solve()
{
    std::string s;
    std::cin >> s;

    int n{ int(s.length()) };
    s += "-";

    std::vector<int> indexs;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '1')
            indexs.push_back(i);
    }

    int l{ 0 }, r{ int(indexs.size()) - 1 };
    if (indexs.size() % 2 == 0)
    {
        while (l < r)
        {
            int ll{ indexs[l] };
            int rr{ indexs[r] };
            s[ll] = '-';
            s[rr] = '2';
            ++l;
            --r;
        }
    }
    else
    {
        int loc{ -1 };
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '1' && s[i + 1] == '2')
            {
                loc = i;
                break;
            }
        }
        if (loc == -1)
        {
            while (l < r)
            {
                int ll{ indexs[l] };
                int rr{ indexs[r] };
                s[ll] = '-';
                s[rr] = '2';
                ++l;
                --r;
            }
        }
        else
        {
            bool find{ false };
            while (l < r)
            {
                int ll{ indexs[l] };
                int rr{ indexs[r] };
                if (!find)
                {
                    if (ll == loc)
                    {
                        ++l;
                        find = true;
                        continue;
                    }
                }
                s[ll] = '-';
                s[rr] = '2';
                ++l;
                --r;
            }
        }
    }

    for (char c : s)
    {
        if (c != '-')
            std::cout << c;
    }
    std::cout << '\n';
}

F

相比于 E，本题可以进行任意次操作。

仅当可以减小字典序时才进行操作。

唯一可以减小字典序的序列：...1...10...0......1x...x。

找到一个 0 之前连续若干个 1，任意选取一个删除，然后从 0 的后缀中找到最末尾的一个 1 变为 2。

void solve()
{
    std::string s;
    std::cin >> s;

    int n{ int(s.length()) };
    s += "-";

    int r{ n - 1 };
    for (int i = 0; i < r; ++i)
    {
        if (s[i] != '0')
            continue;
        int l{ i - 1 };
        while (l >= 0 && s[l] == '1')
        {
            while (r > i && s[r] != '1')
            {
                --r;
            }
            if (s[r] == '1')
            {
                s[l] = '-';
                s[r] = '2';
            }
            else
            {
                break;
            }
            --l;
        }
    }

    for (char c : s)
    {
        if (c != '-')
            std::cout << c;
    }
    std::cout << '\n';
}

吐槽

我说 F 比 E 简单谁赞成？