QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181925#6635. Strange Keyboarducup-team134WA 823ms215976kbC++146.1kb2023-09-17 04:04:532023-09-17 04:04:54

Judging History

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

  • [2023-09-17 04:04:54]
  • 评测
  • 测评结果:WA
  • 用时:823ms
  • 内存:215976kb
  • [2023-09-17 04:04:53]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=1e6+10;
ll inf=2e18;


const int maxalp=30;
int link[maxn],nxt[maxn][maxalp],isleaf[maxn],cnt=1,root=0;
int par[maxn],cpar[maxn],len[maxn];
ll val[maxn];

void ins(int x,string &s,vector<ll>&cost){

    int c=0;
    while(1){

        if(c==s.size()){
            return;
        }

        int sc=s[c]-'a';

        if(nxt[x][sc]==-1){
            par[cnt]=x;
            cpar[cnt]=sc;
            len[cnt]=c+1;
            nxt[x][sc]=cnt++;
        }

        x=nxt[x][sc];
        val[x]=min(val[x],cost[c]);
        c=c+1;
    }
}
int get_link(int x);
int get_nxt(int x,int c){
    if(nxt[x][c]!=-1)return nxt[x][c];
    if(x==0)return 0;
    return nxt[x][c]= get_nxt(get_link(x),c);
}
int get_link(int x){
    if(link[x]!=-1)return link[x];
    if(x==0)return -1;
    if(par[x]==0)return 0;
    return link[x]=  get_nxt(get_link(par[x]),cpar[x]);
}
void reset_aho(){


    for(int i=0;i<cnt;i++){
        link[i]=-1;
        for(int j=0;j<maxalp;j++)nxt[i][j]=-1;
        val[i]=inf;
        len[i]=-1;
    }
    cnt=1;

}



struct bla{

    vector<int>a;
    int pt=0;

    void clear(){
        a.clear();
        pt=0;
    }
    void pop_front(){
        pt++;
    }
    void pop_back(){
        a.pop_back();
        if(a.size()<pt)pt=a.size();
    }
    void push_back(int c){
        a.pb(c);
    }
    int size(){
        return max((int)a.size()-pt,0);
    }
    int front(){
        return a[pt];
    }
    int back(){
        return a.back();
    }


}deq[maxn];


int e=0;
int n,k;
const int maxk=5010;
string s[maxn];
ll dp[maxn*2];
ll rdp[maxn];
/*void upd_dp(int w,int c){

    for(int i=0;i<w;i++)deq[i].clear();

    int msum=w*c+k;

    if(e)printf("%d %d  WC\n",w,c);

    for(int i=0;i<msum;i++)tmp[i]=inf;
    for(int i=0;i<msum;i++){

        if(e){

            for(int j=1;j<=c;j++){
                if(i-j*w>=0)tmp[i]=min(tmp[i],min(dp[i],dp[i-j*w]+j) );
            }

        }
        else{
            int cid=i%w;
            while(deq[cid].size() && (i-deq[cid].front())/w>c)deq[cid].pop_front();

            int id=-1;
            if(deq[cid].size())id=deq[cid].front();

            if(id!=-1)tmp[i]=min(dp[i], dp[id]+((i-id)/w) );

            while(deq[cid].size() && (dp[deq[cid].back()]+(ll)(i-deq[cid].back()))/w>=dp[i] ){
                deq[cid].pop_back();
            }
            deq[cid].push_back(i);
        }

    }

    /// preradi tmp
    for(int i=0;i<msum;i++)
        if(tmp[i]!=inf)
            dp[i%k]=min(dp[i%k],tmp[i]+(ll)i/k);

}*/
int pcnt=0;
void upd_dp(int w,int pp){

    int msum=2*k;

    //if(e)printf("%d %d  WC\n",w,c);

    ll pom=w/k+pp;
    w%=k;

    for(int i=k-1;i>=0;i--){
        dp[i+w]=min(dp[i+w],dp[i]+1+pom);
        ///pcnt++;
    }

    /*/// preradi tmp
    for(int i=0;i<k;i++){
        ///pcnt++;
        if(tmp[i]!=inf)
            dp[i]=min(dp[i],tmp[i]);
    }*/

    for(int i=0;i<k;i++){
        ///pcnt++;
        dp[i]=min(dp[i],dp[k+i]+1);
    }
}

int main(){

    memset(link,-1,sizeof(link));
    memset(nxt,-1,sizeof(nxt));
    memset(len,-1,sizeof(len));
    for(int i=0;i<maxn;i++)val[i]=inf;

    ///freopen("test.txt","r",stdin);

    int t;
    scanf("%d",&t);
    if(t==10)e=1;
    while(t--){

        scanf("%d %d",&n,&k);

        pcnt=0;

        vector<int>cand;
        int sum=0;
        int pb[2]={0,0};
        for(int i=1;i<=n;i++){
            cin>>s[i];
            cand.pb(s[i].size());
            sum+=s[i].size();

            if(e){
                pb[s[i][0]-'a']=1;
            }
        }
        for(int i=0;i<=sum;i++)dp[i]=inf;
        reset_aho();
        sort(cand.begin(),cand.end());
        vector<pii>cand2;

        cand2.pb({cand[0],1});
        for(int i=1;i<cand.size();i++){
            if(cand[i]==cand2.back().ff)cand2[cand2.size()-1].ss++;
            else cand2.pb({cand[i],1});
        }

        ///printf("OP\n");

        dp[0]=0;
        for(int i=0;i<cand2.size();i++){

            int x=cand2[i].ff;
            for(int j=0;(1<<j)<=k;j++){
                upd_dp((1<<j)*x,1<<j);

            }
            pcnt++;

        }

        ///printf("OP\n");

        for(int i=1;i<=n;i++){
            vector<ll>cost;
            for(int j=0;j<s[i].size();j++){
                ll d=((int)s[i].size())-j-1;
                ll cc=d/k;
                d%=k;
                if(d==0){
                    cost.pb(cc+1);
                    continue;
                }
                d=(k-d)%k;
                cost.pb(dp[d]+cc+2);
            }
            if(e){
                //printf("%lld %c | %d COST\n",cost[0],s[i][0],s[i].size()%k);
            }
            ins(root,s[i],cost);
        }

        ///printf("OPALA\n");

        if(e){
            ///for(int i=1;i<cnt;i++)val[i]=1;
        }

        string qr;
        cin>>qr;
        int curr=root;
        for(int i=1;i<=qr.size();i++)rdp[i]=inf;
        rdp[0]=0;
        for(int i=1;i<=qr.size();i++){

            curr=get_nxt(curr,qr[i-1]-'a');

            int pom=curr;
            while(pom!=root){
                rdp[i]=min(rdp[i],rdp[ i-len[pom]]+val[pom]);
                pom=get_link(pom);
            }

        }

        if(e){
           // printf("%d %d PBPB\n",pb[0],pb[1]);
        }

        if(rdp[qr.size()]>=inf)printf("-1\n");
        else printf("%lld\n",rdp[qr.size()]);


       // if(e)printf("%d CCC\n",pcnt);

    }

    //if(e)printf("%d CCC\n",pcnt);

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 24ms
memory: 198996kb

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: 127ms
memory: 208456kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 278ms
memory: 200048kb

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: 823ms
memory: 199256kb

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: -100
Wrong Answer
time: 87ms
memory: 215976kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

207

result:

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