列表

详情


NC24607. [USACO 2011 Ope S]Forgotten Password

描述

As has happened to so many of us, Bessie has forgotten her cowtube password. She does, however, remember some handy bits of information about it.
First, she remembers that her password (denoted as variable P) has length L (1 <= L <= 1,000) roman characters and can be split into one or more words (not necessarily unique) from a dictionary composed of NW (1 <= NW <= 1,000) unique words. A word W_i is defined as a sequence of 1..20 lowercase letters of the Roman alphabet ('a'..'z').
She also remembers certain letters from her password along with their positions.
Consider the following example. Bessie knows that her password looks like 'a??l?ban???????' ('?' represents a letter she cannot remember), and her dictionary has the following words:
apple cow farmer banana bananas
pies The two possible passwords for Bessie to have are 'applebananapies' and 'applebananascow'.
Given the dictionary, and the letters that Bessie remembers, please find her password. If more than one password is valid, find the lexicographically least string that works.

输入描述

* Line 1: Two space-separated integers: L and NW
* Line 2: A string of length L: P
* Lines 3..NW+2: Line i+2 contains the ith word in the dictionary: W_i

输出描述

* Line 1: The lexicographically least password that fits

示例1

输入:

15 6 
a??l?ban??????? 
apple 
cow 
farmer 
banana 
bananas 
pies 

输出:

applebananapies

原站题解

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

C++14(g++5.4) 解法, 执行用时: 176ms, 内存消耗: 26548K, 提交时间: 2020-03-08 13:40:13

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+100;
string s,a[maxn],dp[maxn];
bool check(int x,int y){
    for (int i = x - a[y].size(), j = 0; i < x; i++, j++)
        if (s[i] != '?' && s[i] != a[y][j])
            return 0;
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m>>s;
    for(int i=1; i<=m; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int L=a[j].size();
            if (L > i || (dp[i - L] == "" && i - L != 0))
                continue;
            if(check(i,j)){
                if(dp[i]==""||dp[i-L]+a[j]<dp[i])
                    dp[i]=dp[i-L]+a[j];
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 183ms, 内存消耗: 1528K, 提交时间: 2020-04-03 09:35:04

#include<bits/stdc++.h>
using namespace std;
char s[1005];
string f[1005],a[1005];
int n,m;
bool check(int x,int y)
{
	for(int i=0;i<a[y].size();i++)
	if(s[x+i+1]!='?'&&s[x+i+1]!=a[y][i])
	return 0;
	return 1;
}
int main()
{
	cin>>n>>m;
	scanf("%s",s+1);
	for(int i=1;i<=m;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		int xx=i-a[j].size();
		if(xx<0||xx&&f[xx].empty())
		continue;
		if(check(xx,j))
		if(f[i].empty()||f[i]>f[xx]+a[j])
		f[i]=f[xx]+a[j];
	}
	cout<<f[n];
	return 0;
}

上一题