QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190677#6635. Strange Keyboarducup-team870AC ✓277ms340652kbC++172.3kb2023-09-29 12:31:122023-09-29 12:31:12

Judging History

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

  • [2023-09-29 12:31:12]
  • 评测
  • 测评结果:AC
  • 用时:277ms
  • 内存:340652kb
  • [2023-09-29 12:31:12]
  • 提交

answer

//并没有限制sigma(k)<=5000, k^2过不了 !!!!!!!!
//记串总长为S. 长度不同的串只有O(sqrt(S))个,即最短路的边只有K*sqrt(S)个
//多组数据的最短路复杂度: T*sqrt(1e6/T)*K,T=100时取max,为5e7. 
//记得每轮找最小点的时候不要O(k),虽然过了..... 
//从0到i,走过了哪些边的顺序可以任意换. 因此用每条边更新一遍最短路即可
//字符串前缀匹配的过程用trie模拟即可. 不要用hash+ump(K*K次访问). 其实不用trie,直接ump能过
#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define ll long long
#define vi vector<int>
#define db double
const ll mod=1231453023109121,INF=1e18;
const int N=5005,bs=131,M=1e6+6;
void Min(ll &x,ll y){x=min(x,y);}
char s[M]; string S[M];
ll l[N],dis[N],dp[N][N],ans[N];
int nxt[M][26],cnt=1; ll res[M];
void slv(){
    int n,k;cin>>n>>k;
    rep(i,0,k)l[i]=INF;
    rep(i,1,n){
        cin>>S[i]; int len=S[i].length();
        Min(l[len%k],k+len);
    }
    dis[0]=0; rep(i,1,k-1)dis[i]=INF;
    rep(i,0,k-1){
        if(l[i]==INF)continue;
        int g=__gcd(i,k);
        rep(x,0,g-1){
            for(int j=0;j<k/g*2;j++){
                Min(dis[(x+(j+1)*i)%k], dis[(x+j*i)%k]+l[i]);
            }
        }
    }
    rep(i,0,1e6+2)res[i]=INF;
    rep(i,1,n){
        int now=1,len=S[i].size();
        rep(j,0,len-1){
            int c=S[i][j]-'a';
            if(!nxt[now][c])nxt[now][c]=++cnt;
            now=nxt[now][c];
            int le=len-1-j,x=((-le)%k+k)%k;
            if(dis[x]<INF)Min(res[now],(dis[x]+le)/k+1);
        }
    }
    cin>>s+1; int m=strlen(s+1); //下次用n吧..
    rep(l,1,m)rep(r,l,m)dp[l][r]=INF;
    rep(l,1,m){
        int now=1;
        rep(r,l,m){
            now=nxt[now][s[r]-'a'];
            if(!now)break;
            dp[l][r]=res[now];
        }
    }
    rep(i,0,cnt)memset(nxt[i],0,sizeof nxt[i]); cnt=1;
    rep(i,1,m){
        ans[i]=dp[1][i];
        rep(j,1,i-1)Min(ans[i], ans[j]+dp[j+1][i]);
    }
    cout<<(ans[m]>=INF?-1:ans[m])<<'\n';
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}
/*
1
2 3
defgh
abc
abcde
*/

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 47716kb

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: 79ms
memory: 240604kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

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: 277ms
memory: 55204kb

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: 107ms
memory: 268504kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 57ms
memory: 118836kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

4287
228
3671
549
129
372
475
534
336
288

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 95ms
memory: 62144kb

input:

100
7 4807
abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb
aaaaababaaab...

output:

45
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
116
1
-1
293
519
5
160
15
126
13
31
619
4...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 70ms
memory: 340652kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 58ms
memory: 266172kb

input:

1
100000 4817
acdcaaccca
cdbbbbabba
bcbccbcdbd
cdabaddaad
ddbdbabcac
dadadbbcba
aabcbbcabc
cdcadbbbda
dabacdbabd
dcbadbdabd
cdcbacbada
cadbbadbac
dbadbccdcd
babaddcdca
aaaddacccc
dabdcdadbb
abbbadbdaa
bcdbbacdaa
bcbcbddadb
bddaccbaba
baddadaaac
adbadbdaaa
cacbbbcdbc
abccdcacdb
abaacddbbc
acbbbcbcdc
...

output:

618356

result:

ok 1 number(s): "618356"

Test #10:

score: 0
Accepted
time: 31ms
memory: 152312kb

input:

10
3901 4952
srsofqyvrt
tazndzviuq
jcomfoxkiw
huzfqiecss
hhdtqpaohy
qcrokphbtf
xzkxssibix
hokmdpzydu
jreaeulsjt
vmxdsazajq
jawyofqbck
cwmzupygdm
rgsahqyxqt
kckgorfgvi
kcawvezmyb
mpcyhdifgn
xiwtmwttmp
mzknfqoifl
vbpvvdnqpy
anpdgjnbew
scekjovqpr
lzhfocjvld
oswjfhjdby
pmdbjddkpv
yjbnjcdtmc
gmpjgtpksa
r...

output:

904
208656
4560
30873
28272
5377
1326
93956
93720
282610

result:

ok 10 numbers