UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203870#2133. buzzsnow_trace1009030ms32660kbC++111.6kb2024-03-24 11:27:562024-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,我给组数据试试?

Details

小提示:点击横条可展开更详细的信息

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