1 条题解
-
0
何老师 (root) LV 0 MOD @ 2024-11-05 11:11:41
设给出序列为:s[1]..s[N]
对于前4个测试点:
暴力枚举子串的左下标i和右下标j,然后再统计s[i]..s[j]中间的'H'和'G'的数量,再判定是否孤独照片,时间复杂度\(O(n^3)\)。
对于前5~10个测试点:
用前缀和优化:sum1[i]表示s[1]..s[i]中'G'数量,sum2[i]表示s[1]..s[i]中'H'数量,所以判定s[i]..s[j]是否孤独用前缀和判定即可,时间复杂度 \(O(n^2)\)。
对于11~15个测试点:
枚举i=3..N,求s[1]..s[i]中以s[i]为结尾的孤独串的数量,即sum1[1..i-3]中值为(sum1[i]-1)的元素个数(因为前缀和sum1[1..N]都是非递减序列,可STL查找),对于sum2[]类似。时间复杂度 \(O(NlogN)\)$更高效算法:可以用尺取法计算sum1[1..i-3]中值为(sum1[i]-1)的元素个数,时间复杂度O(N)。
- 1