首页 > 其他分享 >题解 P6878 [JOI 2020 Final] JJOOII 2

题解 P6878 [JOI 2020 Final] JJOOII 2

时间:2023-11-05 20:55:19浏览次数:38  
标签:字符 题意 P6878 题解 JJOOII 最右 2020 Final

好久没写题解,水一篇。

题意

题意显然。

分析

看到这道题,我们就应该进行一个小贪心,对于最左边某一字符,直到最右边的这一字符,我们不会在中间删除同样的字符,不然则可以保留这一字符,将两边往内缩。

也就是说,我们确定了最左边的 J 后,那么留下最后一个 J 必然是当前这个 J 的后面的第 \(K-1\) 个 J,对于 O 和 I 同理,找到从当前节点开始,包括当前结点的,向后共有 \(K\) 个某字符的最左端点。

这个处理,我们可以使用一个栈从右向左来维护相同字符即可。

最后的答案,我们通过枚举最左边的 J,进一步确定最右的 J,确定最右的 O,最右的 I,这两个之间的价值就是 \(R-L+1-3\times K\)。

标签:字符,题意,P6878,题解,JJOOII,最右,2020,Final
From: https://www.cnblogs.com/djh0314/p/17811144.html

相关文章

  • ARC_068F Solitaire题解
    非常骚的一道题首先看数据范围就很像dp(而且在dp专题里),尝试直接dp,发现不太行手玩一波样例,发现答案是2的若干次方乘一个系数。我们发现“若干”=n-k-1,这是巧合吗!?思索一番,会发现当我们取完k个数后剩下的n-k个数取法就为2^(n-k-1),为什么呢?可以把每次操作看成“前取“”or......
  • 2023年11月第一周题解-------数组
    1.问题A:LY学长的随机数解题思路第一种思路是先去重后排序第二种思路是先排序再去重解题方法暴力遍历#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#defineN10voidquickSort......
  • CF1838C题解
    显然\(1\)不是质数,除二外偶数不是质数。然后分类讨论对于\(m\)为偶数,构造\[\begin{bmatrix}1&2&3&\cdots&m\\m+1&m+2&m+3&\cdots&2m\\&&\cdot\\&&\cdot\\&&\cdot\\......
  • CF859G 题解
    总结题意显然可以转化为序列问题嘛。给出序列\(A\{a_i\}\),你需要通过若干次操作使其归零。操作:选定\(d|n\)、\(k\)、\(r\),对于序列中所有满足\(i\bmodd=r\)的位置加上\(k\)。题解很明显,加减相互抵消,对于所有\(d\)、\(r\)相同的位置可以视作一次操作。如何表示......
  • CF773A 题解
    真的是蓝题?这真的不是小学数学题?我们是要求满足(其中\(a\)为正确数,\(b\)为总数)\[\frac{x+a}{y+b}=\frac{p}{q}\]的最小\(b\)。我们可以先把右式的分子分母变化到与\(\frac{x}{y}\)类似的大小。intbs1=x/p+(x%p!=0);intbs2=y/q+(y%q!=0);i......
  • 【洛谷 P1909】[NOIP2016 普及组] 买铅笔 题解(打擂台法)
    [NOIP2016普及组]买铅笔题目背景NOIP2016普及组T1题目描述P老师需要去商店买支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起见,P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装......
  • USACO铂金题解
    USACO铂金题解USACO2018PlatiumB.SortItOut很巧妙的转换注意到操作并不会影响没有被选中的牛的相对顺序所以没有被选中的一定单调递增要使得选中的尽可能少,就要选尽可能长的没有被选中的序列,即原序列的\(LIS\)所以原题等价于求原序列第\(k\)大\(LIS\)用树状数组......
  • [ARC140B] Shorten ARC 题解
    分析自然,我们可以想到利用贪心去解题。我们可以证明,$\texttt{ARC}$左右两边$\texttt{A}$和$\texttt{C}$个数多的比少的变为$\texttt{R}$贡献能更多,第奇数次操作比第偶数次能使操作次数更多。于是,我们可以得出这样的一个算法:若为奇数次操作那我们将现有的$\texttt{ARC......
  • 哈理工新生赛题解
    A小亮的睡眠时间思路:求一下一共花了多少时间思考,注意思考时间大于睡觉时间上限的特殊情况。#include<iostream>usingnamespacestd;intmain(){intn;scanf("%d",&n);intsum=0;intcur;inttotal=450;inth=0;ints=0;......
  • CF1089K King Kog's Reception 题解
    题目传送门前置知识线段树解法第一眼感觉和luoguP1083[NOIP2012提高组]借教室很像。本题同样采用线段树维护,\(sum_{l,r}(1\lel\ler\le10^6)\)表示从\(l\simr\)时刻内骑士拜访的总时间,\(maxx_{l,r}(1\lel\ler\le10^6)\)表示从\(l\simr\)时刻内骑士......