[洛谷题解] CF1033C Permutation Game

题目链接:CF1033C Permutation Game


题目大意请见题目链接中的翻译。本题解中的表述将对照这个翻译。


先决条件:动态规划板子题(数塔问题) | 有向无环图与拓扑排序

这是一道博弈论(研究游戏必胜策略等问题的学说)问题。

游戏状态

显然,游戏局面除了硬币所在的格子之外就没有别的区别了。因此,游戏状态定义为:硬币所在的格子。

必胜与必败状态

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注