←
如果对你有帮助的话点个赞呗 QwQ
↖
求求了真的写了很久,赞是免费的 QwQ
喵了个喵题解 [NOIP2022]
题目描述
小 E 喜欢上了一款叫做《喵了个喵》的游戏。
这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈,任务是要通过游戏规则将所有的卡牌消去。
开始时牌堆中有 $m$ 张卡牌,从上到下的图案分别是 $a_1, a_2, · · · , a_m$。
所有的卡牌一共有 $k$ 种图案,从 $1$ 到 $k$ 编号。
牌堆中每一种图案的卡牌都有偶数张。
开始时所有的栈都是空的。
这个游戏有两种操作:
- 选择一个栈,将牌堆顶上的卡牌放入栈的顶部。如果这么操作后,这个栈最上方的两张牌有相同的图案,则会自动将这两张牌消去。
- 选择两个不同的栈,如果这两个栈栈底的卡牌有相同的图案,则可以将这两张牌消去,原来在栈底上方的卡牌会成为新的栈底。否则,则什么也不会做。
这个游戏一共有 $T$ 关,小 E 一直无法通关。
请你帮小 E 设计一下游戏方案,即对于游戏的每一关,给出相应的操作序列使得小 E 可以把所有的卡牌消去。
输入格式
第一行包含一个正整数 $T$,表示数据组数。
接下来一共 $T$ 组数据,在每组数据中:
第一行包含三个正整数 $n, m, k$,分别表示栈的个数、卡牌的个数、卡牌上图案的种类。
第二行包含 $m$ 个正整数,分别表示 $a_1, a_2, · · · , a_m$,分别从上到下表示牌堆中卡牌的图案。
输入数据保证有解。
输出格式
对于每一组数据,输出若干行。
其中第一行包含一个正整数 $op$,表示操作的次数。你需要保证 $m ≤ op ≤ 2 × m$。
接下来 $op$ 行,每行包含两个或三个正整数,整数之间用一个空格隔开。
若为两个整数 1 s
,则进行一次第一个操作并选择栈 $s$。
若为三个整数 2 s1 s2
,则进行一次第二个操作并选择栈 $s_1$ 和 $s_2$。
你需要保证 $1 ≤ s, s_1, s_2 ≤ n$,且 $s_1 \neq s_2$。
你的输出不需要与样例输出一致,输出任意一个合法解即可得分。
数据范围
设 $S$ 为所有 $T$ 组数据中 $m$ 的总和。
对于所有数据,保证 $S ≤ 2 × 10^6$,$1 ≤ n ≤ 300$,$1 ≤ a_i ≤ k$。
输入样例:
1
2 4 2
1 2 1 2
输出样例:
5
1 1
1 1
1 2
2 1 2
1 1
样例解释
下图是初始状态。
下图是前两次操作之后的结果。
下图是第三次和第四次操作之后的结果。
下图是第五次操作之后的结果。
题意
(= ̄ω ̄=)喵了个咪
初始给定 $n$ 个空栈,每个栈记作 $p_1,p_2,…,p_n$。
一个牌堆,可以将其看做一个长度为 $m$ 的数组,数组中的元素为 $a_1,a_2,…,a_m$,且 $1 ≤ a_i ≤ k$。
对于每一次操作:
- 取 $a_i$ 放入任意 $p_j(1 ≤ j ≤ n)$ 顶部。记该操作为操作 $1$。
- 如果这么操作后,$p_j$ 最上方的两个元素的值相同,则会自动将这两个元素消去。
- 该操作在进行操作 $1$ 后将自动判断并操作。
- 如果操作 $1$ 进行后,可以找到两个不同的栈 $p_k$ 和 $p_l$,如果 $p_k$ 和 $p_l$ 栈底的元素相同,则可以将这两个元素消去,原来在栈底上方的元素会成为新的栈底。如果不同,则什么也不会做。
- 记该操作为操作 $2$。
- 如果这么操作后,$p_j$ 最上方的两个元素的值相同,则会自动将这两个元素消去。
要求输出一种具体的操作方案使得在数组清空后每个栈仍然是空的。
输入数据保证有解。
(思维+模拟) $O(m)$
首先观察数据范围,发现卡牌种类数 $k\in\lbrace2n−2,2n−1\rbrace$,说明 $k$ 与栈数量 $n$ 之间有种神秘的关系。
先看 $k=2n-2$ 时的情形,发现 $2n-2=2(n-1)$,即每个栈分配两个不同的数,仍能留下一个空栈,把这个空栈记为 $sp$。
我们还注意到如果多于两个牌存在于一个栈中,中间的元素会比较尴尬,不好消掉,经常会造成无解情况。
于是有一种思路便呼之欲出了:
每次从牌堆处理一张牌时,如果这张牌的图案在某个栈的顶部出现,那么对该栈进行操作 $1$ 并消掉两张牌;
如果这张牌的图案在某个栈 $p_i$ 的底部出现,那么对 $sp$ 栈进行操作 $1$,再对 $p_i$ 和 $sp$ 进行操作 $2$,消掉两张牌;
否则对任意一个非 $sp$ 的栈进行操作 $1$ 即可。
由于只有 $2n-2$ 种图案,这样的方法可以保证得出结果。可以骗到前 $15$ 分
15 pts代码在后面。
再看 $k=2n-1$ 时的情形,这时上面的策略就不好用了,因为无法保证让 $sp$ 一直为空且让所有其他栈内不超过三张牌。
这里我会给出一个样例来总结可能出现的各种情况。
1
4 32 7
1 2 3 4 5 6 7 7 7 5 5 4 7 4 7 1 1 5 4 5 3 4 3 7 5 7 6 2 3 1 7 4
初始状态:
用之前的操作进行到下图状况,牌堆顶新出来一个 7,这时除了 $sp$ 栈其他的栈都被填满了:
我们发现下一个正好是 7,把他们都放入 $sp$ 里消掉:
可是不是每次都有这样的运气,下一个如果和牌堆顶的牌不一样怎么办?
如果下一张牌的同类牌出现在栈底(设对应栈编号为 $P$),那么可以将牌堆顶的牌放到栈 $P$ 上,然后将下一张牌放到栈 $sp$ 里,最后对栈 $P$ 和 $sp$ 执行一次操作 $2$ 就行。
如果下一张牌的同类牌出现在栈顶就不太好办了,这时候改把牌堆顶的牌放在哪呢?好像哪里都不妥。
我们可以往后看有没有位于底部的牌(设对应栈编号为 $P$),然后将牌堆顶的牌放到对应栈顶试试。
操作非常顺利!
我们再试一次:
还是有点问题。牌堆顶的牌挡住了原栈顶的牌,后面出现的和原栈顶的牌相同的牌不能消除。
不过如果把牌堆顶放入 $sp$,反而能把 $P$ 清空,让 $P$ 成为新的 $sp$:
这两种情况的区别是什么?
前一种情况里 $P$ 的栈顶牌没有被消去,后一种情况里被消去了。
那到底什么时候 $P$ 的栈顶牌会被消去呢?
如果牌堆顶的牌和其后第一张位于栈底的牌(设对应栈编号为 $P$)之间,与 $P$ 的栈顶牌同类的牌出现了奇数次,那么 $P$ 的栈顶牌会被消去,否则则不会。
知道了这一点,剩下的部分就简单啦~
剩下这些肯定都会做了哈
完结散花~~
$$\Large{总结}$$
任意时刻,设牌堆顶的牌为 $u$。保留一个栈为空,记其为 $sp$。
策略 1:
条件:存在 $sp$,且 $u$ 的同类牌在场上存在 或 非 $sp$ 栈中存在至少一个栈大小不超过 $1$
- 除了 $sp$ 外,其他的栈都至多放 $2$ 个元素。每次处理一张牌时,如果 $u$ 在某个栈 $P$ 的顶部出现过,那么把 $u$ 放入 $P$;如果 $u$ 在某个栈 $P$ 的底部出现过,那么把 $u$ 放入 $sp$,对 $P$ 和 $sp$ 进行操作 $2$;否则把 $u$ 放入某个未满的非 $sp$ 栈里。
策略 2:
条件:存在 $sp$,且 $u$ 的同类牌在场上不存在 且 非 $sp$ 栈中没有栈大小不超过 $1$
- 记当前所有在栈顶的 $n-1$ 个元素构成集合 $S$。我们不断扫描之后的图案,直到遇到第一个不在 $S$ 中的图案为止。
- 如果这个图案就是 $u$:把牌堆顶的 $u$ 和现在的 $u$ 都放入 $sp$,消掉它们。因为中间的所有元素都是栈顶,可以直接放入和它们对应的栈上。
- 如果这个图案不是 $u$:那么这个图案 $v$ 是某个栈 $P$ 的栈底。记 $P$ 的栈顶为 $w$,讨论 $w$ 在刚刚扫描过的所有图案中出现次数的奇偶性:
- 奇数次:把 $u$ 放入 $sp$,所有的 $w$ 放入 $P$。这样 $v$ 再次出现的时候,$P$ 上面的 $w$ 被清空了,此时可以直接把 $v$ 消掉,$P$ 变成新的 $sp$。
- 这个过程中,其他栈顶元素放入对应栈顶即可。
- 偶数次:把 $u$ 放入 $P$,所有的 $w$ 放入 $sp$(这里放到 $P$ 里也行)。这样 $v$ 再次出现的时候,$P$ 中自顶到底分别是 $u,w,v$ 三个元素。把 $v$ 放入 $sp$,再消掉 $P$ 和 $sp$ 的栈底,这样 $P$ 中仍然只有两个元素。
- 这个过程中,其他栈顶元素放入对应栈顶即可。
- 奇数次:把 $u$ 放入 $sp$,所有的 $w$ 放入 $P$。这样 $v$ 再次出现的时候,$P$ 上面的 $w$ 被清空了,此时可以直接把 $v$ 消掉,$P$ 变成新的 $sp$。
嗯?有操作次数的限制?($m ≤ op ≤ 2 × m$)其实这个限制根本不用管,因为操作 $1$ 只会 $m$ 次,而操作 $2$ 的有效操作最多 $\frac{m}{2}$ 次。
时间复杂度
如果维护的信息恰当,每个元素只需要检查一次,单个数据组复杂度为 $O(m)$。
设 $S$ 为所有 $T$ 组数据中 $m$ 的总和,总时间复杂度为 $O(S)$。
因为题目保证 $S ≤ 2 × 10^6$,时间完全够用。
空间复杂度
有点玄学,不过维护的各种信息占用的空间很小,差不多 $O(m)$。
(够用就行了)
无注释 15pts C++ 代码(想要注释可以看满分代码里的注释)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
inline int read(){
int x = 0;
bool f = true;
char ch = getchar();
for(; !isdigit(ch); ch = getchar())
if(ch == '-')
f = false;
for(; isdigit(ch); ch = getchar())
x = (x << 1) + (x << 3) + ch - '0';
return f ? x : (~(x - 1));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N];
int id[K];
int spt;
queue<int> q;
vector<PII> ans;
inline void oper_1(int s, int x){
if(!st[s].empty() && st[s].back() == x) st[s].pop_back();
else st[s].push_back(x);
ans.emplace_back(s, -1);
}
inline void oper_2(int s1, int s2){
st[s1].pop_front();
st[s2].pop_front();
ans.emplace_back(s1, s2);
}
inline void simple(int x){
int &s = id[x];
if(!s){
if(q.empty()){
printf("完蛋了只能搞15pts了QwQ");
exit(0);
}
s = q.front(); q.pop();
oper_1(s, x);
}else{
q.push(s);
if(x == st[s].back()){
oper_1(s, x);
}else{
oper_1(spt, x);
oper_2(spt, s);
}
s = 0;
}
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
spt = n;
while(!q.empty()) q.pop();
for(int i = 1; i < n; i++){
q.push(i);
q.push(i);
}
for(int i = 1; i <= m; i++)
simple(a[i]);
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
带注释满分 C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
inline int read(){ // 快读,能提升 1300 多 ms
int x = 0;
bool f = true;
char ch = getchar();
for(; !isdigit(ch); ch = getchar())
if(ch == '-')
f = false;
for(; isdigit(ch); ch = getchar())
x = (x << 1) + (x << 3) + ch - '0';
return f ? x : (~(x - 1));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N]; // 维护每个栈的栈底和栈顶的元素
int id[K]; // 维护所在栈的编号,若局面未出现则为 0
int spt; // 辅助栈的编号
queue<int> q; // 用于维护哪些栈可以弹入元素。初始时除了辅助栈,每个栈可以弹入 2 次
vector<PII> ans; // 保存答案
inline void oper_1(int s, int x){ // 操作 1,向 s 中插入 x
if(!st[s].empty() && st[s].back() == x)
st[s].pop_back(); // 若顶部两个元素相同则弹出
else st[s].push_back(x); // 否则弹入
ans.emplace_back(s, -1); // 添加入答案
}
inline void oper_2(int s1, int s2){ // 操作 2,消除 s1 和 s2 的栈底
st[s1].pop_front(); // 弹出栈底
st[s2].pop_front(); // 弹出栈底
ans.emplace_back(s1, s2); // 添加入答案
}
inline bool simple(int x){ // 新出来一个数 x,尝试简单相消
int &s = id[x];
if(!s){ // 若 x 未出现过
if(q.empty()) return false; // 没有可弹入的栈,return false
s = q.front(); q.pop();
oper_1(s, x); // 否则弹入下一个可弹入的栈
}else{
q.push(s); // 若 x 出现过,一定能够消除,把原先 x 所在的位置弹入 q
if(x == st[s].back()){ // 在栈顶
oper_1(s, x);
}else{ // 在栈底
oper_1(spt, x);
oper_2(spt, s);
}
s = 0; // 然后改为局面未出现
}
return true;
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
spt = n;
while(!q.empty()) q.pop();
for(int i = 1; i < n; i++){
q.push(i);
q.push(i);
}
// 初始化
for(int i = 1; i <= m; i++) if(!simple(a[i])){ // 如果尝试简单相消行不通
int u = a[i]; // 记录当前数值
int r = i + 1, v = a[r];
while(r <= m && v != u && st[id[v]].back() == v)
v = a[++r]; // 寻找下一个不在栈顶的数
// 此时,r 是 i 后第一个不在栈顶的下标,v 是 a[r]
if(v == u){ // 如果 v 正好和 u 一样
oper_1(spt, u);
for(int j = i + 1; j < r; j++)
simple(a[j]);
oper_1(spt, v); // 把他们在辅助栈消除
}else{ // 否则 v 是某个栈 P 的栈底
int p = id[v], w = st[p].back(); // 记 P 的栈顶为 w
bool is_even = true; // 查看 w 出现次数奇偶性
for(int j = i + 1; j < r; j++)
if(a[j] == w)
is_even = !is_even;
if(is_even){ // w 出现次数为偶数
oper_1(p, u); // u 放入 P
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(spt, w); // 这里 w 进 P 和 sp 都行
else simple(a[j]); // 注意这里用 simple 而不是
// oper_1,因为要自动更新 q
}
oper_1(spt, v);
oper_2(spt, p); // 消除两个栈底的 v
id[v] = 0;
id[u] = p;
}else{ // w 出现次数为奇数
oper_1(spt, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(p, w); // 这里注意:
// 不能直接 simple,
// 因为 P 即将变成 sp,
// 所以暂时不能让 P 弹入 q
else simple(a[j]);
}
oper_1(p, v);
id[v] = id[w] = 0; // P 原先元素为 v,w,现在清空
id[u] = spt; // 原先 sp 此时存在一个元素 u
q.push(spt); // 更新 q
spt = p; // P 成为新的 sp
}
}
i = r;
}
// 简单输出
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
无注释满分 C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
inline int read(){
int x = 0;
bool f = true;
char ch = getchar();
for(; !isdigit(ch); ch = getchar())
if(ch == '-')
f = false;
for(; isdigit(ch); ch = getchar())
x = (x << 1) + (x << 3) + ch - '0';
return f ? x : (~(x - 1));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N];
int id[K];
int spt;
queue<int> q;
vector<PII> ans;
inline void oper_1(int s, int x){
if(!st[s].empty() && st[s].back() == x) st[s].pop_back();
else st[s].push_back(x);
ans.emplace_back(s, -1);
}
inline void oper_2(int s1, int s2){
st[s1].pop_front();
st[s2].pop_front();
ans.emplace_back(s1, s2);
}
inline bool simple(int x){
int &s = id[x];
if(!s){
if(q.empty()) return false;
s = q.front(); q.pop();
oper_1(s, x);
}else{
q.push(s);
if(x == st[s].back()){
oper_1(s, x);
}else{
oper_1(spt, x);
oper_2(spt, s);
}
s = 0;
}
return true;
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
spt = n;
while(!q.empty()) q.pop();
for(int i = 1; i < n; i++){
q.push(i);
q.push(i);
}
for(int i = 1; i <= m; i++) if(!simple(a[i])){
int u = a[i];
int r = i + 1, v = a[r];
while(r <= m && v != u && st[id[v]].back() == v)
v = a[++r];
if(v == u){
oper_1(spt, u);
for(int j = i + 1; j < r; j++)
simple(a[j]);
oper_1(spt, v);
}else{
int p = id[v], w = st[p].back();
bool is_even = true;
for(int j = i + 1; j < r; j++)
if(a[j] == w)
is_even = !is_even;
if(is_even){
oper_1(p, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(spt, w);
else simple(a[j]);
}
oper_1(spt, v);
oper_2(spt, p);
id[v] = 0;
id[u] = p;
}else{
oper_1(spt, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(p, w);
else simple(a[j]);
}
oper_1(p, v);
id[v] = id[w] = 0;
id[u] = spt;
q.push(spt);
spt = p;
}
}
i = r;
}
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
备注
求求啦给个赞和关注吧 QwQQQQQ
这题真的耗肝啊
写题解更耗肝啊啊啊
总共 $630$ 行,写了好几天
# sto大佬orz
QwQ谢谢