ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203870 | #2133. buzz | snow_trace | 100 | 9030ms | 32660kb | C++11 | 1.6kb | 2024-03-24 11:27:56 | 2024-03-24 12:07:37 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1005][1005],prei[1005][1005],prej[1005][1005],ok[1005][1005];
char s[1005],t[1005],res[1005];int n,m;int pi[1005];
signed main(){
scanf("%s",s+1);n = strlen(s+1);
scanf("%s",t+1);m = strlen(t+1);
pi[1] = 0;int j = 0;
for(int i= 2;i<=n;i++){
while(j and t[j+1]!=t[i])j = pi[j];
if(t[j+1] == t[i])j++;pi[i] = j;
}for(int i=0;i<=n;i++)memset(dp,128,sizeof(dp));
dp[0][0] = 0;
for(int i= 1;i<=n;i++){
for(int j =1;j<=m;j++){
if(s[i] == t[j] or s[i] == '?'){
if(dp[i-1][j-1]>dp[i][j]){
prei[i][j] = i-1,prej[i][j] = j-1;ok[i][j] = 1;dp[i][j] = dp[i-1][j-1];
}
}
}dp[i][m]++;
dp[i][0] = dp[i-1][0];prei[i][0] = i-1,prej[i][0] = 0,ok[i][0] = 0;
for(int j =1;j<=m;j++){
if(dp[i][j]>dp[i][0]){
prei[i][0]= i,prej[i][0] = j,ok[i][0] = 0;dp[i][0] = dp[i][j];
}
}
for(int j = pi[m];j;j = pi[j]){
if(dp[i][m]>dp[i][j]){
dp[i][j] = dp[i][m];
prei[i][j] = i,prej[i][j] = m,ok[i][j] = 0;
}
}//for(int j =0;j<=m;j++)cout << dp[i][j] << " ";cout << endl;
}int mxpos =0;for(int i = 0;i<=m;i++)if(dp[n][i]>dp[n][mxpos])mxpos =i ;
// cout << dp[n][m] << endl;
int i = n;j = mxpos;
for(int i= 1;i<=n;i++)res[i] = s[i];
while(i!=0 or j!=0){
// cout << " " << i << " " << j << " " << ok[i][j] << endl;
if(ok[i][j])res[i] = t[j];
int ii = i,jj = j;i = prei[ii][jj],j =prej[ii][jj];
}cout << dp[n][mxpos] << endl;
for(int i= 1;i<=n;i++)if(res[i] == '?')res[i] = 'a';
for(int i =1;i<=n;i++)cout << res[i];
return 0;
}/*
winlose???winl???w??
win
*/
这程序好像有点Bug,我给组数据试试?
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 432ms
memory: 32660kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #2:
score: 0
Accepted
time: 442ms
memory: 32648kb
input:
vlsfijcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
490 vlsfijcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #3:
score: 0
Accepted
time: 453ms
memory: 32652kb
input:
ababababababababababababababaabababababababababaabababababababababababababababababababababababababab...
output:
1 ababababababababababababababaabababababababababaababababababababababababababababababababababababab...
result:
ok good job
Test #4:
score: 0
Accepted
time: 435ms
memory: 21984kb
input:
kqfoatydjehqkwsujxerxpeannihrcevphskryrjbgseewacdcryrzxqqisxkxbdwqrhmuknxefppfxbtvxbqfoatydjehqkwsuj...
output:
5 kqfoatydjehqkwsujxerxpeannihrcevphskryrjbgseewacdcryrzxqqisxkxbdwqrhmuknxefppfxbtvxbqfoatydjehqkws...
result:
ok good job
Test #5:
score: 0
Accepted
time: 437ms
memory: 21844kb
input:
pzaabbaabbcacabccacaaaccbbcbabaabcaccbabbaaaaabbcacabccacaaaccbbcbabaabcaccbabbaaaccabbbcabbaaabbaba...
output:
5 pzaabbaabbcacabccacaaaccbbcbabaabcaccbabbaaaaabbcacabccacaaaccbbcbabaabcaccbabbaaaccabbbcabbaaabba...
result:
ok good job
Test #6:
score: 0
Accepted
time: 563ms
memory: 21832kb
input:
dubaabbcaaabcabaabbcaaabcacbccaacabbccbabcbbcbabbcaabbaaabcabbaabbcbbbccabbcbabcabaccaaabbccabcaaccc...
output:
4 dubaabbcaaabcabaabbcaaabcacbccaacabbccbabcbbcbabbcaabbaaabcabbaabbcbbbccabbcbabcabaccaaabbccabcaac...
result:
ok good job
Test #7:
score: 0
Accepted
time: 653ms
memory: 21592kb
input:
vsvobhthrlknganweporrieihdvqwhjiloujphxktsgojyusvobsvobhthrlknganweporrieihdvqwhjiloujphxsvobhtsvobh...
output:
3 vsvobhthrlknganweporrieihdvqwhjiloujphxktsgojyusvobsvobhthrlknganweporrieihdvqwhjiloujphxsvobhtsvo...
result:
ok good job
Test #8:
score: 0
Accepted
time: 593ms
memory: 21880kb
input:
bacbacbbbbabababaccabcacacbabacbacbbbbabababaccabcacacbccccabcaacccacccbbbaababcccccacccbaaabcaaacaa...
output:
6 bacbacbbbbabababaccabcacacbabacbacbbbbabababaccabcacacbccccabcaacccacccbbbaababcccccacccbaaabcaaac...
result:
ok good job
Test #9:
score: 0
Accepted
time: 504ms
memory: 21652kb
input:
eevlqaabcabcbabbabbccabcbbbacaabbacaacbbabbccacacbcaabbbcbbccaabcabcbabbabbccabcbbbacaabbacaacbbabbc...
output:
4 eevlqaabcabcbabbabbccabcbbbacaabbacaacbbabbccacacbcaabbbcbbccaabcabcbabbabbccabcbbbacaabbacaacbbab...
result:
ok good job
Test #10:
score: 0
Accepted
time: 0ms
memory: 9100kb
input:
l nyrwecxqyldyabnmccgfqzimpvmycmekumsdcunqqxctmplhqytkfmvoomyynhamioueyqeyrcsxcjobvioefuexipfauwlibuxh
output:
0 l
result:
ok good job
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 24ms
memory: 9744kb
input:
aaa?a?aaaa??aa?aaaa?aaaaaaaaaaaaaaaa??aaa?aaa?aaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
result:
ok good job
Test #12:
score: 0
Accepted
time: 27ms
memory: 9712kb
input:
???aa??a?????aaa??aaa?a?aaaaa?aa?a????a?a????a??aa aaaaaaaaaaaaaaaaaaaaaaaaa
output:
26 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
result:
ok good job
Test #13:
score: 0
Accepted
time: 27ms
memory: 9716kb
input:
ababa??babaaba?ababababa?abababa????aba?ab?bab?bab abababababababababababab
output:
1 ababaaababaababababababababababababaabaaababababab
result:
ok good job
Test #14:
score: 0
Accepted
time: 27ms
memory: 9692kb
input:
ssz??os??xozs?osz?xo??szs?o?oszs??szs????zsx?xo?xo szsxo
output:
7 sszsxoszsxozsaoszsxoaaszsxoaoszsxoszsxoaszsxoxoaxo
result:
ok good job
Test #15:
score: 0
Accepted
time: 23ms
memory: 9688kb
input:
bb?bcb?a?cbabcbabcba??bc?cbc??bbb?ab?bcb??ab?abcbo babcb
output:
7 bbabcbbabcbabcbabcbabcbcacbcaabbbbabcbcbaaabbabcbo
result:
ok good job
Test #16:
score: 0
Accepted
time: 30ms
memory: 9692kb
input:
a???cbc?a?b?acbc?a???ba????cb?bb???cbc??????bcbb?? acbcb
output:
6 aacbcbcaaabaacbcbacbcbacbcbcbabbacbcbcacbcbabcbbaa
result:
ok good job
Test #17:
score: 0
Accepted
time: 24ms
memory: 9688kb
input:
ookmo?kokm?aoo?okmqaaook?qaq?ak?kokokokmqaokmq?qaa okmqa
output:
5 ookmoakokmqaooaokmqaaookmqaqaakakokokokmqaokmqaqaa
result:
ok good job
Test #18:
score: 0
Accepted
time: 27ms
memory: 9692kb
input:
c??????aacbcb?b?c?aa???b????c?bc??b??c??c??????caa cbbca
output:
6 cbbcaaaaacbcbcbbcaaaacbbcaaacbbcaabaacbbcacbbcacaa
result:
ok good job
Test #19:
score: 0
Accepted
time: 30ms
memory: 9692kb
input:
cbcbcb?c?cbccb?bcbcb?c?bc?cc?cc?cbc?c?bcbcbcbc?cbc cbcbc
output:
14 cbcbcbccbcbccbcbcbcbcccbcbccaccbcbcbccbcbcbcbcbcbc
result:
ok good job
Test #20:
score: 0
Accepted
time: 0ms
memory: 9100kb
input:
? oktyf
output:
0 a
result:
ok good job
Subtask #3:
score: 60
Accepted
Test #21:
score: 60
Accepted
time: 451ms
memory: 32660kb
input:
aaaaaaaaa??aaa??a?aaaaaa?aa?aaa?aa?a?a?aa?aaaaaaaaaaa?aaaaaaa?a?aa??aa???aaaaaaa?aaaaaaaaaa?aaa?aaaa...
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #22:
score: 0
Accepted
time: 440ms
memory: 32652kb
input:
?r???ckss?w?uwgwzwkaaaaa?aa??aaa????????aa?a?aaaa?aa???a????a?a?a??a?a???aaa?a?aaaaaaaaaa?aaa?a????a...
output:
482 araaackssawauwgwzwkaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #23:
score: 0
Accepted
time: 438ms
memory: 32648kb
input:
ababab??aababa?a?aba???aba??baba??bababab?baba??baba?ab?bababababa?aba?abab?ba?ababaaba?ababab??abab...
output:
177 abababaaaababaaaaabaaaaabaaababaaababababababaaababaaababababababaaabaaabababaaababaabababababab...
result:
ok good job
Test #24:
score: 0
Accepted
time: 437ms
memory: 21780kb
input:
tnv?h?f????????????y?i???jos?????kl??io?i?zgxwixo??ys?a??oq?r?wg???g??wrjv?oj?m??hdsqn?sv?a????v??m?...
output:
5 tnvahafaaaaaaaaaaaayaiaiqjosphzgtklyfioliczgxwixocsysyaaioqrrdwgunygubwrjvgojvmldhdsqnrsvzawawmvkb...
result:
ok good job
Test #25:
score: 0
Accepted
time: 433ms
memory: 21712kb
input:
a?abaaccabaa?cabcbaaa?aaccabaaccabcb??aba?a?baaccbc?caccaaaaaa?aac?aba?cca?cb?cabababbaaccbcc???b?ac...
output:
4 aaabaaccabaaacabcbaaaaaaccabaaccabcbaaabaaaabaaccbcacaccaaaaaaaaacaabaaccaacbacabababbaaccbccaaaba...
result:
ok good job
Test #26:
score: 0
Accepted
time: 437ms
memory: 21868kb
input:
v?a??f??f??a?aa??ab?c??a?a?a????c?bbbcccac?c??b??bcab?c????b?c??cc???a??ca?b??b????cc??b???c?aaa??bc...
output:
4 vaaaafaafaaaaaaaaabacaaaaaaaaaaacabbbcccacacaabaabcabacaaaabacaaccaaaaaacaabaabaaaaccaabaaacaaaaaa...
result:
ok good job
Test #27:
score: 0
Accepted
time: 446ms
memory: 21628kb
input:
bgkigt??bohrv??qsuqzshprdcgcqubel?yychnkfg?jtwruqzhkgdchopl?v??fesuqzshprdcgcqubelfyychnkfgbjtwruqzh...
output:
4 bgkigtaabohrvaaqsuqzshprdcgcqubelayychnkfgajtwruqzhkgdchoplavaafesuqzshprdcgcqubelfyychnkfgbjtwruq...
result:
ok good job
Test #28:
score: 0
Accepted
time: 535ms
memory: 21816kb
input:
hlxw??c?bac???cc?bcaaab??c??ab?c?bab???aabc??abb?a?abba????c?cba????cc????ca?bc??bc??a??cc???b?ca??b...
output:
4 hlxwaacabacaaaccabcaaabaacaaabacababaaaaabcaaabbaaaabbaaaaacacbaaaaaccaaaacaabcaabcaaaaaccaaabacaa...
result:
ok good job
Test #29:
score: 0
Accepted
time: 662ms
memory: 21764kb
input:
??tegoljbjmxsxjyxb?cc?cbbccaabcbac?bbc?cccabac?a?c??abbc?abbcccbcccacbbccaabcccacbcccbcccacbbcc?abcb...
output:
4 aategoljbjmxsxjyxbaccacbbccaabcbacabbcacccabacaaacaaabbcaabbcccbcccacbbccaabcccacbcccbcccacbbccaab...
result:
ok good job
Test #30:
score: 0
Accepted
time: 0ms
memory: 9104kb
input:
? avmchmvshklgvywbukpisrticiapcznpphhzmkseufyxbnmkjzuhwgncnjzfvriamtiwmyjxecikmjfoxzwvvqlzpneizwcwuccv
output:
0 a
result:
ok good job
Extra Test:
score: 0
Extra Test Passed