首页 > 其他分享 >CF1923D. Slimes

CF1923D. Slimes

时间:2024-03-16 11:33:43浏览次数:29  
标签:前缀 CF1923D 后缀 Slimes lst cases

Problem - 1923D - Codeforces

  • 现在怎么菜成这样了aaaaaaa

  • 我们考虑枚举 \(i\),则到底是谁吃掉了 \(i\) 不重要 (我思考的时候就因为这个没有想到正解)

  • \(i\) 的后缀反着跑一边即可,因此只考虑 \(i\) 前缀把他吃掉的情况

  • 发现就是找一段最短的前缀的后缀和使区间里的和 \(> a_i\)

  • 但写完后会发现样例 \(3\) 过不去,因为如果区间中全是重复是不可行的

  • 并不需要 \(st\) 表求区间最值判断相等,只需要记录数组 \(lst_i\) 表示上一个与 \(a_i\) 不同的位置

  • \[\begin{cases} lst_i = lst_{i-1} & if & a_i = a_{i-1} \\ lst_i = i - 1 & elsewise \end{cases} \]

  • 复杂度 \(O(n \log n)\),瓶颈在二分

标签:前缀,CF1923D,后缀,Slimes,lst,cases
From: https://www.cnblogs.com/fox-konata/p/18076875

相关文章

  • D. Slimes
    原题链接题解对于任何一个粘液块s而言,要么是从左边被吞并,要么是从右边被吞并,根据对称性,两边的决策是一样的,因此先考虑右边对于被右边吞并而言,有以下几个特征1.起始粘液一定是吞掉了s右边一整块连续的粘液2.右边区间一定存在大小不同的相邻粘液,这样才能发动吞并3.由一二猜想,......
  • AGC004B Colorful Slimes
    ${\scr\color{Orchid}{\text{生于尘埃,溺于人海,死于理想高台。}}}$题目链接:ColorfulSlimes${\scr\color{Cyan}{\text{Solution}}}$分析思路:挺神奇的$dp$一个比较显然的结论:最小值的方案中第$2$种操作最多用$n-1$次证明大概就是一个数用$n-1$次一定会变成另一个数......
  • [ABC140F] Many Slimes
    2023-02-13题目题目传送门翻译翻译难度&重要性(1~10):6题目来源AtCoder题目算法贪心解题思路用了两个multiseta和一个sets,一个multiset用来记录用来存还剩哪些数没生成,另一个用来存已经生成了哪些数,然后后面放数的时候就枚举第二个multiset来生成新的数。然......
  • 【luogu CF618G】Combining Slimes(矩阵乘法)(DP)
    CombiningSlimes题目链接:luoguCF618G题目大意有一个长度为n的栈,如果栈顶两个值都是x就会合并成x+1,一开始没有东西。你有p的概率放进去一个1,1-p的概率放入2......