QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135378#6635. Strange Keyboardnameless_storyTL 833ms10136kbC++201.3kb2023-08-05 14:12:272023-08-05 14:12:30

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 14:12:30]
  • 评测
  • 测评结果:TL
  • 用时:833ms
  • 内存:10136kb
  • [2023-08-05 14:12:27]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define N 1200000

const int INF=0x3f3f3f3f;
int c[N][30],mn[N],tot;

void cmin(int &x,int y) { x=min(x,y); }
void solve()
{
	int n,k; cin>>n>>k;
	for (int i=1; i<=tot; ++i)
	{
		memset(c[i],0,sizeof c[i]);
		mn[i]=INF;
	}
	tot=1;
	vector<string> s;
	vector vis(k,INF);
	for (int i=1; i<=n; ++i)
	{
		string st; cin>>st;
		s.push_back(st);
		cmin(vis[st.size()%k],st.size()/k+1);
	}
	string ss; cin>>ss;
	int m=ss.size();
	vector dp(m+1,INF),f(k+1,INF);
	f[0]=0;
	for (int i=1; i<k; ++i)
	{
		// if (vis[i]==INF) continue;
		for (int j=0; j<k; ++j)
		{
			cmin(f[(i+j)%k],f[j]+vis[i]+(i+j>=k));
		}
		for (int j=0; j<k; ++j)
		{
			cmin(f[(i+j)%k],f[j]+vis[i]+(i+j>=k));
		}
	}
	for (auto st:s)
	{
		int x=1,len=st.size(),step=0;
		for (auto w:st)
		{
			if (!c[x][w]) c[x][w]=++tot;
			x=c[x][w];
			--len;
			cmin(mn[x],f[(k-len%k)%k]+len/k);
		}
	}
	dp[0]=0;
	for (int i=0; i<ss.size(); ++i)
	{
		int x=1;
		for (int j=i; j<ss.size(); ++j)
		{
			int w=ss[j];
			x=c[x][w];
			if (!x) break;
			cmin(dp[j+1],dp[i]+mn[x]+1);
			// f[i][j+1]=mn[x];
		}
	}
	cout<<(dp[ss.size()]==INF?-1:dp[ss.size()])<<'\n';
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin>>T;
	memset(mn,0x3f,sizeof mn);
	while (T--)
	{
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10136kb

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: 84ms
memory: 10076kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 833ms
memory: 9996kb

input:

10
446 4905
afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica
afigcjhcgagabbiccehjcjajigghgbj...

output:

3
2
2
11
6
5
1
1
1
1

result:

ok 10 numbers

Test #4:

score: -100
Time Limit Exceeded

input:

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

output:


result: