P10160 [DTCPC 2024] Ultra
题目背景
Tony2 喜欢玩某二字游戏，这一天他在小 C 面前展示他的Ultra \text{Ultra}Ultra。
但是小 C 不会Ultra \text{Ultra}Ultra，所以他跑去图图酱一去了。
然后图图失败了
于是小 C 趁 Tony2 不在的时候偷偷地把他的跳跃键和下冲键交换了（
题目描述
Tony2 的操作可以看作下冲和跳跃的组合。
称一个Ultra \text{Ultra}Ultra为一段连续的操作，以下冲开头，然后跳跃和下冲交替，并以下冲结束。由于是Ultra \text{Ultra}Ultra，所以至少要有一次跳跃。
小 C 每次可以将一个Ultra \text{Ultra}Ultra变成uLTRA \text{uLTRA}uLTRA，也就是将这个Ultra \text{Ultra}Ultra的每个下冲变成跳跃，将每个跳跃变成下冲。
小 C 不喜欢Ultra \text{Ultra}Ultra，所以想要使得下冲次数尽量少。
形式化题意
给你一个01 0101序列，你可以进行如下操作若干次（或零次）:
- 将序列中形如101 ⋯ 01 101\cdots01101⋯01的一个子串（即1 ( 01 ) k 1(01)^k1(01)k，k ≥ 1 k\ge 1k≥1）替换成等长的010 ⋯ 10 010\cdots10010⋯10（即0 ( 10 ) k 0(10)^k0(10)k）。
你要操作使得1 11的个数尽可能少，输出最少的1 11的个数。
输入格式
一行一个长度为n nn（n ≤ 10 6 n\le 10^6n≤106） 的字符串表示这个01 0101序列。
输出格式
输出一个数表示最少的1 11的个数。
输入输出样例 #1
输入 #1
1010011输出 #1
3说明/提示
样例1 11解释：选中该串的前三个字符101 101101，对其操作后该串变为0100011 01000110100011，仅包含3 33个1 11。容易证明这是最优的。
C++实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=1e6+10;intn,ans;chars[MAXN];intl[MAXN],r[MAXN],sum[MAXN],cnt;intmain(){scanf("%s",s+1),n=strlen(s+1);for(inti=1;i<=n;i++)if(s[i]=='1')ans++;for(inti=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]&1);for(inti=1,j=1,k=0;i<=n;){if(s[i]!='1'){i++,k=0;continue;}for(j=i;j+2<=n&&s[j+1]=='0'&&s[j+2]=='1';j+=2);if(i!=j){if(cnt&&r[cnt]+k+1==i)r[cnt]=j;elsel[++cnt]=i-k,r[cnt]=j;k=0;}else{if(cnt&&l[cnt]!=r[cnt]&&r[cnt]+1==i)r[cnt]++;elsek++;}i=j+1;}for(inti=1;i<=cnt;i++)ans-=sum[r[i]]-sum[l[i]-1]-1;printf("%d",ans);}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
