QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488054#6635. Strange Keyboarducup-team052#WA 341ms56480kbC++231.9kb2024-07-23 15:45:332024-07-23 15:45:33

Judging History

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

  • [2024-07-23 15:45:33]
  • 评测
  • 测评结果:WA
  • 用时:341ms
  • 内存:56480kb
  • [2024-07-23 15:45:33]
  • 提交

answer

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

const int N = 1e6 + 5, M = 5005;
const int inf=0x3f3f3f3f;

char s[N];
int len[N],n,k,dis[M];
int ch[N][26],w[N],dep[N],cnt,m,mnl[M];
vector<int> v[N];
int f[M];
vector<int> can;
struct Node
{
	int id,val;
	Node(int a=0,int b=0) {id=a,val=b;}
	bool operator < (const Node &x) const {return val>x.val;}
};
void init()
{
	for(int i=0;i<k;i++) dis[i]=inf;
	dis[0]=0;
	priority_queue<Node> q;
	q.emplace(0,0);
	while(!q.empty())
	{
		auto [v,w]=q.top(); q.pop();
		if(dis[v]!=w) continue;
		for(int l:can)
		{
			int tl=(v+l)%k;
			int tw=dis[v]+(v+mnl[l])/k;
			if(dis[tl]>tw) dis[tl]=tw,q.emplace(tl,tw);
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		w[i]=inf;
		for(int j:v[i])
		{
			int cl=(len[j]-dep[i]);
			int cw=cl/k+dis[cl%k];
			w[i]=min(w[i],cw);
		}
	}
}
void ins(int len,int id)
{
	int cur=0;
	for(int i=1;i<=len;i++)
	{
		if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++cnt,dep[cnt]=dep[cur]+1;
		cur=ch[cur][s[i]-'a'];
		v[cur].push_back(id);
	}
}

void work()
{
	cin>>n>>k;
	for(int i=0;i<=cnt;i++) for(int j=0;j<26;j++) ch[i][j]=0;
	cnt=0;
	for(int i=0;i<k;i++) mnl[i]=inf;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		len[i]=strlen(s+1);
		mnl[len[i]%k]=min(mnl[len[i]%k],len[i]);
		ins(len[i],i);
	}
	can.clear();
	for(int i=0;i<k;i++) if(mnl[i]!=inf) can.push_back(mnl[i]);
	// for(int i:can) printf("%d ",i); cout<<"\n";
	init();
	scanf("%s",s+1); m=strlen(s+1);
	f[0]=0; for(int i=1;i<=m;i++) f[i]=inf;
	for(int i=0;i<m;i++)
	{
		if(f[i]==inf) continue;
		int cur=0;
		for(int j=i+1;j<=m;j++)
		{
			if(!ch[cur][s[j]-'a']) break;
			cur=ch[cur][s[j]-'a'];
			f[j]=min(f[j],f[i]+1+w[cur]);
		}
	}
	if(f[m]==inf) printf("-1\n");
	else printf("%d\n",f[m]);
}

int main() {
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	int T;
	scanf("%d", &T);
	while (T--) {
		work();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9936kb

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: 31ms
memory: 18104kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 97ms
memory: 15300kb

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: 341ms
memory: 14812kb

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

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

127

result:

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