博弈论，CF 1600E - Array Game

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1600E - Array Game

---

二、解题报告

1、思路分析

记最长递增前缀长度为L，最长递减后缀长度为R

必胜态：L R 一奇一偶 或者 二者均奇

否则为必败态
证明：

先考虑一侧，比如递增前缀，如果L是偶数，那么我们先手在左侧拿，后手一定也能在左侧拿

如果一直保持左侧拿，先手就输了

如果LR都是偶数，那么就算先手前后来回换，我们一定会走到一侧没法拿另一侧为偶数，然后输掉游戏，因此 LR都是偶数为必败态

若L，R一奇一偶，那么先手拿奇，后手就落入了必败态

若L，R二者均奇，那么我们拿第一个元素大的那个，就会使得一侧不能拿，后手会落入必败态

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>
#include <ranges>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) std::cin >> a[i];int L = 0, R = 0;for (int i = 0; i < n; ++ i)if (!i || a[i] > a[i - 1])++ L;elsebreak;for (int i = n - 1; ~i; -- i)if (i + 1 == n || a[i] > a[i + 1])++ R;elsebreak;if (((L + R) & 1) || ((L & 1) && (R & 1)))std::cout << "Alice";elsestd::cout << "Bob";
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --)solve();return 0;
}