首页 > 试题广场 >

选数Ⅱ

[编程题]选数Ⅱ
  • 热度指数：490 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

一个长度为  的只包含字符  和  的字符串 ，下标从  开始。

每次给出一个区间 ，对下标在区间内（包含左右端点）的字符进行染色，在满足下面两个要求的前提下，最多能染色多少个字符？注意每个询问都是独立的，不会对后续询问造成影响。

1）染色的字符的下标  满足 l\leq p_i\leq r。

2）不存在任意两个相邻的字符  同时被染色。


输入描述:
第一行包含两个整数 n\ q\ (1\leq n,q\leq 3\times10^5)，表示字符串长度和询问次数。
第二行包含一个长度为  且只包含数字  和  的字符串。
接下来  行，每行两个整数 l\ r\ (1\leq l\leq r\leq n)，表示询问区间。


输出描述:
输出包含  行，每行一个整数，表示最多染色的下标。
示例1

输入

8 2
01011111
2 5
1 8

输出

3
6

说明

第一个询问染色下标  或 。
第二个询问染色下标 。

备注:

算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-28 00:54:12
题目链接 选数Ⅱ 题目描述 给定一个长度为 、只包含 '0' 和 '1' 的字符串 。有 次独立的询问，每次询问给出一个区间 。对于每个询问，我们需要在子串 中选取若干字符进行染色，要求： 只有字符 '1' 能被染色。 不能有两个相邻的字符同时被染色。 目标是计算在满足以上条件下，最多能染色 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

线段树 动态规划
难度：
0条回答 111浏览

热门推荐

相关试题

选数Ⅱ

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号