文汇网站建设河南天丰建设工程有限公司网站
目录
一、题目
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;
}