P11969 「ALFR Round 7」T2 Game

Wilderness_ · 2025-03-23 19:37:24 · 题解

思路

先考虑 t=1 的情况，显然顺序找出第一个满足 a_i\neq i 的数以及对应的 a_j=i，将 a_i 和 a_j 交换位置得出的序列字典序最小。

而当 t=2 时，先手的操作就要考虑后手对其的影响。不难发现后手必会进行如下操作：

• 将最大的数交换到第一个，若最大的数已在第一个就将次大的数交换至第二个，以此类推，即顺序找出第一个满足 a_i\neq n-i+1 以及对应的 a_j=n-i+1，将 a_i 和 a_j 交换位置。

所以

• 当 a_1=n 时，先手若交换除 a_1 外其他位置，后手就可以将第一个满足 a_i\neq n-i+1 的数进行操作，则序列字典序必然会小于原序列。所以先手必会先把 n 从 a_1 交换到其他位置，然后让后手将其换回；
• 若 a_1\neq n 时，则后手必然会将 a_1 交换为 n，那么不管怎么交换 a_1 都没有影响。那么，先手可以考虑使 a_1=n 时使得余下部分的字典序最小，即找出 a_{i+1}\neq i 以及 a_{j}=i，将 a_{i+1} 和 a_{j} 交换位置，此时必然最优。

考虑 t>2 的情况，发现先手怎么操作，后手都可以使用一步将先手上一步撤销，所以 t 为奇数时像 t=1 时考虑，t 为偶数时像 t=2 时考虑即可。

Code

//代码写的极其抽象，见谅
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
    return;
}
int dg[100010];
signed main()
{
    int t=read(),n=read();
    for(int i=1;i<=n;++i)dg[i]=read();
    if(t&1)
    {
        int syh=0;
        for(int i=1;i<=n;++i)
        {
            if(i^dg[i])
            {
                syh=i;
                break;
            }
        }
        if(!syh)
        {
            for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
            return 0;
        }
        for(int i=1;i<=n;++i)
        {
            if(dg[i]==syh)
            {
                swap(dg[syh],dg[i]);
                break;
            }
        }
        for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
        return 0;
    }
    else
    {
        int syh=0;
        if(dg[1]==n)
        {
            for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
            return 0;
        }
        if(dg[1]==1&&dg[2]==n)
        {
            for(int i=3;i<=n;++i)
            {
                if(i-1^dg[i])
                {
                    syh=i-1;
                    break;
                }
            }
            cerr<<syh<<endl; 
            if(syh)
            {
                for(int i=1;i<=n;++i)
                {
                    if(dg[i]==syh)
                    {
                        swap(dg[syh+1],dg[i]);
                        break;
                    }
                }   
            }
            swap(dg[1],dg[2]);
            for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
            return 0;
        }
        else
        {
            for(int i=2;i<=n;++i)
            {
                if(i-1^dg[i])
                {
                    syh=i-1;
                    break;
                }
            }
            if(syh)
            {
                for(int i=1;i<=n;++i)
                {
                    if(dg[i]==syh)
                    {
                        swap(dg[syh+1],dg[i]);
                        break;
                    }
                }   
            }
        } 
        for(int i=2,j=n;i<=n;++i,--j)
        {
            if(j^dg[i])
            {
                syh=j;
                break;
            }
        }
        if(!syh)
        {
            for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
            return 0;
        }
        for(int i=1,j=n;i<=n;++i,--j)
        {
            if(dg[i]==syh)
            {
                swap(dg[i],dg[n-syh+1]);
                break;
            }
        }
        for(int i=1;i<=n;++i)write(dg[i]),putchar(' ');
    }
    return 0;
}