题解

1 条题解

  • 0
    @ 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

信息

ID
2531
难度
9
分类
搜索 | 枚举组合数学 点击显示
标签
递交数
2
已通过
1
通过率
50%
被复制
4
上传者