打卡信奥刷题（3419）用C++实现信奥题 P10160 [DTCPC 2024] Ultra

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)kk ≥ 1 k\ge 1k≥1替换成等长的010 ⋯ 10 010\cdots10010⋯10即0 ( 10 ) k 0(10)^k0(10)k。你要操作使得1 11的个数尽可能少输出最少的1 11的个数。输入格式一行一个长度为n nnn ≤ 10 6 n\le 10^6n≤106 的字符串表示这个01 0101序列。输出格式输出一个数表示最少的1 11的个数。输入输出样例 #1输入 #11010011输出 #13说明/提示样例1 11解释选中该串的前三个字符101 101101对其操作后该串变为0100011 01000110100011仅包含3 33个1 11。容易证明这是最优的。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN1e610;intn,ans;chars[MAXN];intl[MAXN],r[MAXN],sum[MAXN],cnt;intmain(){scanf(%s,s1),nstrlen(s1);for(inti1;in;i)if(s[i]1)ans;for(inti1;in;i)sum[i]sum[i-1](s[i]1);for(inti1,j1,k0;in;){if(s[i]!1){i,k0;continue;}for(ji;j2ns[j1]0s[j2]1;j2);if(i!j){if(cntr[cnt]k1i)r[cnt]j;elsel[cnt]i-k,r[cnt]j;k0;}else{if(cntl[cnt]!r[cnt]r[cnt]1i)r[cnt];elsek;}ij1;}for(inti1;icnt;i)ans-sum[r[i]]-sum[l[i]-1]-1;printf(%d,ans);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容