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

A. El fucho

算法：

    模拟。

思路：

    打表。

关键代码：

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

    cout << (n - 1) * 2 << endl;
}

B. Abraham’s Great Escape

算法：

    模拟。

思路：

    先考虑无解的情况：当 \(k = n * n – 1\) 时，必然不存在答案。

    否则就可以构造一个 \(RL\)，使得在这里无限循环，如果剩余 \(n * n – k – 2\) 个位置全部指向 \(RL\) 即可。

关键代码：

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

    k = n * n - k;

    if (k == 1)
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;

    if (!k)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
                cout << 'U';

            cout << endl;
        }

        return;
    }

    k -= 2;
    cout << "RL";
    for (int i = 0; i < n; ++i)
    {
        int start = 0;
        if (!i)
            start = 2;
        for (int j = start; j < n; ++j)
        {
            if (k)
            {
                if (!i)
                    cout << 'L';
                else if (!j)
                    cout << 'U';
                else
                    cout << 'L';

                --k;
            }
            else
                cout << 'R';
        }

        cout << endl;
    }
}

C. The Ancient Wizards’ Capes

算法：

    贪心，前缀和。

思路：

    \(i + 1\) 可以直接继承 \(i\) 的 \([1, i – 1]\) 和 \([i + 2, n]\) 的放置状态。

    设 \(state(x)\) 为 \(x\) 位置的状态，设 \(state[1, i – 1] + state[1 + 2, n] = x\)。

    \(i\) 和 \(i + 1\) 有以下几种情况：

• 当双方互相看不见时答案都为 \(x + 1\)
• 当双方互相可以看见时答案都为 \(x + 2\)
• 当 \(i\) 可以看见 \(i + 1\)，\(i + 1\) 看不见 \(i\)，\(ans[i] = x + 2\)，\(ans[i + 1] = x + 1\)
• 当 \(i\) 看不见 \(i + 1\)，\(i + 1\) 可以看见 \(i\)，\(ans[i] = x + 1\)，\(ans[i + 1] = x + 2\)

    综上 \(abs(ans[i] – ans[i + 1]) <= 1\)，所以答案为 \(0\) 的情况为 \(abs(ans[i] – ans[i + 1]) > 1\)

    由于 \(i + 1\) 的状态可直接由 \(i\) 获得，直接枚举 \(1\) 处于两种状态时，后续元素的状态，然后判断最后得到的数量是否与答案相等。

关键代码：

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

    for (int i = 2; i <= n; ++i)
    {
        if (abs(a[i] - a[i - 1]) > 1)
        {
            cout << 0 << endl;
            return;
        }
    }

    vector<ll> b(n + 1, 0);
    auto check = [&]() -> int
    {
        for (int i = 2; i <= n; ++i)
        {
            if (a[i] == a[i - 1])
                b[i] = !b[i - 1];
            else
            {
                if (a[i] > a[i - 1])
                {
                    if (b[i - 1])
                        return 0;

                    b[i] = 0;
                }
                else
                {
                    if (!b[i - 1])
                        return 0;

                    b[i] = 1;
                }
            }
        }

        vector<ll> pre(n + 1, 0), suf(n + 1, 0);
        for (int i = 2; i <= n; ++i)
            pre[i] = pre[i - 1] + !b[i - 1];
        for (int i = n - 1; i >= 1; --i)
            suf[i] = suf[i + 1] + b[i + 1];

        vector<ll> c(n + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
            c[i] = pre[i] + suf[i] + 1;
            if (c[i] != a[i])
                return 0;
        }

        return 1;
    };

    ll ans = 0;
    b[1] = 0;
    ans += check();

    fill(b.begin() + 2, b.end(), 0);

    b[1] = 1;
    ans += check();
    cout << ans << endl;
}

D. Batteries

算法：

    交互题，贪心。

思路：

    将 \(n\) 节电池组成一个首位相连的环。

    可以发现在有 \(a\) 节电池有电的情况下，两节都有电的电池最远相距 \(floor(n / a)\)。

    直接暴力枚举两节有电的电池相聚的距离即可。

关键代码：

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

    auto query = [&](int u, int v) -> bool
    {
        cout << u << ' ' << v << endl;

        ll ans = 0;
        cin >> ans;

        return ans;
    };

    for (int w = 1; w <= n / 2; ++w)
    {
        for (int i = 1; i <= n; ++i)
        {
            int j = i + w;

            if (j > n)
                j -= n;

            if (query(i, j))
                return;
        }
    }
}

E. Mimo & Yuyu

    还没补。