[CF1495B] Let's Go Hiking - 博弈

Description

两个人（下简称 Q 和 D ）取爬山，一个长度为 \(n\) 的排列，其中 \(p_i\) 表示 \(i\) 处的高度。

Q 会先选择一个位置 \(x_0\) ，并把这个位置告诉 D 。在此之后，D 会选择一个位置 \(y_0\) 。

接下来两个人开始轮流爬山， Q 先行动。

• 如果是 Q 行动，假设此时她在 \(x\) 处，D 在 \(y\) 处，则她下一步移动到的位置 \(x'\) 必须满足 \(1\le x'\le n\ ,\ |x'-x|=1\ ,\ x'\neq y\ ,\ p_{x'}<p_x\) 。
• 如果是 D 行动，假设此时他在 \(y\) 处，Q 在 \(x\) 处，则他下一步移动到的位置 \(y'\) 必须满足 \(1\le y'\le n\ ,\ |y'-y|=1\ ,\ y'\neq x\ ,\ p_{y'}>p_y\) 。

当某一个人不能行动时，对方获胜。求出 Q 能选出多少个初始位置 \(x_0\) ，保证她必胜。

Solution

x 必须选在坡顶，否则没救
必须是双边的坡顶
后手可以选这个坡上，与先手距离为奇数的位置，而偶数的位置是不可选的
此时先手可以逃向另一边，如果另一边的距离小于等于这个位置，那么先手被堵死了
所以，如果两边的距离都是奇数，先手死了
如果两边距离一个奇数一个偶数，偶数比奇数小，还是先手死；偶数比奇数大，一样是先手死
如果两边距离都是偶数，那么先手一定能逃脱，所以这时候就不能这么玩
后手必须要去找控制区间之外的部分，找最大上升
如果这个最大上升大于等于那个偶数，那么后手胜利

因此，A 选择的，必然是

• 两边距离相等且为偶数的（否则后手可以从长的那边堵死）
• 距离最长且不能有第三次相等长度的出现的（否则后手可以模仿他对称着走）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, a[N], lu[N], ld[N], ru[N], rd[N], mlu[N], mru[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 2; i <= n; i++)
        if (a[i - 1] < a[i])
            ld[i] = ld[i - 1] + 1;
    for (int i = 2; i <= n; i++)
        if (a[i - 1] > a[i])
            lu[i] = lu[i - 1] + 1;
    for (int i = n - 1; i >= 1; i--)
        if (a[i + 1] < a[i])
            rd[i] = rd[i + 1] + 1;
    for (int i = n - 1; i >= 1; i--)
        if (a[i + 1] > a[i])
            ru[i] = ru[i + 1] + 1;

    int ans = 0;
    int mm = 0;
    int mc = 0;
    for (int i = 1; i <= n; i++)
    {
        if (lu[i] > mm)
            mm = lu[i], mc = 1;
        else if (lu[i] == mm)
            mc++;
        if (ld[i] > mm)
            mm = ld[i], mc = 1;
        else if (ld[i] == mm)
            mc++;
    }

    for (int i = 2; i < n; i++)
    {
        if (a[i - 1] < a[i] && a[i + 1] < a[i])
        {
            if (ld[i] % 2 == 0 && rd[i] % 2 == 0 && ld[i] == rd[i] && ld[i] == mm && mc == 2)
            {
                ans++;
            }
        }
    }

    cout << ans << endl;
}