https://codeforces.com/contest/1495

B. Let’s Go Hiking

 

题意：给定一个 n 的排列，两个人轮流操作：第一次时先选一个初始位置放棋子，之后先手可以移动到两边一个比当前位置权值小的位置，后手可以移动到两边一个比当前位置权值大的位置。问先手有几个初始位置可以必胜。

博弈

思路比较直接，但是细节有点多，要考虑全面。

枚举每个位置作为先手的初始位置，分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int a[N];
int l[N], r[N], mx[N];
multiset<int, greater<int> >st;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	l[1] = r[n] = 0;
	for (int i = 2; i <= n; i++) {
		if (a[i] > a[i - 1])l[i] = l[i - 1] + 1;
		else l[i] = 0;
	}
	for (int i = n - 1; i >= 1; i--) {
		if (a[i] > a[i + 1])r[i] = r[i + 1] + 1;
		else r[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		mx[i] = max(l[i], r[i]);
		st.insert(mx[i]);
	}
	int ans = 0;
	bool flg = 0;
	for (int i = 1; i <= n; i++) {
		if (min(l[i], r[i]) <= 1)continue;
		st.erase(st.find(mx[i]));
		int x = (*st.begin());
		if (l[i] % 2 == 0 && r[i] % 2 == 0) {
			if (mx[i] > x && l[i] == r[i])ans++;
		}
		else if (l[i] % 2 == 0 && r[i] % 2 == 1) {
			if (l[i] > max(x, r[i]) && r[i] > l[i] - 1)ans++;
		}
		else if (l[i] % 2 == 1 && r[i] % 2 == 0) {
			if (r[i] > max(x, l[i]) && l[i] > r[i] - 1)ans++;
		}
		st.insert(mx[i]);
	}
	printf("%d\n", ans);
	return 0;
}