环球消息！ACWING 4261. 孤独的照片

2023-01-09 15:55:26 来源：博客园

题意:

给一个长度为n的只包含"G"和"H"字符串

(资料图)

要求统计所有长度>=3且只有一个不一样的字符的子串个数

思路:

最开始的思路就是

找到一个满足的三个字符

然后向两边扩展

然后就寄了

先不论时间复杂度

每添加一个字符并不是贡献+1

然后就换了一种思路

每次碰到那个特殊字符在中间就向两边扩展看看两边的数字是多少

然后贡献等于x * y

然鹅发现贡献并不是这么多

比如GGHGG的贡献是6

通过这种方法算出来只有4

看了题解

原来还要考虑那个特殊字符在两边的情况

上面那种情况算漏的情况就是GGH和HGG

分别代表特殊字符在最左边和特殊字符在最右边

贡献分别为max(0,y - 1)和max(0,x - 1)

但是我看题解算每个字符两边有各有多少个不同的字符的方法跟我不一样

他是用两个数组预处理了一波就行了

先预处理每个字符左边不同字符数量

如果当前字符是"G"就看当前的h数量如何

同时清零h,g++

如果当前字符是"H"就看当前的g数量如何

同时清零g,h++

右边的预处理反着来就行了

处理完以后就得到了每个字符两边不同字符的长度

然后就累加三种贡献即可

代码:

void solve(){string s1;cin >> n;cin >> s1;s1 = " " + s1;for(int i = 1,g = 0,h = 0;i <= n;i++){if(s1[i] == "G") l[i] = h,h = 0,g++;else l[i] = g,g = 0,h++;}for(int i = n,g = 0,h = 0;i >= 1;i--){if(s1[i] == "G") r[i] = h,h = 0,g++;else r[i] = g,g = 0,h++;}// for(int i = 1;i <= n;i++) cout << l[i] << " ";// cout << endl;// for(int i = 1;i <= n;i++) cout << r[i] << " ";// cout << endl;int ans = 0;for(int i = 1;i <= n;i++){ans += max(r[i] - 1,0ll);ans += max(l[i] - 1,0ll);ans += l[i] * r[i];}cout << ans << endl;}

总结:

这里感觉最难想到的就是用两个数组去统计每个字符左边和右边的连续的不同字符的个数

所以感觉for循环里面套while行不通的话就可以想想这种方法

感觉预处理就比较有用.

关键词：特殊字符分别代表时间复杂度