P6878 [JOI 2020 Final] JJOOII 2 题解

Makerlife 的小站

2025-2026 赛季游记 && 退役记 NOIP 2024 游记集训记录 CSP2024 游记板子库动态规划刷题记录杂题乱记数学期望学习笔记数论学习笔记 CF1000F One Occurrence 题解 CSP2023 游寄主定理 CF1695C Zero Path 题解字符串算法全家桶学习笔记 AT_ABC306D 题解 2023.06.03 模拟赛 Azure for Students 使用指北 AT_ABC286C 题解洛谷 AT1898 题解洛谷 CF1036A 题解洛谷 CF1040A 题解洛谷 SP3591 题解洛谷 AT278 题解洛谷 CF141B 题解洛谷 AT2561 题解洛谷 AT3525 题解洛谷 CF899B 题解洛谷 AT4787 题解洛谷 AT4810 题解洛谷 SP5450 题解

Makerlife · 2023-10-28 · via Makerlife 的小站

Problem Link

Explanation

给定一个只包含 J\tt J、O\tt O、I\tt I 三种字符、长度为 NN 的字符串 SS 和一个正整数 KK。定义 KK 阶 JOI\tt JOI 串为由恰好 KK 个 J\tt J 、KK 个 O\tt O 、KK 个 I\tt I 依次拼接而成的字串。如 22 阶 JOI\tt JOI 串为 JJOOII\tt JJOOII。你可以对 SS 进行任意次以下操作以将 SS 变为 KK 阶 JOI\tt JOI 串：

删除 SS 的第一个字符
删除 SS 的最后一个字符
删除 SS 的任意一个字符

要求最小化并输出第三种操作的次数。如果不能将 SS 变为 KK 阶 JOI\tt JOI 串，输出 -1。

Solution

可以发现只要定位到了最前端的 J\tt J 的位置，那么就可以确定一个最短的 JOI\tt JOI 串。

即我们可以暴力从前向后扫 J\tt J 的位置，然后依次找到 KK 个 O\tt O 和 I\tt I 即可。

可以对上面的算法进行优化，我们记录每个 J\tt J、O\tt O、I\tt I 的位置为 cj、co、ci，那么一段 J\tt J 的开始位置即为 cjjcj_j，结束位置为 cjj+k−1cj_{j+k-1}，O\tt O，I\tt I 同理。

Core Code

int n,k;
char s[N];
int cj[N],co[N],ci[N];
int totj,toto,toti;
int ans=INF;
int main()
{
	n=read();k=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='J') cj[++totj]=i;
        if(s[i]=='O') co[++toto]=i;
        if(s[i]=='I') ci[++toti]=i;
	}
    for(int i=1;i<=totj;i++)
    {
        if(i+k-1>totj) break;//后面不足 k 个 j，下面 o,i 同理
        int ed=cj[i+k-1];//一段 j 的结束，下面 o,i 同理
        int pos=1;
        while(co[pos]<=ed && pos<=toto) pos++;//o 的起始位置，下面 i 同理
        if(pos+k-1>toto) break;
        ed=co[pos+k-1];
        pos=1;
        while(ci[pos]<=ed && pos<=toti) pos++;
        if(pos+k-1>toti) break;
        ed=ci[pos+k-1];
        ans=min(ans,ed-cj[i]+1-3*k);//答案为枚举的区间长度与 3*k 的差
    }
    printf("%d\n",(ans==INF)?-1:ans);
	return 0;
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Makerlife 的小站

Explanation

Solution

Core Code