QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#622034#9111. Zayin and Stringblack_king1WA 118ms11076kbC++173.7kb2024-10-08 19:35:592024-10-08 19:36:00

Judging History

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

  • [2024-10-08 19:36:00]
  • 评测
  • 测评结果:WA
  • 用时:118ms
  • 内存:11076kb
  • [2024-10-08 19:35:59]
  • 提交

answer

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

const int mod=998244353;

int calc(char c){
    return c-'a';
}

inline int fpow(int x, int t = mod - 2) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}

struct ACAM{
    struct node{
        int son[26],trans[26];int fail=0;double val=0;double ans=-1e9;int trueans=0;int len=0;
    };
    node trie[4000+10];
    int cnt=0;int rt=0;
    int res=0;
    void initial(){
        rt=0;cnt=0;
        res=0;
        for(int i=0;i<=4000;i++){
            memset(trie[i].son,0,sizeof(trie[i].son));
            memset(trie[i].trans,0,sizeof(trie[i].trans));
            trie[i].fail=0;trie[i].val=0;
            trie[i].ans=-1e9;trie[i].trueans=-1e9;
            trie[i].len=0;
        }
    }

    void insert(string str,int val){
        int p=rt;
        for(auto s:str){
            if(!trie[p].son[calc(s)]){
                trie[p].son[calc(s)]=++cnt;
            }
            p=trie[p].son[calc(s)];
        }
        trie[p].val=val;
    }
    void build(){
        queue<int> q;q.push(rt);
        while(!q.empty()){
            int te=q.front();
            node cur=trie[te];
            q.pop();
            for(int i=0;i<26;i++){
                if(cur.son[i]){
                    node temp=trie[cur.son[i]];
                    temp.fail=cur.fail;
                    while(temp.fail&&!trie[temp.fail].son[i]){
                        temp.fail=trie[temp.fail].fail;
                    }
                    if(te&&trie[temp.fail].son[i]){
                        trie[cur.son[i]].fail=trie[temp.fail].son[i];
                    }
                    trie[cur.son[i]].val+=trie[trie[cur.son[i]].fail].val;
                    trie[te].trans[i]=trie[te].son[i];
                    q.push(cur.son[i]);
                }
                else{
                    trie[te].trans[i]=trie[trie[te].fail].trans[i];
                }
            }
        }
    }

    bool check(string str,double x){
        res=0;
        for(int i=0;i<=cnt;i++){trie[i].ans=-1e9;trie[i].trueans=0;trie[i].len=0;}
        trie[0].ans=0;trie[0].trueans=0;trie[0].len=0;
        for(auto s:str){
            for(int i=cnt;i>=0;i--){
                if(trie[i].ans>-1e9){
                    node* temp=&(trie[trie[i].trans[calc(s)]]);
                    if(trie[i].ans+temp->val-x>temp->ans){
                        temp->ans=trie[i].ans+temp->val-x;
                        temp->trueans=(1ll*(trie[i].trueans)+((int)temp->val))%mod;
                        temp->len=trie[i].len+1;
                    }
                }
            }   
        }
        for(int i=1;i<=cnt;i++){
            if(trie[i].ans>=0){res=i;return true;}
        }
        return false;
    }

    int cal(){
        return 1ll*trie[res].trueans*fpow(trie[res].len)%mod;
    }
    void print(){
        for(int i=0;i<=20;i++){
            printf("%d %d\n",trie[i].trueans,trie[i].len);
        }
    }
};

ACAM dir;
string arr[200000+10];

int main(){
    int t;scanf("%d",&t);
    while(t--){
        dir.initial();
        int n,m;scanf("%d%d",&n,&m);
        string s;cin>>s;
        for(int i=1;i<=m;i++){
            cin>>arr[i];
            int val;scanf("%d",&val);
            dir.insert(arr[i],val);
        }
        dir.build();
        double l=0.0,r=1e5+0.0, eps=1e-8;
        while(r-l>eps){
            double mid=(l+r)/2;
            if(dir.check(s,mid)){l=mid;}
            else{r=mid;}
        }
        dir.check(s,l);
        //dir.print();
        printf("%d\n",dir.cal());
    }
    
    
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 118ms
memory: 11076kb

input:

80
4 7
ggeg
g 92946
d 65678
gg 50828
wrj 93954
gge 53780
a 94179
geg 40837
5 6
hiiii
ii 67984
foh 69185
hi 88153
pj 39431
i 32219
wfmve 96834
8 12
wvxxvwww
xw 1522
rzl 16262
wx 77596
v 69622
vw 82225
nykkmkv 19236
xv 83470
o 16781
w 2405
m 98319
ww 13889
qggbvty 16331
8 14
jjjiiijh
i 96670
z 74397
i...

output:

332874949
86864
249640519
499244123
665548146
81272
61572
67112
499196918
748779217
88888
831949361
74929
665552405
499139737
665543594
332830174
60785
748771076
63646
103574
101389
97767267
332787384
665596551
89874
110460
499215461
665540622
41750
732199036
96189
101652
94537
83443
111657
66556009...

result:

wrong answer 2nd lines differ - expected: '599030808', found: '86864'