QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466372#6635. Strange Keyboarducup-team191#TL 1444ms410136kbC++232.9kb2024-07-07 18:52:382024-07-07 18:52:38

Judging History

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

  • [2024-07-07 18:52:38]
  • 评测
  • 测评结果:TL
  • 用时:1444ms
  • 内存:410136kb
  • [2024-07-07 18:52:38]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=5010,MOD=1e9+7,B1=32984723,B2=345932;
const char en='\n';
const ll LLINF=1ll<<60;

void ad(int&a,int b)
{
	a+=b;
	if (a>=MOD) a-=MOD;
}

int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

void su(int&a,int b)
{
	a-=b;
	if (a<0) a+=MOD;
}

int sub(int a,int b)
{
	if (a<b) return a-b+MOD;
	return a-b;
}

int mul(int a,int b)
{
	return (a*1ll*b)%MOD;
}

int pot(int n,int k)
{
	if (k==0) return 1;
	int r=pot(n,k/2);
	r=mul(r,r);
	if (k%2) r=mul(r,n);
	return r;
}

using hashtype=unsigned long long;

void dod(hashtype&a,char c)
{
	//a={add(mul(a.x,B1),c),add(mul(a.y,B2),c)};
	a=a*B1+c;
}

const bool DEB=0;
string re;
ll t,di[N],rr[N],n,k,dp[N],di2[N][N];
hashtype hashdef;
bool bio[N];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (DEB) t=1;
	else cin>>t;
	while (t--)
	{
		if (DEB) n=5e3,k=5000;
		else cin>>n>>k;
		vector<string> v(n);
		for (auto&x: v)
		{
			if (DEB)
			{
				x="";
				for (int z=0;z<199;++z) x.pb(rand()%26+'a');
			}
			else cin>>x;
		}
		if (DEB)
		{
			re="";
			for (int i=0;i<5000;++i) re.pb(rand()%26+'a');
		}
		else cin>>re;
		for (int i=0;i<k;++i) di[i]=LLINF,rr[i]=LLINF,bio[i]=0;
		for (auto x: v) di[x.size()%k]=min(di[x.size()%k],(int)x.size()+k);
		rr[0]=0;
		for (int z=0;;++z)
		{
			ll nm=LLINF;
			int kak=-1;
			for (int i=0;i<k;++i) if (!bio[i] && rr[i]<nm)
			{
				nm=rr[i];
				kak=i;
			}
			if (kak==-1) break;
			bio[kak]=1;
			for (int i=kak;i<k;++i) rr[i]=min(rr[i],rr[kak]+di[i-kak]);
			for (int i=0;i<kak;++i) rr[i]=min(rr[i],rr[kak]+di[i+k-kak]);
		}
		vector<pair<hashtype,ll>> mo;
		for (auto x: v)
		{
			hashtype ha=hashdef;
			int xs=x.size();
			for (int i=0;i<xs;++i)
			{
				dod(ha,x[i]);
				int moo=((i+1-xs)%k+k)%k;
				if (rr[moo]==LLINF) continue;
				ll co=(rr[moo]+xs-(i+1))/k+1;
				//mo.pb({ha.x*1ll*MOD+ha.y,co});
				mo.pb({ha,co});
			}
		}
		sort(all(mo));
		int rs=re.size();
		for (int i=0;i<=rs;++i) dp[i]=LLINF;
		vector<pair<hashtype,int>> sv;
		sv.reserve(rs*(rs+1)/2);
		for (int i=0;i<rs;++i)
		{
			hashtype ha=hashdef;
			for (int j=i;j<rs;++j)
			{
				dod(ha,re[j]);
				//sv.pb({ha.x*1ll*MOD+ha.y,i*rs+j});
				sv.pb({ha,i*rs+j});
				di2[i][j]=LLINF;
			}
		}
		sort(all(sv));
		int p1=0;
		for (auto x: sv)
		{
			while (p1<(int)mo.size() && mo[p1].x<x.x) ++p1;
			if (p1<(int)mo.size() && mo[p1].x==x.x) di2[x.y/rs][x.y%rs]=mo[p1].y;
		}
		dp[0]=0;
		for (int i=0;i<rs;++i)
		{
			for (int j=i;j<rs;++j)
			{
				dp[j+1]=min(dp[j+1],dp[i]+di2[i][j]);
			}
		}
		if (dp[rs]==LLINF) cout<<-1<<en;
		else cout<<dp[rs]<<en;
	}
}

詳細信息

Test #1:

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

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: 1444ms
memory: 410136kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 578ms
memory: 90956kb

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: