QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168494#6635. Strange Keyboarducup-team1209#WA 176ms247360kbC++203.9kb2023-09-08 16:00:162023-09-08 16:00:17

Judging History

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

  • [2023-09-08 16:00:17]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:247360kb
  • [2023-09-08 16:00:16]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ; 
using pi = pair <int, int> ;

void cmn(ll &x, ll y) {
    if(x > y) x = y; 
}
void cmn(int &x, int y) {
    if(x > y) x = y; 
}

cs int N = 1e6 + 5;
cs int M = 5e3 + 5; 

int T; 
int ch[N][26], nd; 
int n, k, m; 
char S[N];

int in[N], out[N], dfn; 
void dfs(int u) {
    in[u] = ++ dfn; 
    for(int i = 0; i < 26; i++)
    if(ch[u][i]) dfs(ch[u][i]);
    out[u] = dfn; 
}

struct ds {
    int n; 
    vector <pi> p; 
    vector <int> st[20]; 

    void ins(int x, int l) {
        p.pb({x, l});
    }
    void build() {
        sort(p.begin(), p.end());
        n = p.size(); 
        for(int i = 0; i < 20; i++)
            st[i].resize(n);
        for(int i = 0; i < n; i++) 
            st[0][i] = p[i].second; 
        for(int i = 1; i < 20; i++)
            for(int j = 0; j + (1 << i) - 1 < n; j++) 
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
    int qmn(int l, int r) {
        auto pl = lower_bound(p.begin(), p.end(), pi(l, 0)) - p.begin();
        auto pr = lower_bound(p.begin(), p.end(), pi(r + 1, 0)) - p.begin();
        // cout << "query " << l << ' ' << r << endl;
        // for(auto [x, l] : p) cout << x << ' ' << l << endl;
        // cout << pl << ' ' << pr << endl;
        if(pl >= pr) return -1; 
        int x = __lg(pr - pl);
        return min(st[x][pl], st[x][pr - (1 << x)]);
    }
    void clear() {
        p.clear();
        for(int i = 0; i < 20; i++) 
            st[i].clear();
        n = 0; 
    }
} t[M];

ll e[M][M];

ll calc() {
    vector <ll> d(m + 1, 1e18);
    d[0] = 0; 
    vector <bool> vis(m + 1);
    for(int i = 0; i <= m; i++) {
        int p = 0;
        ll mn = 1e18;
        for(int j = 0; j <= m; j++)
        if(!vis[j] && (d[j] < mn)) {
            mn = d[j];
            p = j; 
        }
        vis[p] = 1; 
        for(int j = 0; j <= m; j++)
            cmn(d[j], d[p] + e[p][j]);
    }
    return d[m];
}

void Main() {
    scanf("%d%d", &n, &k);
    vector <int> a(n), le(n);
    vector <ll> d(k + 1, 1e18); 
    d[k] = 1; 
    for(int i = 0; i < n; i++) {
        scanf("%s", S);
        int len = strlen(S);
        int x = 0; 
        for(int j = 0; j < len; j++) {
            int c = S[j] - 'a';
            if(!ch[x][c]) ch[x][c] = ++ nd; 
            x = ch[x][c];
        }
        a[i] = x; 
        le[i] = len; 
        cmn(d[k - len % k], (ll) len / k + 2);
    }
    dfs(0);

    for(int i = 0; i < n; i++)
        // cout << i << ' ' << a[i] << ' ' << in[a[i]] << ' ' << le[i] << endl,
        t[le[i] % k].ins(in[a[i]], le[i]);

    for(int i = 0; i < k; i++)
        t[i].build();

    scanf("%s", S);
    m = strlen(S);
    for(int i = 0; i <= m; i++)
        for(int j = 0; j <= m; j++)
            e[i][j] = 1e18; 
    for(int i = 0; i < m; i++) {
        int x = 0; 
        for(int j = i; j < m; j++) {
            int c = S[j] - 'a';
            x = ch[x][c];
            if(x == 0) break;
            int le = (j - i + 1) % k;  
            int len = t[le].qmn(in[x], out[x]);
            if(len != -1) {
                cmn(e[i][j + 1], (ll) (len - (j - i + 1)) / k + 1);
            }
        } 
    }
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= min(i, k); j++)
            cmn(e[i][i - j], d[j]);
    ll ans = calc();
    if(ans < 1e18) {
        cout << ans << '\n';
    }
    else {
        cout << -1 << '\n';
    }
    for(int i = 0; i <= nd; i++) {
        for(int j = 0; j < 26; j++)     
            ch[i][j] = 0; 
        in[i] = out[i] = 0; 
    }
    dfn = nd = 0; 
    for(int i = 0; i < k; i++)
        t[i].clear();
}

int main() {
    #ifdef zqj 
    freopen("1.in","r",stdin);
    #endif
    cin >> T; 
    while(T--) Main();
    return 0; 
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 11864kb

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: 56ms
memory: 208412kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 16ms
memory: 76440kb

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: 28ms
memory: 24884kb

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: 176ms
memory: 247360kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: -100
Wrong Answer
time: 87ms
memory: 85136kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

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