当前位置: 首页 > news >正文

LGP8866 [NOIP 2022] 喵了个喵 学习笔记

LGP8866 [NOIP 2022] 喵了个喵 学习笔记

\(\texttt{Luogu Link}\)

前言

史。无需多言。

本笔记也许参考了这篇题解。对于一道构造题来说,此解析写的确实认真负责,配最高赞。

题意简述

\(\texttt{E}\) 喜欢上了一款叫做《喵了个喵》的游戏。

:小 \(\texttt{E}\) 能别整些有的没的了吗。

:别急,小 \(\texttt{E}\) 的整活(人)巅峰还在 \(\texttt{NOIP 2022}\) 半年之后的省选。

这个游戏有一个初始 \(m\) 张牌的牌堆和 \(n\) 个可以从栈底删除元素的初始为空的栈(即双端队列)。卡牌有 \(k\) 种图案(颜色),牌堆里每种图案的卡都有偶数张。这个游戏有两种操作:

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

牌堆内的每一张卡牌都是已知的。对于此游戏给出一个合法操作序列可以消去所有卡牌。

多测。\(\sum m\le 2\times 10^6\)\(n\le 300\)

特别地,\(15\text{pts}\) 的数据满足 \(k=2n-2\),其余 \(85\text{pts}\) 的数据满足 \(k=2n-1\)

做法解析

显然由部分分可得,我们先思考 \(k=2n-2\) 的情形。

\(2n-2\) 这个数字给的就很好。它意味着我们如果给每两个颜色都分配一个栈去处理,最后就刚好还有一个空栈。再考虑到一个栈里能把牌消掉的方式也是刚好两种,操作方案就呼之欲出了:我们把 \(i\)\(i+n-1\) 分配到 \(i\) 号栈。具体来说,对于每次从牌堆顶拿的卡牌,若其分配的栈中不存在和它相同的卡牌,则直接放进去;否则若有和它相同的卡牌在堆底,则将它自身放进空栈并执行栈底消除;否则若有和它相同的卡牌在栈顶,则将它直接放上去执行栈顶消除。所以 \(15\text{pts}\) 是很简单的。

思考 \(k=2n-1\)。此时和 \(k=2n-2\) 的区别在于不一定永远存在一个空栈了,当然我们仍然尝试在大多数时候保持 \(k=2n−2\) 做法的特性,即 \(n−1\) 个栈仅保存两种元素并且剩余一个栈为空,可以吗?

当整个局面已经存在了 \(2n-2\) 个元素,且出现了第 \(2n-1\) 号颜色,我们要把它放哪儿呢?你发现有些情况我们直接把它放辅助栈即可,有时候我们得把它放到某个栈顶以便后续有栈底消执行。也就是说,后面的颜色会影响我们当前对 \(2n-1\) 号颜色的决策,我们得开个辉眼。

一时兴起了。

当然,只要局面上只有不大于 \(2n-2\) 种颜色需要考虑,我们就可以沿用 \(k=2n-2\) 的策略。而当出现了第 \(2n-1\) 种颜色(不一定是编号上的 \(2n-1\),而是指场面上同时集齐了 \(2n-1\) 种颜色)的一个元素 \(a_l=u\) 时,我们就要看看之后出现的颜色。

首先,我们找到 \(l\) 后第一个满足 \(c_r\) 颜色不在栈顶的元素(显然 \((l,r)\) 中的元素因为有现在栈顶的元素和它同色,所以基本上可以简单消除)。若 \(c_r=c_l=u\),则我们直接把 \(c_l\)\(c_r\) 都扔辅助栈即可。否则 \(c_r=v\neq u\),就意味着我们要消掉某个栈 \(s\) 当前栈底的元素。记当前待在 \(s\) 栈顶的元素为 \(a\),则我们又要根据 \(a\)\((l,r)\) 中出现次数的奇偶性做个分讨(此时 \((l,r)\)\(a\) 不能走简单消)。

此处 \((l,r)\) 即为 \([l+1,r-1]\) 的意思。

如果出现奇数次,说明带上局面中本来就有的 \(a\) 就是偶数个了,可以两两消除,这意味着到了 \(r\)\(a\) 可以被消干净了,我们把 \(c_r\)\(s\) 一扔,就和原本处于栈底的 \(v\) 消掉了,此时 \(s\) 就空出来了,我们又有了一个空栈可作辅助栈,于是就可以放心把 \(c_l=u\) 扔到当前辅助栈里。

如果出现偶数次,说明后来的 \(a\) 可以两两消除,而局面上这个 \(a\) 仍然存在,我们必须走栈底消 \(v\)。于是,我们把 \(c_l=u\) 扔到 \(s\) 上,\((l,r)\) 中那偶数次出现的 \(a\) 扔到辅助栈里。这样考虑 \(c_r\) 时辅助栈仍然是空的,我们把 \(c_r\) 扔进去并栈底消除,之后辅助栈还是空的并且 \(s\) 中的元素数量也回到了两个,保持了可维护的状态。

