(以“分类:组合数学 ==摘要== {{信息题|Subsequences Of Substrings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}506|1|100|没有用lld|10|time=2015...”为内容创建页面) |
小 (→题解: 格式) |
||
第9行: | 第9行: | ||
xbaax | xbaax | ||
baa | baa | ||
− | + | 容易得到方案数为2*2=4种 | |
+ | |||
*栗子2: | *栗子2: | ||
xbaaxbaax | xbaaxbaax | ||
baa | baa | ||
− | + | 容易得到方案数为对于第一个baa,方案数为2*6种,第二个baa,除去之前算过的,共4*2种,合起来共20种。 | |
+ | |||
+ | *栗子3: | ||
+ | xbaaa | ||
+ | baa | ||
+ | 容易得到方案数为2*2=4种(按照最前的匹配运算即可) | ||
− | + | 类比得到匹配一段字符串从索引i至索引j,其方案数为: | |
(s1.size()-j)*(i-last)//last为上一个i | (s1.size()-j)*(i-last)//last为上一个i | ||
− | + | 统计求和即可<ref>http://vawait.com/sgu-506/</ref>,详见代码。 | |
+ | |||
==代码== | ==代码== | ||
{{折叠|506.cpp代码已折叠 | {{折叠|506.cpp代码已折叠 |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
Subsequences Of Substrings | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-22 21:08:21 | 没有用lld(10) |
(AC 458)
给定字符串s1,s2,要求s1首尾去除若干连续位后,s2仍然是s1的子串(子串的定义是s1移除若干位后为s2,如ac是abc的子串)。
- xbaax
- baa
容易得到方案数为2*2=4种
- xbaaxbaax
- baa
容易得到方案数为对于第一个baa,方案数为2*6种,第二个baa,除去之前算过的,共4*2种,合起来共20种。
- xbaaa
- baa
容易得到方案数为2*2=4种(按照最前的匹配运算即可)
类比得到匹配一段字符串从索引i至索引j,其方案数为:
- (s1.size()-j)*(i-last)//last为上一个i
统计求和即可[1],详见代码。
506.cpp代码已折叠
展开折叠内容
|
---|
显示/移除行号
|