P8866 [NOIP2022] 喵了个喵

发布时间 2023-09-06 08:06:20作者: FOX_konata

原题

看了三遍忘了三遍,后来决定写博客

首先看\(k=2n-2\)的情况,显然我们只需要空出一个栈,如果牌堆里的牌在栈顶出现过,则直接消去;如果牌堆里的牌在栈底出现,则我们把牌放到空栈中后再消去即可


然后我们考虑\(k=2n-1\)的情况,我们考虑一直延续\(k=2n-2\)的思路,即尽量让栈保持\(n-1\)个满的状态

  1. 如果牌堆中的数已经出现过,我们直接把他消掉

  2. 否则找到后面第一个\(a_i\)为堆底的位置,如果\(a_i\)所在的堆的堆顶在牌堆顶到\(a_i\)出现了奇数次,则这个数可以直接被消掉,我们把牌堆顶的牌放到空栈里;否则\(a_i\)所在堆的堆顶不能被消去,但偶数个会互相抵消,而且把\(a_i\)放到空栈里\(a_i\)会被消去,我们把牌堆顶的牌放到\(a_i\)所在堆堆顶即可

\[\large{\color{#ff0000}{\text{被cm+搏杀了,已经可以AFO了}}} $$7\]