XHRlyb和她的小伙伴Cwbc在玩捉迷藏游戏。
Cwbc藏在多个不区分大小写的字符串中。
好奇的XHRlyb想知道，在每个字符串中Cwbc作为子序列分别出现了多少次。
由于Cwbc可能出现的次数过多，你只需要输出每个答案对2000120420010122取模后的结果。
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！
[编程题]躲藏
今天是dp喵，简单喵~想象一下，本喵在字符串里寻找“Cwbc”这四个字符组成的序列（不区分大小写哦~）。代码里用四个变量来跟踪本喵找到了多少种“半成品”序列：dp0：记录找到的 'c' 开头数量（这是第一步喵~）dp1：记录找到的 'cw' 组合数量（已经有点完整的雏形啦！）dp2：记录找到的 'c
展开全文
这道题需要格外注意一句话：
不区分大小写。
所以考虑设 dpi,0/1/2/3dp_{i,0/1/2/3}dpi,0/1/2/3 表示以 iii 结尾，最后一位恰好匹配到 cwbc 的第 0/1/2/30/1/2/30/1/2/3 个字符的方案数。
然后稍微压一下状态，写出状态转移方程：（代码
展开全文
import sys
MOD = 2000120420010122
for line in sys.stdin:
a = line.strip().lower()
ans = 0
c = 0
cw = 0
cwb = 0
for x in a:
展开全文
dp数组的含义：匹配到子串当前位置的子序列的个数。也就是说dp[2]意思是匹配到'b'这个字符的子序列个数是多少，匹配到b，那么前面一定是有cw的，所以当前dp[2]+=dp[1]状态转移方程为：dp[i]+=dp[i-1]但是注意若当前字符与前面有字符相同，也就是这里判断到c时dp[0]要继续自增
展开全文
还是挺典的一个子序列动态规划的，就是用dp[i]表示以Cwbc中第i个位置结尾的子序列个数就好了
唯一要注意的点是这里不区分大小写
// BggBB wZPXsv:. UBgQGv
// BgEQQ
展开全文
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 200012042
展开全文
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5, M = 2000120420010122;
ll f[N];
int main() {
ios::s
展开全文
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=2000120420010122;
void solv
展开全文
//算法学习第四题，DP
#include <bits/stdc++.h>
using namespace std;
//using ll=long long;
const long long MOD = 2000120420010122;
//int 最大只有 $2 \times 1
展开全文
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
