题解 | #小红的大小判断#(官方题解详细版)
思路如下
对于本题翻转的情况
- 情况1:连通块数量多1 左边界与左边界左边的一样 000111 翻转的时候就会多一个 001000
- 情况2:连通块数量少1 左边界与左边界的不一样 0011100 翻转的时候就会少一个 0000011
- 情况3:连通块数量不变 仅有整个字符串两侧的翻转不变 所以要想通过情况3不变 只有两个边缘的情况
所以需要通过枚举边界寻找范围
- 如图
- 在枚举右边界的过程中
- 计算出此时的右边界左侧相同的数量left_qk1
- 左侧一共有i个 (i的范围是1开始不是0 所以忽略了最左侧)(最右侧也是一样忽略掉)
- 那么不相同的就是i-left_qk1个
- 两侧一个加一个减 就是不变
#define int long long //最好还是开一下long long 数据很大
using namespace std;
signed main(){
string s;
cin>>s;
int count1=1;
int left_qk1=0;
for(int i=1;i<s.size()-1;i++){
//以i为右边界 顺便遍历左边界
if(s[i]!=s[i-1]) left_qk1++;//左边界不相同的情况 遍历范围1-i
if(s[i]!=s[i+1]){
//右侧边界不相同的情况 那么此时的总数应该取决于左侧边界相同的情况有多少
count1+=i-left_qk1;
}
else{
//右侧边界相同的情况 对应左侧边界不相同的情况
count1+=left_qk1;
}
}
cout<<count1;
return 0;
}
//考试未发现的关键性质
//区间内翻转并不会影响区间内相邻连通块数量,仅会影响区间边缘的连通块数量
//对于本题翻转的情况
//情况1:连通块数量多1 左边界与左边界左边的一样 000111 翻转的时候就会多一个 001000
//情况2:连通块数量少1 左边界与左边界的不一样 0011100 翻转的时候就会少一个 0000011
//情况3:连通块数量不变 仅有整个字符串两侧的翻转不变 所以要想通过情况3不变 只有两个边缘的情况
//考试时思路:
//0011000 1 2 3 0011000
//分析 先求一共多少个颜色块 根据颜色块遍历
//所有个颜色块全覆盖 1 颜色块 不能两两之间全选 相邻的颜色块之间 每个颜色块可以变色 4 反向 最边缘的不行
//要留一个
//遍历只有一个的 只要是颜色块长度大于1的 都有n个行 最边上的是n-1 所以是5
京东工作强度 418人发布