abb
难度：3星
提示 1：对于每个字母 ch，找到后面和 ch 不等的两个相等字母的个数 cnt 即可，贡献为
Ccnt2=cnt∗(cnt−1)/2C_{cnt}^2=cnt*(cnt-1)/2Ccnt2=cnt∗(cnt−1)/2
提示 2：快速得出每个 cnt 的方式：开一个后缀和数组
展开全文
题意整理。
给定长度为n的字符串。
求"abb"型子序列的个数。
方法一（后缀和数组）
1.解题思路
首先进行预处理，得到对应的后缀和数组。
suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数，所以可以在O(1)O(1)O(1)时间内，获得当前字母之后的对应字母出现次数。
展开全文
简单易懂思路：用abb中第一个出现的b来考虑，一个字符作为第一b能产生的abb字符，等于它后面相同的字符数量（意味着还能凑成多少个bb）乘以它前面与它不相同的字符数量（可以被当作a的）。于是先记录每一个字符总出现的次数。然后再遍历字符串记录每个字符已经出现的次数和后面还没出现的次数。
#includ
展开全文
cnt[i] 表示在索引为0~i-1 之间小写字母出现的次数，i-cnt[i]表示除了这个字符以外其他字符的数量，这样我们就可以统计出像 ab这样的字符串有多少个
使用dp[i]记录 0~i-1 之间 以字符s[i]结尾的字符串有多少
#include<stdio.h>
int ma
展开全文
描述
给一个长度为nnn的字符串，问有多少个形式为abb的子序列
思路
一个比较常见的动态规划题目，设dp[i][j]dp[i][j]dp[i][j]表示区间[1,i][1,i][1,i]中以字母jjj为结尾，有多少个形式为ab的子序列，则对于字符串sss最终的答案为∑i∈[1,n]dp[i−1
展开全文
开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列
展开全文
n = int(input())
if n < 3:
print(0)
else:
s = input()
dp = [{} for i in range(n)] # dp[i]记录i之后各个字母出现的次数
ans = 0
for i in range
展开全文
统计每个字符串开始的叠词数量
while True:
try:
n = int(input())
sn = input()
dp = [0 for _ in range(n)] # 用来存放当前i坐标字符串开头的叠词数量
di
展开全文
n = int(input())
s = input()
#回溯
# result = []
# path = []
# def back(s):
# if len(path) == 3 and path[0]!=path[1] and path[1] == path[2
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
