前沿资讯!NOIP2022第二题喵了个喵题解与SPJ

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

2022-12-08 16:22:23 来源：博客园

题目大意：n个双端队列，操作1可以从队尾入队，相邻相同则消除队尾两个元素；操作2可以选择两个队头元素相同的队列，消除两个队头元素，m个范围在1~2n-1的元素进来，如果操作才能让最终所有队列为空？

解题思路

对于元素种类为2n-2的情况，每个队列只放2个元素，即使放满，也是可以消除的：在队尾就通过入队直接消除；在队头就利用空队进行消除。

(资料图片)

这启发我们要利用好空队，但有一种情况，不得不用空队，那就是连续2n-1个元素都不一样。

如果后面元素是队头，我们可以不用空队，让队头所在队列临时存放3个，他很快就被消除回2个元素了。因为他是最早需要用空队的，其他都可以通过队尾消除或者放入新的空位。（此刻之前其他元素都是队尾元素）

如果后面元素是队尾怎么办？总会出现队头的，关键在于哪个队列的队头先出现！

如果该队列先出现队尾再出现队头，那么它可以通过入队消除2次成为空队列，期间也不需要用到空队列，他将成为新的空队列（在成为新的空队列之前，可以入队消除，但不能只入队不消除）。

如果该队列先出现队头再出现队尾，那么该队列可以临时存放3个元素，他可以使用空队列前变回2个元素。（其实就是队头先出现）

当然，不用忘记当前元素，自己也是“队尾”，如果自己先出现，可以临时占用空队。

函数f进行操作管理，具体操作存储到数组a和b。操作1是入栈，入栈后能消除就消除，操作2是消除栈底，期间需要维护i是否栈底d[i]，i在哪个栈p[i]。具体思想请看思维导图，代码注释中的栈底即队头，栈顶即队尾。

代码核心是预留空栈u，如果他被占用，那么记录下一个成为空栈的是谁，因为能保证下次使用空栈时他会成为空栈。

以上为O(nm)暴力AC代码，6万万时间复杂度勉强不超时吧！

我们也可以在操作过程中“排序”，把元素至少2个的栈放到后面，这样就不需要暴力查找空位了。

原理：记录有多少个栈是满的，全部放到后面。新增一个满栈，放最后；一个满栈降到1个元素，放到前面。这样基本能保证第二个栈有空位，如果没有空位，那就要考虑是否动用空栈了。

注意：栈排序需要交换栈元素，我们还要记录每个站原来的编号是哪个！

实现后，可以简单判断一下x是否都为0，或者提交到OJ、用SPJ检验。