首页 > 其他分享 >喵了个喵 题解

喵了个喵 题解

时间:2024-03-02 17:02:15浏览次数:20  
标签:牌堆 放到 题解 sp 张牌 栈底 消除

传送门

这玩意是 T2 ???

观察到 \(k=2n-2\) 或 \(k=2n-1\),所以我们可以尝试让每个栈里面都保持两张牌。同时保留一个空栈,用来消栈底。 记这个保留的空栈为 \(sp\)。

策略 1:

  1. 如果当前牌堆顶的牌能消,必然消;

  2. 否则除了 \(sp\),如果存在一个没有填到两张牌的栈,放进去。

当 \(k=2n-1\),可能策略1不适用:当前除了 \(sp\) 都填了 \(2\) 张牌,且牌堆顶的牌在当前所有栈中都没有出现。

我们找到当前牌堆中第一张出现在栈底的牌。 这张牌我们希望它放到 \(sp\) 号栈用操作二消除。但是当前牌堆顶可能要占用 \(sp\) 号栈,怎么办?

假设第一张出现在栈底的牌位置是 \(x\),\(x\) 对应的栈靠上的牌是 \(y\)。我们检查牌堆顶到 \(x\) 中间 \(y\) 出现了多少次:

  1. 如果是奇数次,说明可以把 \(y\) 消掉。那我们把牌堆顶放到 \(sp\) 号栈上。

    因为 \(x\) 是第一张栈底牌,所以牌堆顶到 \(x\) 中间的牌都可以放到某个栈的栈顶消除。

    于是我们把牌堆顶放到 \(sp\),把中间的牌放到栈顶消除,\(y\) 都放到 \(x\) 的栈上面,然后把 \(x\) 放到 \(x\) 的栈上——此时 \(y\) 已经消干净了。此时 \(x\) 所在的栈已经空了,我们把 \(sp\) 号栈改为这个栈即可。

  2. 如果是偶数次,把牌堆顶放到 \(x\) 所在栈上面(此时 \(y\) 被夹在中间),然后中间的除了 \(y\) 的牌都放到对应栈顶消除,\(y\) 都放到 \(sp\) 号栈消除(\(y\) 偶数次)。

    然后把 \(x\) 放到 \(sp\) 号栈和 \(x\) 原来的栈底消除,此时 \(x\) 原来所在的栈就剩下原来牌堆顶和 \(y\) 了。依然满足每个栈只有 \(\le 2\) 张牌。

标签:牌堆,放到,题解,sp,张牌,栈底,消除
From: https://www.cnblogs.com/FLY-lai/p/18048857

相关文章

  • CF1915D Unnatural Language Processing 题解
    容易发现音节的划分不仅要求子串形如\(\texttt{CV}\)或\(\texttt{CVC}\),并且接下来的两个字符也必须是\(\texttt{CV}\),不然会导致无法划分下去。于是我们遍历字符串,找出所有满足上述条件的子串,记录需要输出\(\texttt{.}\)的位置即可。实现:intn;strings,ans,t="";cin>......
  • CF1915E Romantic Glasses 题解
    我们考虑维护\(sum_i\)表示前\(i\)个数中偶数下标的数之和与奇数下标的数之和之差,其中\(sum_0=0\)。若在某一时刻,有\(sum_i=sum_j(j<i)\),说明\(j\simi\)中偶数下标的数之和与奇数下标的数之和之差为\(0\)。这个使用map判断即可。实现:intn,f=0;cin>>n;m.clear()......
  • CF1921D Very Different Array 题解
    补充一个对本题贪心思路更(?)清楚的解释。本题贪心思路:在\(a_i,b_i\)分别升序的情况下,对于每个\(a_i\),与它差值最大的\(b_i\)只可能出现在\(b_{n-i+1}\)与\(b_{m-i+1}\)这两者中。证明:首先,假设我们有一个长度为\(n\)的升序序列\(s\)。则对于\(s_1\),与它差值最大......
  • CF10E 题解
    传送门有\(n\)种货币。找一个最小的金额\(x\),使得贪心法付款不是最优解;如果贪心法始终都是最优解,输出\(-1\)。\((n\le400)\)将货币集合记作一个\(n\)维向量\(C=(c_1,c_2,\dots,c_n)\)。对于金额\(x\)的一个表示法,也记作一个\(n\)维向量\(V\)。即\(C\timesV=x\)。......
  • NOIP2023 T4 题解
    T4写出转移方程:\(f_i\)表示前\(i\)天且第\(i\)天必须跑的最大能量值。\(g_i=\max\limits_{j=1}^i\{f_j\}\)。初值\(f_0=g_0=0\)。对于转移方程,考虑枚举最后一段跑的段是从哪里开始的:\(f_i=\displaystyle\max_{j=i-k+1}^i(g_{j-2}+prize(j,i)-(j-i+1)\timesd)\)。其中\(p......
  • SP14846 GCJ1C09C - Bribe the Prisoners 题解
    非常好区间dp。我们发现直接依题做是困难的,因此考虑反着做。也即,假定起初那\(Q\)个牢房均为空,现在要将给定的\(Q\)的犯人插入其中,求最小代价。然后我们发现这题和P1775很像,相当于每插入一个人,两段不相邻的牢房就被合并到了一起。接着我们就考虑这玩意怎么做区间dp。......
  • 【题解】「HDU 7084」Pty loves string
    CQBZOJHDU7084不难想到把最终在\(S\)从中间分开,就变成了前后两个broder拼起来。考场重现:直接把所有的broder求出来,将相同长度的broder的下标存在一起,然后暴力匹配,最后还没来及优化。考场代码(除了fail树,其她其实都挺逼近正解正解是建出fail树(甚至搞忘还有这东......
  • 2023互联网笔试记录汇总(61道真题+题解)
    以下编程题均为博主在2023年投递实习和秋招过程中的笔试真题(共61道编程题),为避免不必要的麻烦,不对题目的来源进行说明。3.4第一题题意:给一个数组(n≤2e5),求数组内任意数对的最大差值。即对任意i<j,求最大的x[j]-x[i]。题解:处理一下前缀最小值。第二题题意:给一个数组(n≤2e5......
  • 信息传递(题解)[并查集]
    题目题目描述有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有......
  • P10187 [USACO24FEB] Palindrome Game B 题解
    挑战题解区最短代码回文数?数学题!打表找规律吧……显然,\(1\sim9\)都是回文数,先手赢(就一位你还想咋地啊)。然后是\(10\)。样例告诉我们,这个不行。接着是\(11\sim19\),发现随便减个\(1\sim9\)就可以变成\(10\),而\(10\)是后手赢。赢得就是后手的后手,那就是先手,可以。......