链接：https://codeforces.com/contest/2147

A. Shortest Increasing Path

算法：

    找规律。

思路：

    答案只有 \(-1\) \(2\) \(3\) 三种情况。

• \(x < y\)：两步即可。
• \(x == y\)：不成立。
• \(x > y\) 时
  • \(y == 1\)： 不成立。
  • \(x >= y + 2\)：可以选出来，需要三步。

关键代码：

void miyan()
{
    ll x, y;
    cin >> x >> y;

    if (x < y)
        cout << 2 << endl;
    else if (x == y)
        cout << -1 << endl;
    else
    {
        if (y == 1)
            cout << -1 << endl;
        else if (x >= y + 2)
            cout << 3 << endl;
        else
            cout << -1 << endl;
    }
}

B. Multiple Construction

算法：

    构造。

思路：

    手玩几组样例。

关键代码：

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

    for (int i = n; i; --i)
        cout << i << ' ';
    cout << n << ' ';
    for (int i = 1; i < n; ++i)
        cout << i << ' ';
    cout << endl;
}

C. Rabbits

算法：

    贪心，模拟，找规律。

思路：

    可以发现以下几条规律：

• 相邻的两个 \(1\) 可以被完全分割成两段并且完全不受对方影响。
• 被规则 \(1\) 分割后的字符串中存在相邻 \(0\) 的子串必然成立，此时也可以将相邻的 \(0\) 进行分割成两段。
• 如果某一段的第一个字符为 \(0\) 并且为开头或者最后一个字符为 \(0\) 并且为结尾，那么这一段必然成立。

    最后对于由规则 \(1\) \(2\) 分割后的段必然为 \(0\) \(1\) 交替段，可以发现只有当左右端点都为 \(1\) 的段才可能不成立。

    因为如果有一个端点为 \(0\) ，那么他可能为：

• 起点或者终点，由规则 \(3\) 可知必然成立。
• 被规则 \(2\) 分割而来，也必然成立。

关键代码：

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

    bool flag = (s[0] == '0');
    ll cnt = (s[0] == '0');
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '0')
            ++cnt;

        if (s[i] == s[i - 1])
        {
            if (s[i] - '0')
            {
                if (!flag && cnt % 2 == 1)
                {
                    cout << "NO" << endl;
                    return;
                }

                flag = 0;
                cnt = 0;
            }
            else
                flag = 1;
        }
    }

    if (!flag && cnt % 2 == 1 && s[n - 1] - '0')
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

D. Game on Array

算法：

    博弈论，贪心。

思路：

    这题的主要难点在于想到对奇偶的不同决策。

    对于偶数，每个人的最优策略必然都是每个人都拿走一半，既一个偶数，先手先取了，后手也可以跟着取，所有偶数会均分给双方。

    对于奇数，一个人取完之后，其就变为了偶数，后续的最优策略与偶数情况相同。

    所有双方的最优策略就为抢出现次数最多的奇数。

    使用一个桶存储每个奇数出现的次数，使用大根堆模拟双方选择的操作即可。

关键代码：

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

    ll ans1 = 0, ans2 = 0;
    map<int, int> m;
    while (n--)
    {
        int x;
        cin >> x;
        if (x & 1)
            ++m[x];
        ans1 += x / 2, ans2 += x / 2;
    }

    priority_queue<int> q;
    for (auto [_, x] : m)
        q.push(x);

    ll now = 1;
    while (q.size())
    {
        if (now)
            ans1 += q.top(), q.pop();
        else
            ans2 += q.top(), q.pop();

        now = !now;
    }

    cout << ans1 << ' ' << ans2 << endl;
}

E. Maximum OR Popcount

    还没补。