题解 | #选数Ⅱ#
选数Ⅱ
https://www.nowcoder.com/practice/3647d44e120b4ec19536a8236d251a06
题目链接
题目描述
给定一个长度为 、只包含 '0' 和 '1' 的字符串
。有
次独立的询问，每次询问给出一个区间
。对于每个询问，我们需要在子串
中选取若干字符进行染色，要求：
- 只有字符 '1' 能被染色。
- 不能有两个相邻的字符同时被染色。
目标是计算在满足以上条件下，最多能染色的字符数量。
解题思路
本题要求在字符串的子区间中，选取满足条件的字符进行染色，以使数量最多。在仔细分析题目和标准解法后，我们发现题目的核心规则可以分解为两个独立的部分：
- 字符 '0' 的染色：题目中的不相邻约束 “不存在任意两个相邻的字符 1 同时被染色” 只针对字符 '1'。这意味着字符 '0' 没有限制，可以全部被染色。
- 字符 '1' 的染色：需要遵循不相邻的规则。
因此，最终的答案等于 (区间内 '0' 的数量) + (区间内不相邻 '1' 的最大数量)。
我们可以分别计算这两个部分：
1. 计算区间内 '0' 的数量
这可以通过一个简单的前缀和数组 sum_zeros 来实现。sum_zeros[i] 存储原字符串前 个字符中 '0' 的数量。对于任意查询
，'0' 的数量就是
sum_zeros[r] - sum_zeros[l-1]。
2. 计算区间内不相邻 '1' 的最大数量
这是一个动态规划问题，但可以用贪心和二进制倍增（Binary Lifting）来高效求解。
-
贪心策略：为了选取尽可能多的 '1'，最优的策略是从区间的右端点
出发，贪心地选择最靠右的那个可以被选择的 '1'，然后从这个位置向前寻找下一个可以被合法选择的最靠右的 '1'，如此往复，直到跳出区间
。
-
构建“跳转”关系：我们可以预处理一个数组
parent[i]，它表示“如果我当前选择了位置（假设
），那么在我之前，下一个可以合法选择的位置在哪里？”。
- 如果
，那么前一个位置没有限制，我们可以从上一个 '1' 的位置跳转而来。
- 如果
，那么我们不能选择
，必须从
- 如果
-
二进制倍增优化：一步步地往前跳转效率太低。我们可以构建一个二维数组
f[i][j]，表示从位置次到达的位置。这可以使用动态规划在
的时间内预处理出来。
-
查询：对于查询
f数组进行倍增跳转，每次都尝试跳跃最大的步数，同时保证不会跳出区间下界。通过累加跳跃的步数，我们就能在
的时间内计算出从
将两部分结果相加，即得到最终答案。总时间复杂度为 。
代码
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main() {
// 开启快速IO
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
string s_str;
cin >> s_str;
s_str = " " + s_str; // 字符串下标从1开始，方便处理
// sum_zeros[i] 记录前i个字符中'0'的数量
vector<int> sum_zeros(n + 1, 0);
// f[i][j] 记录从位置i向前跳2^j步到达的位置
vector<vector<int>> f(n + 2, vector<int>(20, 0));
// last1: 最近的'1'的位置, prev_last1: 次近的'1'的位置
int last1 = 0, prev_last1 = 0;
for (int i = 1; i <= n; i++) {
sum_zeros[i] = sum_zeros[i - 1];
if (s_str[i] == '1') {
// 如果当前'1'与上一个'1'相邻, 则父节点是上上个'1'
if (last1 > 0 && last1 + 1 == i) {
f[i][0] = prev_last1;
} else { // 否则父节点是上一个'1'
f[i][0] = last1;
}
prev_last1 = last1;
last1 = i;
} else {
sum_zeros[i]++;
f[i][0] = last1; // '0' 的父节点是上一个'1'
}
// 使用DP构建倍增表
for (int j = 1; j < 20; j++) {
f[i][j] = f[f[i][j-1]][j-1];
}
}
while (q--) {
int l, r;
cin >> l >> r;
// 1. 计算区间内'0'的数量
int zeros_count = sum_zeros[r] - sum_zeros[l - 1];
// 2. 倍增计算不相邻'1'的最大数量
int ones_count = 0;
int current_pos = r;
// 从r开始贪心选择'1'
if (s_str[current_pos] == '1') {
ones_count = 1;
} else {
// 如果r是'0', 则从它之前最近的'1'开始
current_pos = f[r][0];
if(current_pos >= l) {
ones_count = 1;
}
}
// 如果起点在区间内，开始倍增跳转
if (current_pos >= l) {
for (int i = 19; i >= 0; i--) {
// 尝试跳2^i步，如果目的地仍在区间内，则执行跳转
if (f[current_pos][i] >= l) {
ones_count += (1 << i);
current_pos = f[current_pos][i];
}
}
} else {
ones_count = 0; // 起点已在区间外
}
cout << zeros_count + ones_count << "\n";
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
String s = " " + sc.next(); // 字符串下标从1开始
// sumZeros[i] 记录前i个字符中'0'的数量
int[] sumZeros = new int[n + 1];
// f[i][j] 记录从位置i向前跳2^j步到达的位置
int[][] f = new int[n + 2][20];
// last1: 最近的'1'的位置, prevLast1: 次近的'1'的位置
int last1 = 0, prevLast1 = 0;
for (int i = 1; i <= n; i++) {
sumZeros[i] = sumZeros[i - 1];
if (s.charAt(i) == '1') {
// 如果当前'1'与上一个'1'相邻, 则父节点是上上个'1'
if (last1 > 0 && last1 + 1 == i) {
f[i][0] = prevLast1;
} else { // 否则父节点是上一个'1'
f[i][0] = last1;
}
prevLast1 = last1;
last1 = i;
} else {
sumZeros[i]++;
f[i][0] = last1; // '0' 的父节点是上一个'1'
}
// 使用DP构建倍增表
for (int j = 1; j < 20; j++) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
StringBuilder sb = new StringBuilder();
for (int k = 0; k < q; k++) {
int l = sc.nextInt();
int r = sc.nextInt();
// 1. 计算区间内'0'的数量
int zerosCount = sumZeros[r] - sumZeros[l - 1];
int onesCount = 0;
int currentPos = r;
// 从r开始贪心选择'1'
if (s.charAt(currentPos) == '1') {
onesCount = 1;
} else {
// 如果r是'0', 则从它之前最近的'1'开始
currentPos = f[r][0];
if (currentPos >= l) {
onesCount = 1;
}
}
// 如果起点在区间内，开始倍增跳转
if (currentPos >= l) {
for (int i = 19; i >= 0; i--) {
// 尝试跳2^i步，如果目的地仍在区间内，则执行跳转
if (f[currentPos][i] >= l) {
onesCount += (1 << i);
currentPos = f[currentPos][i];
}
}
} else {
onesCount = 0; // 起点已在区间外
}
sb.append(zerosCount + onesCount).append("\n");
}
System.out.print(sb.toString());
}
}
import sys
def main():
n, q = map(int, input().split())
s = " " + input() # 字符串下标从1开始
# sum_zeros[i] 记录前i个字符中'0'的数量
sum_zeros = [0] * (n + 1)
# f[i][j] 记录从位置i向前跳2^j步到达的位置
f = [[0] * 20 for _ in range(n + 2)]
# last1: 最近的'1'的位置, prev_last1: 次近的'1'的位置
last1, prev_last1 = 0, 0
for i in range(1, n + 1):
sum_zeros[i] = sum_zeros[i - 1]
if s[i] == '1':
# 如果当前'1'与上一个'1'相邻, 则父节点是上上个'1'
if last1 > 0 and last1 + 1 == i:
f[i][0] = prev_last1
else: # 否则父节点是上一个'1'
f[i][0] = last1
prev_last1 = last1
last1 = i
else:
sum_zeros[i] += 1
f[i][0] = last1 # '0' 的父节点是上一个'1'
# 使用DP构建倍增表
for j in range(1, 20):
f[i][j] = f[f[i][j - 1]][j - 1]
for _ in range(q):
l, r = map(int, input().split())
# 1. 计算区间内'0'的数量
zeros_count = sum_zeros[r] - sum_zeros[l - 1]
ones_count = 0
current_pos = r
# 从r开始贪心选择'1'
if s[current_pos] == '1':
ones_count = 1
else:
# 如果r是'0', 则从它之前最近的'1'开始
current_pos = f[r][0]
if current_pos >= l:
ones_count = 1
# 如果起点在区间内，开始倍增跳转
if current_pos >= l:
for i in range(19, -1, -1):
# 尝试跳2^i步，如果目的地仍在区间内，则执行跳转
if f[current_pos][i] >= l:
ones_count += (1 << i)
current_pos = f[current_pos][i]
else:
ones_count = 0 # 起点已在区间外
print(zeros_count + ones_count)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：前缀和、贪心、二进制倍增
- 时间复杂度：预处理前缀和数组
sum_zeros需要。预处理二进制倍增数组
f需要。每次查询都进行一次倍增跳转，需要
。总共有
次查询，因此总时间复杂度为
。
- 空间复杂度：
sum_zeros数组需要f数组需要
投递4399游戏等公司10个岗位