小美的01串翻转【牛客tracker 每日一题】
小美的01串翻转
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小美定义一个01 0101串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。
例如，" 10001 " "10001""10001"的权值是1 11，因为只需要修改一次：对第三个字符取反即可。
现在小美拿到了一个01 0101串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗？
输入描述：
一个仅包含′ 0 ′ '0'′0′和′ 1 ′ '1'′1′的字符串，长度不超过2000 20002000。
输出描述：
所有非空子串的权值和。
示例1
输入：
10001输出：
8说明：
长度为 2 的子串中，有2 22个" 00 " "00""00"的权值是1 11。
长度为3 33的3 33个子串权值都是1 11。
长度为4 44的2 22个子串权值都是1 11。
长度为5 55的1 11个子串权值是1 11。
总权值之和为2 + 3 + 2 + 1 = 8 2+3+2+1=82+3+2+1=8
解题思路
本题核心是枚举子串+前缀和优化求解所有子串的最小翻转权值之和。满足相邻字符不同的01 0101串仅有两种固定模式：奇数位为1 11、偶数位为0 00；奇数位为0 00、偶数位为1 11。任意子串的最小翻转次数 = 子串长度 - 两种模式中匹配字符数的最大值。使用前缀和数组预处理两种模式下的字符匹配数量，双重循环枚举所有非空连续子串，通过前缀和O(1)计算子串的匹配数，求出权值后累加。算法时间复杂度O ( n 2 ) O(n^2)O(n2)，字符串长度不超过2000 20002000，计算量仅400 400400万，高效且精准。
总结
核心逻辑：交替01 0101串仅两种合法模式，最小翻转次数由最大匹配数决定，枚举所有子串求和。
关键操作：前缀和预处理模式匹配数，双重循环枚举子串，快速计算单串权值并累加。
效率保障：O ( n 2 ) O(n^2)O(n2)复杂度完美适配题目长度限制，无冗余计算，快速得到答案。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=2e7+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;intmain(){string s;cin>>s;ll n=s.size();vector<ll>x1(n+1,0),x2(n+1,0),y1(n+1,0),y2(n+1,0);for(ll i=1;i<=n;i++){x1[i]=x1[i-1];x2[i]=x2[i-1];y1[i]=y1[i-1];y2[i]=y2[i-1];if(i&1){if(s[i-1]=='1')x2[i]++;elsex1[i]++;}else{if(s[i-1]=='1')y2[i]++;elsey1[i]++;}}ll ans=0;for(ll i=1;i<=n;i++)for(ll j=i;j<=n;j++){ans+=j-i+1-max(y1[j]-y1[i-1]+x2[j]-x2[i-1],y2[j]-y2[i-1]+x1[j]-x1[i-1]);}cout<<ans<<endl;return0;}