代码实现

对于 \(k\le 2n-2\) 的局面,我们做简单的处理 regu。用队列存放当前有位置增添颜色的栈,用双端队列模拟栈的真实情况,用数组 id 记录每种颜色存在于哪个栈中。

后面 \(k=2n-1\) 的策略是好写的。

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=3e2+5,MaxM=2e6+5;
int N,M,K,C[MaxM],id[MaxN<<1],ex;
vector<pii> ans;
void apu(int s){ans.push_back({s,0});}
void abo(int s,int t){ans.push_back({s,t});}
queue<int> q;deque<int> stk[MaxN];
bool regu(int u){int s=id[u];if(!s){if(q.empty())return false;id[u]=s=q.front(),q.pop();apu(s),stk[s].push_back(u);}else{id[u]=0;q.push(s);if(u==stk[s].back())apu(s),stk[s].pop_back();else apu(ex),abo(ex,s),stk[s].pop_front();}return true;
}
void befinit(int n){ans.clear();fill(id,id+n*2+1,0);ex=n;while(!q.empty())q.pop();for(int i=1;i<N;i++)q.push(i),q.push(i);
}
void mian(){readis(N,M,K);befinit(N);for(int i=1;i<=M;i++)readi(C[i]);for(int l=1,r,u,v;l<=M;l=r+1){r=l,u=C[l];if(regu(u))continue;do{r++,v=C[r];}while(r<=M&&v!=u&&stk[id[v]].back()==v);if(u==v){apu(ex);for(int i=l+1;i<r;regu(C[i]),i++);apu(ex);continue;}int s=id[v],a=stk[s].back(),kk=0;for(int i=l+1;i<r;i++)kk^=(C[i]==a);if(kk){apu(ex),stk[ex].push_back(u);for(int i=l+1;i<r;i++){if(C[i]==a)apu(s);else regu(C[i]);}apu(s),stk[s].clear();id[a]=id[v]=0,id[u]=ex,q.push(ex),ex=s;}else{apu(s),stk[s].push_back(u);for(int i=l+1;i<r;i++){if(C[i]==a)apu(ex);else regu(C[i]);}apu(ex),abo(ex,s),stk[s].pop_front();id[v]=0,id[u]=s;}}writil(ans.size());for(auto [x,y] : ans){if(y)printf("2 %d %d\n",x,y);else printf("1 %d\n",x);}
}
int Tcn;
int main(){readi(Tcn);while(Tcn--)mian();return 0;
}
http://www.hskmm.com/?act=detail&tid=30647

相关文章:

  • edge每次打开不是用自己的账户,还要选择一次
  • LibreOffice Impress播放不出视频的解决方法
  • VMware ESXi 9.0.1.0 macOS Unlocker OEM BIOS 2.7 Inspur 浪潮 定制版
  • Exchange 异常关机后无法登录owa/ecp 以及ems无法连接远程服务器
  • 【GitHub每日速递 251014】Claude Code:用自然语言命令让编码快到飞起!
  • 新项目完结,Ai Agent 智能体、拖拉拽编排!
  • 硅谷大佬揭秘创业者成功法则
  • 2025年南通宠物医院最新权威推荐榜:专业诊疗与暖心服务口碑之选
  • 2025年10月学校家具定制厂家最新推荐排行榜,课桌椅,宿舍床,图书馆家具,教室家具公司推荐!
  • 2025年10月螺杆泵厂家最新推荐排行榜,单螺杆泵,双螺杆泵,三螺杆泵,高效耐用品质之选!
  • 2025年恒温恒湿系统厂家最新推荐榜单,精加工车间/厂房/美术馆/仓库/计算机房/档案室/工业/工厂车间恒温恒湿系统公司推荐
  • 2025年会议系统厂家最新推荐排行榜,专业音视频会议系统,智能会议解决方案,高清视频会议系统公司推荐!
  • RSA密钥生成基准测试深度解析
  • MaxKB 在不同场景下 RAG 引擎与向量存储的应用案例分析
  • C#数组
  • 251013
  • 简谈误差与不确定度
  • 可怕!我的Nodejs系统因为日志打印了Error 对象就崩溃了 Node.js System Crashed Because of Logging an Error
  • 前言
  • 实践
  • 数据结构字符串和图
  • 字典dict
  • 结婚证识别技术:融合计算机视觉、深度学习与自然语言处理的综合性AI能力的体现
  • 上下文丢失
  • 数据结构序列
  • 上下文学习(In-context Learning, ICL)
  • 混淆矩阵
  • 提示词工程实践指南:从调参到对话的范式转变
  • Multi-Head Attention机制
  • 泛化能力