题目链接

样例说明

样例中：

• 小明的第一次操作是查询，我们可以得到字符串 “010011” 中第一次出现 ‘1’ 的位置为 2 。

• 小明的第二次操作将下标为 2的字符反转，此时字符串变为 “000011” 。

• 小明的第三次操作是查询，我们可以得到字符串 “000011” 中第一次出现 ‘1’
  的位置为 5 。

• 小明的第四次操作是将下标为 6 的字符反转，此时字符串变为 “000010”

• 小明的第五次操作是查询，我们可以得到字符串 “000010” 中第一次出现 ‘1’ 的位置为 5 。

理解了！从程序设计学生的角度来看，我们可以通过一些简单而高效的方式来处理这个问题。我们先理清问题的要点，找出最直接的求解方式，然后给出代码实现。

问题要点总结

1. 字符串更新和查询：我们有一个初始的二进制字符串 s，需要进行 q 次操作。

   • 操作1：查询字符串中第一次出现 '1' 的位置。
   • 操作2：反转指定位置上的字符（从 '0' 变为 '1'，或者从 '1' 变为 '0'）。

2. 高效求解的关键：

   • 对于 操作1，直接遍历字符串查找第一个 '1' 会比较低效，特别是在字符串很长且查询次数较多的情况下。
   • 对于 操作2，我们只需要在原字符串上更新指定位置的值。

思路

• 初始化阶段：先将字符串转换为一个列表，方便后续更新字符。
• 查询操作：每次查询我们可以从当前字符串的头部开始查找第一个 '1'，如果找到了，就返回其位置。如果没有找到，返回 -1。
• 更新操作：直接对字符串中指定位置的字符进行反转，之后查询操作可以直接利用更新后的字符串。

具体步骤：

1. 初始化：

   • 将输入字符串 s 转换为列表，方便修改。
   • 找到字符串中第一个 '1' 的位置，并记录。

2. 操作1：直接输出记录的第一个 '1' 的位置。

3. 操作2：反转指定位置的字符，并更新 first_one_index（如果该位置是 '1' 或 '0'）。

算法设计

1. 将字符串转换为列表，以便快速修改。
2. 遍历字符串一次，记录第一个 '1' 的位置。
3. 对于操作1，直接返回 first_one_index。
4. 对于操作2，更新指定位置，并根据需要调整 first_one_index。

代码实现

Python 实现：

python">import os
import sys# 请在此输入您的代码
# 获取n,q,s
n,q=map(int,input().split(" "))
s=input()
result=[]
for _ in range(q):temp_q=input()if int(temp_q[0])==1:# 就开始查找第一次1出现的位置result.append(int(s.find("1"))+1)   #记得转化成1开始的下标else:user_position=int(temp_q.split(" ")[1])-1  #转换成下标change_number=abs(1-int(s[user_position])) s=s[0:user_position]+str(change_number)+s[user_position+1:]for _ in range(len(result)):print(result[_])

代码解释

1. 输入部分：

   • 首先通过 map(int, input().split(" ")) 获取了两个整数 n 和 q，表示字符串长度和操作次数。
   • 接着获取字符串 s，并初始化一个 result 列表，用来存储查询操作的结果。

2. 循环处理每一个操作：

   • 对于每一个操作，判断操作类型。
   • 如果操作类型是 1（查询操作），则用 find() 方法查找字符串中第一次出现 1 的位置，记得加 1 转化成 1-based 索引，并存入 result 列表。
   • 如果操作类型是 2（反转操作），则获取指定的下标，将该位置字符反转（使用 abs(1-int(...))，实现 0 与 1 的切换），然后将反转后的字符串拼接起来。

3. 输出结果：

   • 最后通过遍历 result 列表，输出所有查询操作的结果。

其他版本

其他版本都使用了相似的思路：

• 查询操作：直接通过字符串查找第一次出现 '1' 的位置，记得转换为 1-based 索引。
• 反转操作：反转字符串中指定位置的字符，并更新字符串。

C 版本实现

#include <stdio.h>
#include <string.h>int main() {int n, q;scanf("%d %d", &n, &q);char s[n + 1];scanf("%s", s);int result[q];  // 用于存储查询操作的结果int resultIndex = 0;// 处理每个操作for (int i = 0; i < q; i++) {int op;scanf("%d", &op);if (op == 1) {  // 查询操作// 查找第一个 '1' 的位置char* first_one = strchr(s, '1');  // 找到第一个 '1'if (first_one != NULL) {result[resultIndex++] = first_one - s + 1;  // 1-based 索引} else {result[resultIndex++] = -1;}} else if (op == 2) {  // 反转操作int x;scanf("%d", &x);x--;  // 转换为0-based索引s[x] = (s[x] == '1') ? '0' : '1';  // 反转字符}}// 输出查询结果for (int i = 0; i < resultIndex; i++) {printf("%d\n", result[i]);}return 0;
}

C++ 版本实现

#include <iostream>
#include <string>
using namespace std;int main() {int n, q;cin >> n >> q;string s;cin >> s;int result[q];  // 用于存储查询操作的结果int resultIndex = 0;// 处理每个操作for (int i = 0; i < q; i++) {int op;cin >> op;if (op == 1) {  // 查询操作size_t pos = s.find('1');if (pos != string::npos) {result[resultIndex++] = pos + 1;  // 1-based 索引} else {result[resultIndex++] = -1;}} else if (op == 2) {  // 反转操作int x;cin >> x;x--;  // 转换为0-based索引s[x] = (s[x] == '1') ? '0' : '1';  // 反转字符}}// 输出查询结果for (int i = 0; i < resultIndex; i++) {cout << result[i] << endl;}return 0;
}

Java 版本实现

java">import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入n和qint n = scanner.nextInt();int q = scanner.nextInt();// 输入字符串StringBuilder s = new StringBuilder(scanner.next());// 用于存储查询结果List<Integer> result = new ArrayList<>();// 处理每个操作for (int i = 0; i < q; i++) {int op = scanner.nextInt();if (op == 1) {  // 查询操作int pos = s.indexOf("1");if (pos != -1) {result.add(pos + 1);  // 1-based 索引} else {result.add(-1);}} else if (op == 2) {  // 反转操作int x = scanner.nextInt() - 1;  // 转换为0-based索引char currentChar = s.charAt(x);s.setCharAt(x, (currentChar == '1') ? '0' : '1');  // 反转字符}}// 输出查询结果for (int res : result) {System.out.println(res);}scanner.close();}
}

解释：

• C: 使用 strchr() 函数查找第一个 '1' 的位置，如果找到了就输出其位置（转换为 1-based 索引），否则输出 -1。
• C++: 使用 find() 方法查找字符串中第一次出现 '1' 的位置，处理和 C 类似。
• Java: 使用 indexOf("1") 方法查找字符串中第一次出现 '1' 的位置，处理逻辑与 C/C++ 相同。