给出 $1 \sim n$ 的排列, 开始时A, B各选一个点, 然后轮流移动, 每次移动只能移动到相邻的位置, 且不能碰到另一个人. 并且, A只能走更小的数字, B只能走更大的数字. A先走, 不能走的人输. 问A必胜的选点有多少个.
$2 \le n \le 10^5$
可以发现, 和排列没什么关系. 看成折线图, 发现, A一定要选峰, 否则在坡上, B只需要卡他下坡路, A就无了.
所以现在需要看某个峰是不是必胜.
考虑仅有一个峰, 首先能够发现, 如果AB相对走的话, 距离为奇数, A败; 距离为偶数, A胜. 更多地(当时这么思考的), 如果下落长度为奇数, 那么B只要放在底下(或者离峰距离为奇数的地方), A必败. 所以此时A一定不会走是奇数的一边, 那么他只能走另一边. 如果另一边是奇数, 那无论如何必败.
这启示我们考虑两边的下落距离奇偶性.
还可以发现, 如果有一边很长, 另一边较短, B可以放在较长的边上, 这样A走另一边不能胜利. 走这一边还需要看B放的位置到峰是不是奇数.
这启示我们考虑两边下落的距离差.
所以这样讨论:
- 2奇: 必败
- 1奇1偶:
- 奇>偶: B放奇边底端, A必败
- 偶>奇: B放偶边(长边)等于奇边的位置, A必败
- 2偶:
- 不相等: B放较长边的 (较短边+1) 的位置, A必败
- 相等: A必胜
画图即可. 由于重点不在证明而在思考方式, 所以不画(证)了.
然后还需要注意一点, 如果有多个峰, 或者说多个"下落"(边界点不是峰, 但是有下落), 那么仅有 “拥有最大落差的峰” 才可能成为必胜点. 否则, B只爬走最大坡, A一定没B走得远. 所以结论是, 当且仅当落差最大的峰唯一, 且左右两边落差相等且为偶数, A的必胜点且仅有一个(这个峰).
太菜了, 考场想1h+也没想出来, 逻辑混乱, 头脑混沌, 不知所措. 后来还是和 littlechai 讨论了半天才解决.
思维题还是要多练, 没有形成一种有用的思考方式.
复杂度$O(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
51
52
53
54
|
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define lowbit(x) (x&(-x))
#define LCH(x) (x<<1)
#define RCH(x) (x<<1|1)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INTINF = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e5+10;
int n, p[MAXN], ans = 0, f[MAXN], g[MAXN], mx = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", p + i);
for (int i = 2; i <= n; i++)
f[i] = p[i] > p[i-1] ? f[i-1] + 1 : 0;
for (int i = n-1; i; i--)
g[i] = p[i+1] < p[i] ? g[i+1] + 1 : 0;
for (int i = 1; i <= n; i++)
mx = max(mx, max(f[i], g[i]));
if ((mx&1)^1) {
for (int i = 1; i <= n; i++)
if (f[i] == mx && g[i] != mx || g[i] == mx && f[i] != mx) {
ans = 0;
break;
}
else if (!ans && f[i] == mx && g[i] == mx)
ans++;
else if (ans && (f[i] == mx || g[i] == mx)) {
ans = 0;
break;
}
}
printf("%d\n", ans);
return 0;
}
|