列表

详情

NC231682. 特工 007

描述

羊驼 Lucky 是羊驼大陆情报局的特工，代号 "007"。羊驼大陆情报局经常会给特工们分配一些任务，任务分为 26 种，代号分别为 A~Z ，作为羊驼大陆情报局深资老特工的 Lucky 已经完美完成了无数次各类任务了，它曾经甚至和传说中的 "龙神" 对质过 。

然而，人到中年，体力总是力不从心，面对情报局给他安排的任务表，Lucky 逐渐学会了如何摸鱼。具体的，Lucky 已经对 m 种任务感到厌倦、无聊，如果Lucky 在完成当前任务的同时，下一个任务属于这 m 种，那么 Lucky 可以选择去完成任务，也可以选择跳过而去完成下下个任务，而对于其他种类的任务，比如去暗杀 "龙神"，Lucky 觉得还是有那么点意思的，为了给枯燥的生活添加一些乐趣，Lucky 一定会做这种任务。注意: Lucky 在跳过一个任务的时候，必须完成所跳过的任务的后一个任务；如果被跳过的任务为最后一个任务，则所有任务被认为已完成；Lucky 所接到的第一个任务，必须完成，不能跳过。

现在，对于情报局新下发给 Lucky 的任务时间表，Lucky 想要知道他有几种完成整张任务时间表的方案。

答案对 取模。

输入描述

第一行两个整数 n， m （ ） ，表示任务时间表长度为 n，Lucky 对 m 种任务感到厌倦。

第二行一个字符串 s 长度为 n ，保证出现的字符均为大写英文字母。

第三行一个字符串 p 长度为 m，表示 Lucky 厌倦的 m 种任务。

输出描述

一个整数，表示 Lucky 完成整张任务时间表的方案数。

示例1

输入: 

5 1
ABCAB
A

输出: 

2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

pypy3 解法, 执行用时: 616ms, 内存消耗: 140128K, 提交时间: 2021-12-19 17:27:06 

def main():
    n, m = map(int, input().split())
    s = input().strip("\r\n")
    if m > 0:
        ws = input().strip("\r\n")
    else:
        ws = ""
    mod = 10 ** 9 + 7 
    f = [[0] * 2 for _ in range(n)]
    f[0][1] = 1 
    for i in range(1, n):
        if s[i] in ws:
            f[i][0] = f[i - 1][1]
        f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod 
    ans = (f[n - 1][0] + f[n - 1][1]) % mod 
    print(ans)

main()

C++ 解法, 执行用时: 46ms, 内存消耗: 9348K, 提交时间: 2021-12-22 12:02:40 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
string s1,s2;
int dp[1000005];
bool pd[200];
int mod=1e9+7;
signed main(){
cin>>n>>m;
cin>>s1>>s2;
for(int i=0;i<m;i++){
	pd[s2[i]]=1;
}
dp[0]=1;
for(int i=0;i<n-1;i++){
	if(pd[s1[i+1]]){
		dp[i+2]+=dp[i]; 
		dp[i+2]%=mod;
	}
	dp[i+1]+=dp[i];
	dp[i+1]%=mod;
}
printf("%lld",(dp[n]+dp[n-1])%mod);








	return 0;
}

Python3 解法, 执行用时: 1722ms, 内存消耗: 126464K, 提交时间: 2022-04-08 14:46:09 

n,m=map(int,input().split())
s=input()
if m >0:ws=input()
else:ws=""
f=[[0]*2 for _ in range(n)]
mod,f[0][1]=10**9+7,1
for i in range(1,n):#第一个不能跳过，所以不用判断，所以是1~n
  if s[i] in ws:f[i][0]=f[i-1][1]
  f[i][1]=(f[i-1][0]+f[i-1][1]) % mod
print((f[n-1][0]+f[n-1][1]) % mod)

上一题

© 2025 nowcoder.com