T4 午枫的又一个01串 题目大意 给定一个 010101 串，这个串的度为相邻两位元素不相同的个数，可以进行指定操作最多 mmm 次，求出最小度是多少。 解题思路 对于一个 010101 串，如果我们进行的操作区间不在开头也不在结尾，即 [l,r][l,r][l,r] 满足 1<l<r<n1<l<r<n1<l<r<n ，不难 sls_lsl 和 sl−1s_{l-1}sl−1 从不同变为相同，srs_rsr 和 sr***_{r****r+1 从不同变为相同。所以当我们对中间部分操作一次，度就会减 222 。 考虑完中间部分操作的影响，接下来考虑开头和结尾操作会有什么影响： 如果开头 s1=1s_1=1s1 =1 ，则无法操作，同理，如果结尾 sn=0s_n=0sn =0 也无法操作。 如果开头 s1=0s_1=0s1 =0 ，我们对区间 [1,r][1,r][1,r] (1<r<n)(1<r<n)(1<r<n) 做一次操作后，由于 s1s_1s1 前面没有数字了，原本就没有度，所以左端点的改变不会的度产生影响，srs_rsr 和 sr***_{r****r+1 从不同变为相同，因此此次操作会让度减少 111 。同理，对结尾 sn=1s_n=1sn =1 ，做一次操作也会让度减少 111 。 因此，先求出原串的度，优先对串的中间部分进行操作，在判断开头结尾的情况做出相应操作，计算度的减少量即可。 参考代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=1e6+5; char s[N]; vector<int> ve; int main() { int n,m; scanf("%d %d",&n,&m); cin>>(char*)(s+1); int ans=0; for (int i=1;i<n;i++) { if (s[i]!=s[i+1]) { ans++; } } int cnt=0,t=0; for (int i=1;i<=n;i++) { if (s[i]'0') { if (i1) { t++; }else if (s[i-1]'1') { cnt++; } }else if (s[i]'1') { if (in) { if (cnt>=1) { cnt--; ve.push_back(1); } }else if (s[i+1]'0') { if (cnt>=1) { cnt--; ve.push_back(2); }else if (t==1) { t--; ve.push_back(1); } } } } sort(ve.begin(),ve.end()); for (int i=ve.size()-1;i>=0&&m>=1;i--,m--) { ans-=ve[i]; } printf("%d",ans); return 0; }