Let’s Go Hiking

Created by LXC on Wed Sep 20 19:23:56 2023

https://codeforces.com/problemset/problem/1495/B

ranting: 1900

tag: games, greedy

problem

给出一个1到n的排列$a_1, a_2, \cdots, a_n$，现在A和B两个人在博弈。

A先选择一个位置x，B后选择一个位置y，x和y不能冲突。

然后A和B轮流执行操作。

A只能移动到相邻的位置x-1或x+1上，并且移动后的位置上的值要比移动前的位置上的值小，也不能移动到y上。

B只能移动到相邻的位置y-1或y+1上，并且移动后的位置上的值要比移动前的位置上的值大，也不能移动到x上。

当有一方移动后而另一方无法移动则获胜。

问A能获胜的x的位置有哪些。

$n \le 10^5$

solution

很有趣的思维题。只要能分析出来结论代码就很简单。

如果x处于$a_{x-1} < a_{x} < a_{x+1}$或者$a_{x-1} > a_{x} > a_{x+1}$这样的”坡道”上，A只能向一个方向移动，而B可以在这个方向上堵住A。所以这样的坡道位置是不可行的。

因此，我们只能选择$a_{x-1} < a_{x} > a_{x+1}$这样的”峰值”位置。B是不能堵住A了，只能比谁走得远了。B选择一条最长的坡道，而A所处的山峰两侧坡道如果都不是B所选择坡道，则必输。即便A和B都是选的最长坡道，但是通向的不是同一个山峰，由于A先手缘故，A必输，所以可以判段出一个结论就是不能有多条通向不同山峰的最长的坡道。

再进一步分析，A和B走同一条坡道的情况下，B只需要在距离A奇数移动步数的位置就可以让A必输。

但是A在山峰，所以如果B所选位置到达山峰的距离小于另一边坡道的长度，那么A就不会选择与B同一个坡道。

现在我们知道了A选择的山峰是拥有最长坡道的山峰，且B会在最长坡道上选择位置。这个山峰如果另一侧坡道较短，实际上A就必输了，因为B至少有两个相邻位置可以选，其中包含了偶数位置。

所以最长坡道的山峰两侧的坡道是等长的，并且长度也不能是奇数。

综上所述，x的位置最多只有一个点，这个点满足的条件有：这个点是峰值点，只有这个峰值点拥有最长坡道，这个点两侧坡道长度相等且为偶数。

我们可以先预处理所有峰值两侧的坡道长度。

然后统计最长坡道长度，若为奇数，无答案。

然后统计最长坡道通向不同峰值个数，有多个，无答案。

最后看最长坡道峰值点两侧坡道长度是否相等，不相等，无答案。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), l(n), r(n);
    for (auto& i : a)
        cin >> i;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] < a[i])
            l[i] = l[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] > a[i + 1])
            r[i] = r[i + 1] + 1;
    }
    int mx = 0;
    for (int i = 0; i < n; i++) {
        mx = max({mx, l[i], r[i]});
    }
    if (mx % 2) {
        cout << "0\n";
        return;
    }
    int cntmx = 0;
    for (int i = 0; i < n; i++) {
        if (l[i] == mx || r[i] == mx)
            cntmx++;
    }
    if (cntmx != 1) {
        cout << "0\n";
        return;
    }
    for (int i = 0; i < n; i++) {
        if (l[i] == mx && r[i] == mx) {
            cout << "1\n";
            return;
        }
    }
    cout << "0\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}