【最长上升子序列】【博弈论】Game on Permutation—CF1860C

Game on Permutation—CF1860C

思路

假设 Alice 最初选择的是 $a_i$。

如果先手必胜，那么 $a_i$ 左边必须存在比它小的元素，并且不管 Bob 多么“聪明”，Alice 都能赢。

在 Bob 很聪明的情况下，Bob 最多移动一次。
证明：
如果 Bob 移动的此时 $\ge 2$，那么以 $a_i$ 结尾的最长严格上升子序列的长度一定 $\ge 4$，Bob 完全可以在第一次移动的时候就移动到一个左边有且仅有一个比这个元素小的元素的位置，下一步 Alice 将不得不移动到这个位置，再下一步 Bob 不能移动，Bob 获胜（其实 Bob 必须移动到这个位置，不然他就输了，看下边的分析）。
如果 Bob 第一次移动的时候就移动到一个左边没有比这个元素小的元素的位置，那么 Bob 必败，Bob 不会这么做。
如果 Bob 第一次移动的时候就移动到一个左边至少有两个比这个元素小的元素的位置，那么下一步 Alice 可以移动到一个左边有且仅有一个比这个元素小的元素的位置，Bob 必败，Bob 不会这么做。

所以 $a_i$ 点先手必胜的条件：Bob 至少能移动一次，且第一次移动后的位置 $a_j$ 左边不存在比 $a_j$ 小的元素。也就是：以 $a_i$ 点结尾的最长严格上升子序列的长度为 $2$。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 3e5 + 10;

int n;
int a[N];

void solve() {
	cin >> n;
	vector <int> a(n + 1); // 题目中的 p 数组
	for (int i = 1; i <= n; i ++) cin >> a[i];
	
	int res = 0;
	
	vector <int> b(n + 1);
	int len = 0;
	for (int i = 1; i <= n; i ++) {
		if (i == 1 || a[i] > b[len]) {
			b[++ len] = a[i];
			if (len == 2) {
				res ++;
			}
		} else {
			int k = lower_bound(b.begin() + 1, b.begin() + len + 1, a[i]) - b.begin();
			if (k == 2) {
				res ++;
			}
			b[k] = a[i];
		}
	}
	
	cout << "       ";
	cout << res << "\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
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