本文主要是介绍蓝桥集训之孤独的照片，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥集训之孤独的照片
-
核心思想：贡献法
- 遍历每一个字符 求出其左右边与之不同的的连续字符数量
- 最终答案为 l * r + l–1 + r–1
-
#include<iostream>using namespace std;const int N = 500010;typedef long long LL;int n;char str[N];int l[N],r[N];int main(){cin>>n>>str;for(int i=0,h=0,g=0;i<n;i++) //h记录遍历到的h数量{if(str[i] == 'G') l[i] = h,h=0 , g++; //连续h数量清空else l[i] = g,g=0, h++;}for(int i=n-1,h=0,g=0;i>=0;i--) //反向遍历 找右边不同的{if(str[i] == 'G') r[i] = h,h = 0,g++;else r[i] = g, h++ ,g = 0;}LL res=0;for(int i=0;i<n;i++)res += (LL)l[i] * r[i] + max(l[i] -1,0) + max(r[i] -1,0); //r[i]/l[i]可能为0 cout<<res;}
这篇关于蓝桥集训之孤独的照片的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
