QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135345#6635. Strange KeyboardPlentyOfPenalty#WA 51ms100848kbC++202.0kb2023-08-05 13:56:202023-08-05 13:56:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 13:56:21]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:100848kb
  • [2023-08-05 13:56:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6,MK=5000;
const long long INF=1e18;
int Q,n,K,m,len[N+10],c[N+10][26],vis[N+10][26],ap[MK+10],cnt,TIM,tmp;
long long mn[MK+10],g[MK+10],cst[N+10],dp[MK+10];
string s[N+10],T;
void Ins(int x,int id,int nw){
	//cout<<"INS "<<x<<" "<<id<<","<<nw<<"\n";
	cst[x]=min(cst[x],g[K-(len[id]-nw)%K]+1+1+(len[id]-nw)/K);
	//cout<<"CST="<<cst[x]<<"\n";
	if(nw==len[id])return;
	int t=s[id][nw]-'a';
	if(vis[x][t]!=TIM)vis[x][t]=TIM,c[x][t]=++cnt,cst[cnt]=INF;
	Ins(c[x][t],id,nw+1);
}
int main(){
#ifdef memset0
	freopen("E.in","r",stdin);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>Q;
	while(Q--){
		cin>>n>>K;
		++TIM;
		for(int i=1;i<K;++i)mn[i]=g[i]=INF;
		//cin>>s[0];
		for(int i=1;i<=n;++i){
			cin>>s[i];
			//s[i]=s[0];
			len[i]=s[i].size();
			mn[len[i]%K]=min(mn[len[i]%K],1ll+len[i]/K);
			ap[len[i]%K]=TIM;
		}
		// for(int i=1;i<K;++i)
		// 	if(ap[i]){
		// 		long long t=mn[i]*2;
		// 		for(int j=2,l=(i<<1)%K;j<K;++j,t+=mn[i]){
		// 			mn[l]=min(mn[l],t);
		// 			if(t>INF)break;
		// 			if((l+=i)>=K)l-=K;
		// 		}
		// 	}
		// for(int i=1;i<K;++i)for(int j=0,t=i;j<K;++j,((++t)==K?t=0:0)){
		// 	g[t]=min(g[t],g[j]+mn[i]);
		// }
		for(int i=K-1;i>=1;i--){
			if(mn[i]==INF)continue;
			for(int j=2;;j++)
				if(i*j>=K){
					mn[i*j%K]=min(mn[i*j%K],mn[i]*j);
					break;
				}else{
					mn[i*j]=min(mn[i*j],mn[i]*j);
				}
		}
		g[K]=-1;
		for(int i=0;i<K;i++)g[i]=mn[i];
		//for(int i=0;i<K;++i)cout<<"G "<<i<<"="<<g[i]<<"\n";
		cnt=1;
		for(int i=1;i<=n;++i)Ins(1,i,0);
		cin>>T,m=T.size();
		for(int i=1;i<=m;++i)dp[i]=INF;
		for(int i=0;i<m;++i)if(dp[i]!=INF){
			tmp=1;
			//cout<<"DP "<<i<<"="<<dp[i]<<"\n";
			for(int j=i+1;j<=m;++j){
				if(vis[tmp][T[j-1]-'a']!=TIM)break;
				tmp=c[tmp][T[j-1]-'a'];
				dp[j]=min(dp[j],dp[i]+cst[tmp]);
			}
		}
		cout<<(dp[m]==INF?-1ll:dp[m])<<endl;
	}
	return 0;
}
/*
2
2 3
defgh
abc
abcde
1 1
a
b
*/

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 39844kb

input:

2
2 3
defgh
abc
abcde
1 1
a
b

output:

3
-1

result:

ok 2 number(s): "3 -1"

Test #2:

score: 0
Accepted
time: 13ms
memory: 41612kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 14ms
memory: 41048kb

input:

10
446 4905
afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica
afigcjhcgagabbiccehjcjajigghgbj...

output:

3
2
2
11
6
5
1
1
1
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 11ms
memory: 40996kb

input:

100
140 4879
baabaababbababbaabababaaababbbabbbbbbabbababbbabbbbabbbbbbaabbbbbbbbabaabbbaabaabbbaabbabaabaabbbabbbababbbaabbabaaaaabbaaabbbabb
baa
baabaababbababbaabababaaababbbabbbbbbabbab
baabaababbababbaabababaaabab
baabaababbababbaabababaaababbbabbb
baabaababbababbaabababaaababbbabbbbbbabbababbb...

output:

1
1
1
1
3
1
1
1
1
1
1
3
2
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
4
3
2
1
2
1
1
1
1
1
2
1
1
1
3
1
1
1
2
1
1
1
2
3
1
1
1
2
1
1
1
1
1
1
1
1
3
2
3
1
3
1
1
2
1
2
3
2
1
1
1
3
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
2
1
4
1

result:

ok 100 numbers

Test #5:

score: -100
Wrong Answer
time: 51ms
memory: 100848kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

203

result:

wrong answer 1st numbers differ - expected: '205', found: '203'