【超详细题解】| 纸牌游戏

文章有些长，如果嫌烦可以直接划到最底下看代码

---

由于题目只要求输出 $YES$ 和 $NO$ ，所以我们实际上可以不用进行麻烦的模拟操作，只需要搞懂它的原理即可。
以输入数据#1的
$3\ 3\ 6\\3\ 6\ 4\ 1\ 2\ 5$
为例，假设它现在都堆叠在 $(1,1)$ 的格子上了，由条件和题目可知，棋盘大小为 $3 \times 3 = 9$，其中除了 $(1,1)$ 格子和 $(n,m)$ 格子之外都可以随意放纸牌，则由 $9 - 2 = 7$ 个可随意放纸牌的格子，暂且称它为“$空格子$”。

由于只需要输出 $YES$ 和 $NO$ ，因此不需要考虑如何在空格子上放纸牌，只需要考虑用到多少个空格子即可，这样的话就不需要二维数组了，只需要一维数组来模拟空格子的所有纸牌的操作过程就可以了，即只需要完成将纸牌往数组最后插入，以及纸牌在数组两端的删除（可以用 $deque< \blue{int} >\ dq$ 来模拟）。

根据题意，首先挪出 $(1,1)$ 格子的是 $3$ ，那么将3加入dq：

1	2	3	4	5	6	7
3

然后将 $6$ 加入dq：

1	2	3	4	5	6	7
3	6

由于 $(n,m)$ 从上往下为 $1-n$ ，故应按照 $n-1$ 的顺序将纸牌放到 $(n,m)$ 格子，这个移到 $(n,m$ 格子的操作可以视为将在dq中的当前元素（即此时的末尾元素）删除，故变为：

1	2	3	4	5	6	7
3

接着插入4：

1	2	3	4	5	6	7
3	4

$\cdots$ $\cdots$
依此类推，最后插入完5又删除5之后就会变成这个样子：

1	2	3	4	5	6	7
3	4	1	2

接下来，就到了处理空格子中的纸牌了。首先处理 $4$ ，这时候可以把dq想象成一个队列（毕竟它本来就是双端队列），完成这样的操作：

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

其中第一、二行是删除 $3$ 将 $3$ 移到末尾的操作，而第三行是删除 $4$ ，表示 $4$ 已经移到了 $(n,m)$ 的位置。
同样的道理，可以完成下面的操作：

1	2	3	4	5	6	7
1	2

这删除了 $3$

1	2	3	4	5	6	7
1

这删除了 $2$

1	2	3	4	5	6	7

到此为止，所有牌都放到了位置上。这里可以注意到，在dq模拟 $stack$ 栈操作时，我们的空格子“数组”中存放的数据个数是单调不下降的，但是在模拟 $queue$ 队列操作时，这个“数组”元素个数在单调下降。

由于经过计算，我们样例最大空格子数量为7，这说明如果“数组”长度不够，则输出 $NO$ ，显然，只有dq模拟 $stack$ 时“数组”元素个数才可能增大，因此，我们可以直接用 $stack$ 来替换烦人的 $deque$ ，只要完成插入和删除操作就可以了，最后判断栈的长度即可。

但是，用 $stack$ 还是有些小题大做了，因为我们只需要求栈的长度！最后我们判断栈的长度时和栈中元素没有任何关系！况且，输入数据的顺序在我们将它插入栈中后已经不重要了，这表示我们可以省略输入数据的数组，那么我们也可以顺势将这个栈省略掉，节省内存空间，直接用 $\blue{int}$ 类型的变量 $cnt$ 来记录长度即可。于是，我们判断 $(n,m)$ 处当前应该存入什么数据 $cur$ ，如果输入当前数据 $a$ 和对应插入数据 $cur$ 相等，则将 $cur - 1$，否则就将记录栈长度的 $cnt + 1$，最后将 $cnt$ 和棋盘空格子数量进行比较即可。

---

$AC$ 代码：

#include<iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        int size=n*m-2,cnt=0,cur=k,a;
        while(k--){
            cin>>a;
            cnt+=a!=cur,cur-=a==cur;
        }
        if(cnt>size)cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

时间复杂度：

$O\,(t\cdot k)$ ，题目给定 $1\leq t\leq 100,\,\,1\leq k\leq 10^5$ ，可知最大时间复杂度为 $10^7$ 可以过
这还不过？