题目大意请见题目链接中的翻译。本题解中的表述将对照这个翻译。
先决条件：动态规划板子题（数塔问题） | 有向无环图与拓扑排序
这是一道博弈论（研究游戏必胜策略等问题的学说）问题。
游戏状态
显然，游戏局面除了硬币所在的格子之外就没有别的区别了。因此，游戏状态定义为：硬币所在的格子。
必胜与必败状态
It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.
题目提到，游戏一定是有限的，即，一定有人有必胜策略。因此，如果以某个状态为 初始状态 时，先手 玩家是 有必胜策略 的，那么称这个状态为 必胜状态。否则，因为一定有一个人会有必胜策略，所以这个状态就叫做 必败状态。
- 硬币不能移动的状态是 必败状态，因为先手立刻就输了。
- 其他情况下：
- 如果当前状态的下一步 可以 是 必败状态，那么这个状态是 必胜状态，因为，当前状态下，先手有决定权，因此可以将下一个 必败状态 留给后手。
- 否则，即当前状态的下一步 一定 是 必胜状态，那么这个状态是 必败状态，因为，当前状态下，先手无论怎么走，都会将一个 必胜状态 留给后手。
实现方法 / 复杂度分析
由于硬币只能从数值小的格子移到数值大的格子，因此如果从 当前状态 向 下一步能到达的状态 连有向边，形成的一定是 有向无环图，其中，方格中的数字就是 拓扑序。
我们按拓扑序从大到小进行DP。这样，DP进行到数值小的格子时，数值大的格子一定已经完成了DP，当前格子的必胜性就可以确定。
在已知当前格子，枚举当前格子可以到达的状态时，只枚举与当前格子距离为当前格子中数值的格子（这是移动硬币的条件之一）。因为如果枚举1..n，时间复杂度会变成O(n^2)肯定会TLE
而使用只枚举倍数的方法，复杂度值是：
\sum\limits_{i=1}^{i \leq n} \lfloor \frac{n}{a_i} \rfloor
Furthermore, there are no pair of indices i =\not j such that a_i = a_j
题目提到格子中的数范围是1..n，且两两不同，因此，复杂度值简化为
\sum\limits_{i=1}^{i \leq n} \lfloor \frac{n}{i} \rfloor
如果你数学学得好，你早就知道，这个值大约是n\cdot ln(n)。如果你不知道，你可以用下面的程序验证。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 100000;
int ans = 0;
for(int i=1;i<=n;i++) {
ans += n/i;
}
cout<<ans<<endl;
}
输出：1166750
因此肯定能过。
代码
Talk\ is\ cheap,\ show\ me\ the\ code.
// status: [Accepted]
// oj: [luogu]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
// 格子中的值
int arr[MAXN];
// 值为i的格子编号为pos[i]
int pos[MAXN];
// 格子是必胜(1)还是必败(0)
int status[MAXN];
int n;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int i=1;i<=n;i++) {
pos[arr[i]] = i;
}
for(int i=n;i>=1;i--) {
int u = pos[i];
status[u] = 0;
int v = u;
// 只枚举距离是倍数的
while(v - arr[u] > 0) v-=arr[u];
for(;v<=n;v+=arr[u]) {
if(!(arr[u] < arr[v])) continue;
// 发现能到达必败状态，说明这个状态一定是必胜的。
if(status[v] == 0) {
status[u] = 1; break;
}
}
}
// 输出结果
for(int i=1;i<=n;i++) {
if(status[i]) {
cout<<'A';
}
else {
cout<<'B';
}
}
cout<<endl;
}
评测记录：R24491666
Comments | NOTHING