博弈论+递推+调和级数枚举，CF 1033C - Permutation Game

本文主要是介绍博弈论+递推+调和级数枚举，CF 1033C - Permutation Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1033C - Permutation Game

---

二、解题报告

1、思路分析

我们考虑一个位置符合什么条件可以必胜？

如果可以跳到一个必败的位置

考虑最大的格子一定是必败

而每个格子只能跳到比自己大的格子

于是我们就可以倒序处理状态

对于每个格子枚举比自己大的整数倍距离的格子中是否有必败态

似乎是O(N^2)，但是由于枚举的是自己的倍数距离的下标， 是O(NlnN)的

2、复杂度

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

3、代码详解

 ​

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e8 + 7, P = 1e9 + 7;void solve() {int n;std::cin >> n;std::vector<int> a(n), pos(n);std::vector<bool> f(n);std::string res(n, 'B');for (int i = 0; i < n; i ++ ) std::cin >> a[i], pos[a[i] - 1] = i;for (int i = n; i; i -- ) {int j = pos[i - 1];while (j >= i) j -= i;for (; j < n; j += i) {if (a[j] <= i) continue;if (!f[j]) {f[pos[i - 1]] = true;break;}}if (f[pos[i - 1]]) res[pos[i - 1]] = 'A';}std::cout << res;
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}

这篇关于博弈论+递推+调和级数枚举，CF 1033C - Permutation Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---