Day13

T6

题意：

Alice和Bob去玩一个游戏。游戏在一个棋盘上玩，棋盘上有n个格子，每个格子上包含一个1到n之间的数字$a_i$ .任意两个格子内的数字不相同。

棋子可以放在1~n任意一个格子上。Alice和Bob轮流移动棋子，Alice先手。棋子可以从i格移到j格，只有一下条件均满足时才允许移动：

• $a_j > a_i$

• $|i - j| mod$ $a_i$ $= 0$

  无法进行移动的一方判负。对于每一个可能的初始位置，若双方都采取最优策略，判断谁能获胜。

  可以证明，游戏总是有限的，即总存在一方有必胜策略。（因为只能往大了移动）

  $1\le n \le 10^5$

  任意$i\neq j$ 都有$a_i \neq a_j$

  思路：

  不能移动的状态是必败态。若某种状态可以转移到必败态，那么这个状态可以是必胜态，先手则必胜。若这种状态只能转移到必胜态，那么这个格子对于先手一定是必败态。

  考虑每一个点，枚举它可以到达的节点。只能是$a_i$ 的倍数

  由于值各不相同，而且只能从a小的地方转移到a大的地方，所以可以枚举值，然后看这个值能到的全部地方，根据上面推出来的更新值即可。

  可以用$win_i$ 表示第i格为起点可否赢。$pos_i$ 表示值为$i$ 的下标的值

  代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n;
  int a[100005];
  int pos[100005];
  bool vis[100005];
  int main() {
  	cin >> n;
  	for(int i = 1;i <= n;i ++) {
  		cin >> a[i];
  		pos[a[i]] = i;
  	}
  	for(int i = n;i >= 1;i --) {
  		int p = pos[i];
  		bool Flag = 1;
  		for(int j = p-a[p];j >= 1;j -= a[p]) {
  			if(!vis[j] && a[j] > a[p]) vis[p] = 1;
  		}
  		for(int j = p+a[p];j <= n;j += a[p]) {
  			if(!vis[j] && a[j] > a[p]) vis[p] = 1;
  		}
  	}
  	for(int i = 1;i <= n;i ++) {
  		if(vis[i]) {
  			cout << "A";
  		} else {
  			cout << "B";
  		}
  	}
  	return 0;
  }