小H和密码

链接:https://www.nowcoder.com/acm/contest/72/B
来源:牛客网

题目描述

    小H在击败怪兽后,被一个密码锁挡住了去路
    密码锁由N个转盘组成,编号为1~N,每个转盘有M个位置,每个位置上要么有一个小写字母,要么没有任何字符。一个密码能被转盘表示出,当且仅当指定每个转盘上面的某一个位置,然后将这些位置按照所属的转盘编号顺次连接(空位置直接忽略),可以得到这个密码
    小H并没有得到任何线索,因此只能猜,她一共猜了Q次,但并不知道自己猜的密码能否被表示出来,于是她向你求助

输入描述:

第1行,三个整数N,M,Q
第2~N+1行,每行一个长度为M的字符串,依次表示每个转盘上的字符
第N+2~N+Q+1行,每行一个长度不超过10000的字符串,表示小H猜的密码
2≤N,Q≤300,2≤M≤27,同一个转盘上每种字符最多出现一次

输出描述:

输出Q行,每行都是YES或NO,依次表示小H猜的每个字符串能否被表示出

输入例子:
3 2 3
a#
ab
bc
aa
bb
ba
输出例子:
NO
YES
NO

-->

示例1

输入

3 2 3
a#
ab
bc
aa
bb
ba

输出

NO
YES
NO

备注:

#表示空字符

分析:

用贪心确定每个密码盘选哪个字符是错误的

递归肯定超时,剪枝都补救不了

所以这题看起来字符串模拟的题,居然要用dp写。。。

考虑DP,设dp[i][j]表示前i个密码盘,有j个选了某个小写字母的方案     时间复杂度O(N^2Q)

则决策只有当前密码盘选择空字符或者小写字母两种

用桶记录每个位置有哪些可用字母,询问串过长直接输出NO

重点:初始化+bool传递

小H和密码

所以第二位选0个的项都设为1

看别人代码,学了一招,传递可行性用&1,很骚


#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
typedef long long ll;
#define inf 2147483647
#define ri register int int n,m,q;
int str[][];
int dp[][];
char ss[maxn],s[maxn]; int main()
{
// freopen("test.txt","r",stdin);
// freopen("outout.txt","w",stdout);
cin>>n>>m>>q;
for(int i=; i<=n; i++)
{
scanf("%s",ss);
for(int j=; j<strlen(ss); j++)
{
if(ss[j]=='#')
str[i][]=;
else str[i][ss[j]-'a'+]=;
}
}
while(q--)
{
memset(dp,,sizeof(dp));
scanf("%s",s+);
int len=strlen(s+);
if(len>n){
cout<<"NO"<<endl;
continue;
}
for(int i=; i<=n; i++)
dp[i][]=;
for(int i=; i<=n; i++)
for(int j=; j<=i; j++)
{
if(str[i][s[j]-'a'+])
dp[i][j]=dp[i-][j-]&;
if(str[i][]&&!dp[i][j])
dp[i][j]=dp[i-][j]&;
}
if(dp[n][len])
cout<<"YES";
else cout<<"NO";
cout<<endl;
}
return ;
}

上一篇:easyui combobox下拉框文字超出宽度有横向滚轮


下一篇:js与jquery中html() text() val()中的区别