当前位置:首页 > 数学 > 构造 > 正文
洛谷P8866喵了个喵(NOIP2022)
174+

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

题目描述

小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈,任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌,从上到下的图案分别是 $a_1, a_2,\dots, a_m$。所有的卡牌一共有 $k$ 种图案,从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作:

– 选择一个栈,将牌堆顶上的卡牌放入栈的顶部。如果这么操作后,这个栈最上方的两张牌有相同的图案,则会自动将这两张牌消去。
– 选择两个不同的栈,如果这两个栈栈**底**的卡牌有相同的图案,则可以将这两张牌消去,原来在栈底上方的卡牌会成为新的栈底。如果不同,则什么也不会做。

这个游戏一共有 $T$ 关,小 E 一直无法通关。请你帮小 E 设计一下游戏方案,即对于游戏的每一关,给出相应的操作序列使得小 E 可以把所有的卡牌消去。

输入输出格式

输入格式

第一行包含一个正整数 $T$,表示数据组数。

接下来一共 $T$ 组数据,在每组数据中:

第一行包含三个正整数 $n, m, k$,分别表示栈的个数、卡牌的个数、卡牌上图案的种类。

第二行包含 $m$ 个正整数,分别表示 $a_1, a_2,\dots, a_m$,分别从上到下表示牌堆中卡牌的图案。

输入数据保证有解。

输出格式

对于每一组数据,输出若干行。

其中第一行包含一个正整数 $\mathrm{op}$,表示操作的次数。你需要保证 $m \leq \mathrm{op} \leq 2\times m$。

接下来 $\mathrm{op}$ 行,每行包含两个或三个正整数,整数之间用一个空格隔开。

若为两个整数 $\texttt{1 s}$,则进行一次第一个操作并选择栈 $s$。

若为三个整数 $\texttt{2 s1 s2}$,则进行一次第二个操作并选择栈 $s_1$ 和 $s_2$。

你需要保证 $1 \leq s, s_1, s_2 \leq n$,且 $s_1 \neq s_2$。

输入输出样例

输入样例 #1

1
2 4 2
1 2 1 2

输出样例 #1

5
1 1
1 1
1 2
2 1 2
1 1

说明

**【样例 1 解释】**

下图是初始状态:自行理解!!!

**【样例 2】**

见选手目录下的 $\texttt{meow/meow2.in}$ 与 $\texttt{meow/meow2.ans}$。

**【数据范围】**

设 $S$ 为所有 $T$ 组数据中 $m$ 的总和。

对于所有数据,保证 $S \leq 2 \times 10^6$,$1 \leq n \leq 300$,$1 \leq a_i \leq k$。

| 测试点 | $T=$ | $n$ | $k=$ | $m \leq$ |
| :———-: | :———-: | :———-: | :———-: | :———-: |
| $1\sim 3$ | $1001$ | $\leq 300$ | $2n-2$ | 无限制 |
| $4\sim 6$ | $1002$ | $=2$ | $2n-1$ | 无限制 |
| $7\sim 10$ | $3$ | $=3$ | $2n-1$ | $14$ |
| $11\sim 14$ | $1004$ | $=3$ | $2n-1$ | 无限制 |
| $15\sim 20$ | $1005$ | $\leq 300$ | $2n-1$ | 无限制 |

**【评分方式】**

对于每一组数据,若在按顺序进行所有操作后,牌堆为空且所有的栈均为空,则认为你的答案正确。

**【提示】**

你可以通过 $T$ 的个位数来判断这个测试点是属于哪一类数据。

你的输出不需要与样例输出一致,输出任意一个合法解即可得分。

解题思路

对于元素种类为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个元素,放到前面。这样基本能保证第二个栈有空位,如果没有空位,那就要考虑是否动用空栈了。

注意:栈排序不仅需要交换栈元素,还要记录每个栈原来的编号是哪个!

(感谢qzm123提供思路)

报歉!评论已关闭.