牛客534819680号
2021-04-09 13:19 北京航空航天大学 算法工程师
关注
将串分成四类：
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)
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
爱奇艺公司氛围 53人发布 05-26 10:24
门头沟学院 Java 
点赞 评论 收藏
分享
05-15 19:57
西安建筑科技大学 Java 
那一天的Java_Java起来：他本来公司就是做这个的，不就是正常的游戏客户端和服务器开发，软硬件联动，有啥恶心不恶心的，提前告诉你就是怕你接受不了，接受不了就没必要再往后走流程浪费时间，虽然这公司是一坨。 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 考研对你找工作产生了哪些影响？ #
14488次浏览 136人参与
# 你的房租占工资的比例是多少？ #
28906次浏览 304人参与
# 聊聊这家公司值得去吗 #
254488次浏览 2340人参与
# 找实习你看重大厂光环还是业务方向 #
8244次浏览 72人参与
# 职场捅娄子大赛 #
366721次浏览 3753人参与
# 你最满意的offer薪资是哪家公司？ #
26858次浏览 143人参与
# 每人推荐一个小而美的高薪公司 #
74458次浏览 1363人参与
# kpi面有什么特征 #
40301次浏览 327人参与
# 打杂的实习你会去吗？ #
111495次浏览 970人参与
# 机械应届生薪资要多少才合适？ #
22769次浏览 92人参与
# 你有哪些缓解焦虑的方法？ #
8271次浏览 267人参与
# 大家实习每天都在干啥 #
81159次浏览 500人参与
# 来聊聊机械薪资天花板是哪家 #
123795次浏览 739人参与
# 米哈游工作体验 #
15642次浏览 112人参与
# 秋招前后对offer的期望对比 #
290791次浏览 2176人参与
# 为了找工作你投递了多少公司？ #
17448次浏览 247人参与
# 机械人的薪资开到多少，才适合去？ #
109644次浏览 449人参与
# 机械只有读研才有出路吗？ #
20226次浏览 230人参与
# 小米求职进展汇总 #
827233次浏览 5928人参与
# 硬件/芯片公司工作体验 #
76169次浏览 670人参与