博弈？题解

写在前面

上次写博客已经是两年前的事情了，明天就网络赛了，心中烦躁，一时也不知道写什么好，故此传一下这道题的题解，也算是我出的第一道题，题目不难，还是挺有纪念意义的。

题目回顾

给定长度为 $n$ 的排列 $p[1..n]$。Alice 和 Bob 轮流操作，Alice 先手。每一步，玩家必须选择一个位置 $i $且满足 $ p[i]≠i$，然后执行一次交换操作：$swap(p[i], p[p[i]]);$

如果当前排列已经是恒等排列，即对所有 $j$ 都有 $p[j]=j$，则无法再走，当前玩家失败。问：在双方都最优的情况下，Alice（先手）是否必赢？

并没有所谓的最优策略

如果你实际操作一下，你会发现，每一次合法的操作，都会贡献一个$p[i] = i$，而且这个是不可变的，也就是说，根本不存在所谓的最优策略，每一个合法的策略都是最优策略，所以这或许都称不上一个博弈的题目。

“环”的被发现

我们再尝试模拟一下，对于一个这样的数据

2 3 1 6 4 5
1 2 3 4 5 6

我们手摸一下这个数据，可以发现，这个数据的操作被完美的分成了两部分，1-3是一部分，4-6是一部分。并且当我们把p[i]作为指向来思考，就可以发现，这是一个不折不扣的“环”，第一个位置指向第二个位置，第二个位置指向第三个位置，第三个位置反过来又指向第一个位置。这有什么意义呢？这意味着，如果我们将某个位置作为中间商，来不断交换，只需要k-1次交换（ k是这个“环”中元素的个数），这个“环”就能被还原。如果熟悉魔方盲拧的同学应该知道我说的是什么，我们继续用这个例子来讲解：

对于前面的那个“环”，我们让1号位做中间商。那么1->2,1号能和2号交换，变成了：

3 2 1
1 2 3

现在1上面是3，也就是1->3,1号和3号交换，这个“环”就还原了。这个首尾相接的“环”实际上也就是还原的次序。

次数的奇偶与结果

对于每一个”环“，都是$k-1$次交换，那么不难发现，总共需要的交换次数：（假设一共有$c$个环） $\sum_{j=1}^{c} (k_{j} -1) = (\sum_{j=1}^{c}k_j) - c = n - c$ 也就是说，我只需看$n-c$次行动，是$Alice$赢还是$Bob$赢，显而易见，奇数次是$Alice$,偶数次是$Bob$。

其实如果说你不想推式子，也没有发现“环”，但是你知道每次交换都会产生一个$p[i] = i$，直接模拟也是可以的，对于每一个$ p[i]≠i$ 的地方，反复的执行$swap$,因为每次肯定会产生一个答案，复杂度也是$O(n)$的。

复杂度分析

时间复杂度：
- 判断整个有多少个环，只需要所有遍历一遍，整体 $O(n)$。

完整 C++ 实现

#include <bits/stdc++.h>
using namespace std;

// 用于比较常见的 输出"YES"和"NO"题目
#define returnNo return void(puts("No"))
#define returnYes return void(puts("Yes"))
//

// 用于 debug函数,只会在本地编辑器才显示
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '[';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << ']';
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
//

// 常用头
#define int long long
#define endl '\n'
constexpr int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    vector<int> vis(n + 1, false);
    int c = 0;

    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            c++;
            int u = i;
            while (!vis[u])
            {
                vis[u] = true;
                u = v[u];
            }
        }
    }
    if ((n - c) % 2 == 1)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    while (_--)
        solve();
}

奇排列？偶排列？

如果你学习过线性代数，那么对奇排列和偶排列一定不陌生。在这道题里，我们已经论证过了，并没有所谓的最优策略，胜负完全是由次数来决定的，而我们在线性代数中学过，只要交换两个数，那么奇排列就会变成偶排列，偶排列就会变成奇排列。对于恒等排列而言，肯定是偶排列。也就是说，我们要经过若干次交换，让这个排列变成偶排列。也就是说，如果说原来排列是奇排列，那么肯定是经过奇数此次交换，那么Alice赢，如果是偶排列，则是偶数次交换，那么是$Bob$赢。

因此我们可以通过判断这个排列是奇排列还是，偶排列来确定这道题的答案。而确定奇排列和偶排列，我们可以通过归并排序的方法，也可以使用树状数组的方法来求解这个题

下面是树状数组的示例代码：

#include <bits/stdc++.h>
using namespace std;

// 用于比较常见的 输出"YES"和"NO"题目
#define returnNo return void(puts("No"))
#define returnYes return void(puts("Yes"))
//

// 用于 debug函数,只会在本地编辑器才显示
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '[';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << ']';
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
//

// 常用头
#define int long long
#define endl '\n'
constexpr int N = 2e5 + 10;

int n, ans;
int s[N];
vector<int> arr;

int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int k)
{
    for (; x <= N; x += lowbit(x))
        s[x] += k;
}

int getsum(int x)
{
    int sum = 0;
    for (; x > 0; x -= lowbit(x))
        sum += s[x];
    return sum;
}

int query(int l, int r)
{
    return getsum(r) - getsum(l - 1);
}

void solve()
{
    cin >> n;
    for (int i = 1, t; i <= n; i++)
    {
        cin >> t;
        arr.push_back(t);
    }
    vector<int> tmp(arr);
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < n; i++)
    {
        arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin() + 1;
        update(arr[i], 1);
        ans += query(arr[i] + 1, n + 1);
    }
    if (ans % 2 == 1)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    while (_--)
        solve();
}