QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135744#6635. Strange KeyboardPhantomThresholdTL 952ms45252kbC++202.0kb2023-08-05 23:31:482023-08-05 23:31:58

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 23:31:58]
  • 评测
  • 测评结果:TL
  • 用时:952ms
  • 内存:45252kb
  • [2023-08-05 23:31:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1010000;
const int maxt = 5050;
const int inf  = 1e9;

int n,K;
int len[maxn],id[maxn];
int rt,tr[maxn][26],fa[maxn],f[maxn],tot;
int newnode()
{
	++tot;
	for(int i=0;i<26;i++) tr[tot][i]=0;
	fa[tot]=0;
	f[tot]=inf;
	return tot;
}
int dis[maxt],a[maxt];
vector<int>ai;
priority_queue< pair<int,int> >q;

string T; int tn;
int g[maxt];

signed main()
{
	ios_base::sync_with_stdio(false);
	int Tcase; cin>>Tcase;
	
	int flag=1;
	if(Tcase!=100) flag=0;
	while(Tcase--)
	{
		cin>>n>>K;
		
		if(flag && Tcase==99 && n==7 && K == 4807) flag=1;
		else flag=0;
		
		for(int i=0;i<K;i++) a[i]=inf;
		tot=0;
		rt=newnode();
		for(int i=1;i<=n;i++)
		{
			string str; cin>>str;
			len[i]=str.size();
			a[len[i]%K]= min( a[len[i]%K], len[i]/K+1 );
			
			if(flag) continue;
			int now=rt;
			for(auto c:str)
			{
				int j=c-'a';
				if(!tr[now][j]) 
				{
					tr[now][j]=newnode();
					fa[tr[now][j]]=now;
				}
				now=tr[now][j];
			}
			id[i]=now;
		}
		cin>>T; tn=T.size();
		
		ai.clear();
		for(int k=0;k<K;k++) if(a[k]!=inf) ai.push_back(k);
		sort(ai.begin(),ai.end());
		
		for(int i=0;i<K;i++) dis[i]= inf;
		dis[0]=0; q.push( make_pair( dis[0],0 ) );
		while(!q.empty())
		{
			auto [D,i]= q.top(); q.pop();
			if( D!=dis[i] ) continue;
			for(auto k:ai)
			{
				int j= (i+k)%K, jc=D+a[k]+(i+k>=K);
				if( dis[j]>jc )
				{
					dis[j]=jc;
					q.push(make_pair(dis[j],j));
				}
			}
		}
		
		if(flag) continue;
		
		for(int i=1;i<=n;i++)
		{
			int l=0,x=id[i];
			while(x!=rt)
			{
				f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
				x=fa[x]; l++;
			}
		}
		
		for(int i=0;i<=tn;i++) g[i]=inf;
		g[0]=0;
		for(int i=0;i<tn;i++)
		{
			int now=rt;
			for(int j=1;j<=tn-i;j++)
			{
				int c=T[i+j-1]-'a';
				if(tr[now][c]==0) break;
				now=tr[now][c];
				g[i+j]=min(g[i+j],g[i]+1+f[now]);
			}
		}
		cout<< (g[tn]==inf?-1:g[tn]) <<'\n';
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 11664kb

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: 17ms
memory: 11928kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 47ms
memory: 11880kb

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: 163ms
memory: 11932kb

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: 0
Accepted
time: 175ms
memory: 45252kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 952ms
memory: 41140kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

4287
228
3671
549
129
372
475
534
336
288

result:

ok 10 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

100
7 4807
abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb
aaaaababaaab...

output:

32
11
4
2475
132
50
330
20
6
99
25
126
6
4
14
74
108
208
11
5
67
166
2822
178
1307
548
92
386
493
279
2415
255
262
567
215
46
113
31
651
17
4
8
21
12
100
69
152
15
55
521
146
11
13
181
-1
442
1839
2
5
31
26
122
696
280
77
1
839
11
273
7
178
421
228
6
6
82

result: