C. Binary String Copying - 思维

 

 分析：

        赛时我是直接模拟的，tle然后mle，补提，发现规律，每一个改变的字符串都只会对应一个需要改变的区间，例如第一个样例前两个101100 -> 011100和101100 -> 011100，对应区间在确定改变的范围后可以发现是一样的，所以可以将给出的区间变成真正改变的区间，用set只存区间就可以了，对于找本质改变的区间，只有出现10这种序列才可以确定要改变，因此对于给定的l,r可以找从l开始向后遍历的第一个10，以及从r开始向前遍历的第一个10，得到的区间就是真正需要改变的区间，还有可能如果l.>r的时候，区间不存在，那么表示s本身，没有改变，也算一种新的字符串，也要存下来。

代码：

#include <bits/stdc++.h>using namespace std;
using ll = long long;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --){int n, m;cin >> n >> m;string s;cin >> s;s = " " + s;vector<int> l(n + 2, -1), r(n + 2, n + 2);for(int i = 1; i <= n; i ++) {l[i] = l[i - 1];if(s[i] == '0') l[i] = i;}for(int i = n; i >= 1; i --) {r[i] = r[i + 1];if(s[i] == '1') r[i] = i;}set<pair<int, int>> ans;while(m --) {int a, b;cin >> a >> b;if(r[a] <= l[b]) ans.insert({r[a], l[b]});else ans.insert({-1, -1});}cout << ans.size() << '\n';}
}