CF1740D Knowledge Cards

题意

有一个 \(n \times m\) 的棋盘。现在\((1,1)\)中有一个栈，你可以按照一定的顺序进行出栈操作，每次都可以移动一个卡片到一个相邻的空白位置，但是卡片不能重合。问，能否通过若干次操作，将\((1,1)\)中全部的卡片移动到\((n,m)\)的栈中并使得这个栈按照从栈顶到栈底单调递增。

注意，操作过程中不能向\((1,1)\)中移动或者从\((n,m)\)中移走

思路

先看一个游戏：

现在有一个\(n\times m\)的格子，每次你都可以移动蓝色或者灰色的格子到相邻的空白格子里，目标是将蓝色的格子移动到\((n,m)\)

很明显，一定存在一种操作满足上述条件

而类比到题目里，\((1,1)\)和\((n,m)\)就相当于两个栈，蓝色的就相当于现在希望入栈的值，而灰色的就是已经出了\((1,1)\)但是还没发进入\((n,m)\)

可以发现，一个\(n\times m\)的格子中最多存在\(n\times m-4\)个灰色格子，也就是说等待的数最多只能有\(n\times m-4\)个

其实，相当于就是每一个数之前，有多少个比他小的数，就是他出\((1,1)\)之后方格中灰色格子的个数，而这个个数一旦超出\(n\times m-4\)，那么就无法完成操作

据此，判断即可，而求每个数前面的有多少个比他小的数可以用桶\(O(n)\)实现。

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
int n,m,k;
int a[Maxn];
int maxn,cnt,now;
int f[Maxn];
void run()
{
    cin>>n>>m>>k;maxn=-1e9,now=k;
    memset(f,0,4*(k+3));
    for(int i=1;i<=k;i++)
    {
        cin>>a[i];
        f[a[i]]=1;
        if(a[i]==now)
        {
            maxn=max(cnt,maxn);
            while(f[--now]) cnt--;
        }
        else cnt++;
    }
    if(maxn>n*m-4) cout<<"TIDAK";
    else cout<<"YA";
    cout<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) run();
}