Main » 2013 September 27 » [NOIP2011模拟赛_No.7]忘记的密码
3:45 PM [NOIP2011模拟赛_No.7]忘记的密码 |
忘记的密码(1A)#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #define N 1010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; string S[N],T; string dp[N]; int n,m; int check(int p,string s) { int i; FOR(i,0,s.size()-1) { if (T[i+p]=='?') continue; if (T[i+p]!=s[i]) return 0; } return 1; } int main() { ios::sync_with_stdio(false); cin>>n>>m; cin>>T; int i,j; FOR(i,1,m) cin>>S[i]; sort(S+1,S+1+m); FOR(i,1,n) {dp[i]="";FOR(j,0,19) dp[i]+="z";} dp[0]=""; FOR(i,0,n-1) if (T[i]=='?') { FOR(j,1,m) { int L=S[j].size(); if (check(i,S[j])) if ((dp[i]+S[j])<dp[i+L]) dp[i+L]=dp[i]+S[j]; } }else FOR(j,1,m) { int L=S[j].size(); if (S[j][0]==T[i]) if (check(i,S[j])) if ((dp[i]+S[j])<dp[i+L]) dp[i+L]=dp[i]+S[j]; } cout<<dp[n]<<endl; } |
|
|
| Total comments: 0 | |