1 条题解

  • 0
    @ 2025-2-12 15:21:31

    Solution

    首先,这里输入很奇葩。我们可以把它拆成一个序列,设序列长度为 N=n×mN=n\times m

    假设 AN1+2ANA_{N-1}+2 \leq A_N。可以证明,Xuan 总是会获胜。

    • 如果 Xuan 能够使得 AN<AN1A_N<A_{N-1} 并让 Xiang 面对一个必输的局面,Xuan 就会赢。
    • 假设通过使 aN<aN1a_N<a_{N-1} 能够获得所有必胜的局面。然后,如果我们 aNaN1+1a_N \gets a_{N-1}+1,那么可以从该局面过渡到的所有局面都是必胜的。因此,将 aNaN1+1a_N \gets a_{N-1}+1 所得到的局面是必败的。所以,初始局面是必胜的。

    接下来,考虑当给定一个满足 aN=aN1+1a_N=a_{N-1}+1 的局面。根据上述证明,Xuan 和 Xiang 不应该给出最大两个元素差为 22 或更大的局面。综上,我们可以假设 aa 的最大两个元素的差为 11

    然后,我们发现每一步操作都会将 max{a}\max\{a\} 减少 11

    max{a}=N1\max\{a\}=N-1 时,该局面无法进行操作,因此可以根据输入中 aNa_NN1N-1 的奇偶性差异来确定赢家。

    复杂度为 O(N)O(N)

    但是输入不是有序,进行排序。复杂度为 O(NlogN)O(N \log N)

    std 和这里的说法有些不同,std 写法更为简洁。

    Code

    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int a[300020];
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n * m; i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + n * m + 1);
        for (int i = 1; i <= n * m; i++)
        {
            a[i] -= i - 1;
        }
        if (a[n * m] == a[n * m - 1] && (a[n * m] % 2 == 0))
            puts("Xiang");
        else
            puts("Xuan");
        return 0;
    }
    
    • 1

    信息

    ID
    717
    时间
    1500ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    87
    已通过
    5
    上传者