QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122711#6635. Strange Keyboardinstallb#TL 282ms58208kbC++142.0kb2023-07-10 22:39:472023-07-10 22:39:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 22:39:49]
  • 评测
  • 测评结果:TL
  • 用时:282ms
  • 内存:58208kb
  • [2023-07-10 22:39:47]
  • 提交

answer

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

#define int long long

const int INF = 0x3f3f3f3f3f3f3f3f;

string s[5005];
int len[5005];
int f[5005],g[5005];

// trie
int rt,tot;
int ch[27][2000005],val[2000005];

void solve(){
    rt = 1; tot = 1;

    int n,k;
    cin >> n >> k;
    for(int i = 0;i < k;i ++) len[i] = INF;
    len[0] = 0;
    for(int i = 1;i <= n;i ++){
        cin >> s[i];
        int l = s[i].length();
        len[l % k] = min(len[l % k],l);
    }
    for(int i = 0;i < k;i ++) f[i] = INF;
    f[0] = 0;
    for(int i = 1;i < k;i ++){
        for(int j = 0;j <= 4 * k * i;j += i){
            f[(j + i) % k] = min(f[(j + i) % k],f[j % k] + len[i] / k + 1 + (j + i >= k));
        }
    }

    // for(int i = 0;i < k;i ++) cout << len[i] << " \n"[i == k - 1];
    // for(int i = 0;i < k;i ++) cout << f[i] << " \n"[i == k - 1];

    for(int i = 1;i <= n;i ++){
        int l = s[i].length();
        int now = rt;
        for(int j = 0;j < l;j ++){
            int x = s[i][j] - 'a';
            if(!ch[x][now]) ch[x][now] = ++ tot;
            now = ch[x][now];
            int d = (k - (l - j - 1) % k) % k;
            val[now] = min(val[now],1 + (l - j - 1 + k - 1) / k + f[d]);
        }
    }

    string t;
    cin >> t;
    int lt = t.length(); t = ' ' + t;
    g[0] = 0;
    for(int i = 1;i <= lt;i ++) g[i] = INF;
    for(int i = 0;i < lt;i ++){
        int now = rt;
        for(int j = i + 1;j <= lt;j ++){
            int x = t[j] - 'a';
            if(!ch[x][now]) break;
            now = ch[x][now];
            g[j] = min(g[j],g[i] + val[now]);
        }
    }
    if(g[lt] == INF) g[lt] = -1;
    cout << g[lt] << '\n';

    // clear
    for(int i = 1;i <= tot;i ++){
        for(int j = 0;j < 26;j ++) ch[j][i] = 0;
        val[i] = INF;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    memset(val,0x3f,sizeof(val));
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 58208kb

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: 282ms
memory: 22808kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: -100
Time Limit Exceeded

input:

10
446 4905
afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica
afigcjhcgagabbiccehjcjajigghgbj...

output:

3
2
2
11
6

result: