QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#466372 | #6635. Strange Keyboard | ucup-team191# | TL | 1444ms | 410136kb | C++23 | 2.9kb | 2024-07-07 18:52:38 | 2024-07-07 18:52:38 |
Judging History
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...