将串分成四类: 1. 没有3连 + 末尾两个数字不同, A[L] 2. 没有3连 + 末尾两个数字相同, B[L] 3. 恰有1个3连 + 末尾两个数字不同, C[L] 4. 恰有1个3连 + 末尾两个数字相同, D[L] 有如下递推关系: A[2] = S * (S - 1) B[2] = S C[2] = 0 D[2] = 0 令R = S - 1以方便书写 A[L+1] = A[L] * R + B[L] * R B[L+1] = A[L] C[L+1] = C[L] * R + D[L] * R D[L+1] = B[L] + C[L] 最后输出结果C[L] + D[L]之和即可。 时间复杂度为O(L)
点赞 评论

相关推荐

05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
点赞 评论 收藏
分享
那一天的Java_Java起来:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务