QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620242#9111. Zayin and StringMu_SilkWA 596ms123036kbC++202.9kb2024-10-07 17:08:212024-10-07 17:08:22

Judging History

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

  • [2024-10-07 17:08:22]
  • 评测
  • 测评结果:WA
  • 用时:596ms
  • 内存:123036kb
  • [2024-10-07 17:08:21]
  • 提交

answer

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

const int N=1000010;

const ll M=998244353;
ll qpow(ll a,ll b){
    ll ans=1;
    while (b){
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans;
}

struct node{
    ll value=0;
    int next[26]={0};
    int fail;
}tree[N];
int cnt=0;

void clear(){
    for(int i=0;i<=cnt;i++){
        tree[i].value=0;
        fill(tree[i].next,tree[i].next+26,0);
        tree[i].fail=0;
    }
    cnt=0;
}

void insert(const string& s,ll v){
    int n=s.size();
    int cur=0;
    for(int i=0;i<n;i++){
        if(tree[cur].next[s[i]-'a']==0){
            tree[cur].next[s[i]-'a']=++cnt;
        }
        cur=tree[cur].next[s[i]-'a'];
    }
    tree[cur].value+=v;
}

void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(tree[0].next[i]!=0){
            tree[tree[0].next[i]].fail=0;
            q.push(tree[0].next[i]);
        }
    }
    while(q.size()>0){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(tree[x].next[i]!=0){
                tree[tree[x].next[i]].fail=tree[tree[x].fail].next[i];
                q.push(tree[x].next[i]);
            }
            else tree[x].next[i]=tree[tree[x].fail].next[i];
        }
    }
    for(int i=0;i<=cnt;i++){
        tree[i].value+=tree[tree[i].fail].value;
    }
}

struct Node{
    double v;
    ll a,b;  
};

int n,m;
string s;
Node p[2][N];

ll ans=0;

bool check(double x){
    int cur=0;
    for(int i=0;i<=cnt;i++)p[cur][i]={-1e18,0,0};
    p[cur][0]={0,0,0};
    for(int i=0;i<s.size();i++){
        for(int j=0;j<=cnt;j++)p[cur^1][j]=p[cur][j];
        for(int j=0;j<=cnt;j++){
            int nxtj;
            if(tree[j].next[s[i]-'a']>0)nxtj=tree[j].next[s[i]-'a'];
            else nxtj=tree[j].fail;
            if(p[cur^1][nxtj].v<=p[cur][j].v+tree[nxtj].value-x+1e-8){
                p[cur^1][nxtj].a=p[cur][j].a+tree[nxtj].value;
                p[cur^1][nxtj].b=p[cur][j].b+1;
                p[cur^1][nxtj].v=p[cur][j].v+tree[nxtj].value-x;
            }
        }
        cur^=1;
    }
    for(int i=0;i<=cnt;i++){
        if(p[cur][i].v>=0&&p[cur][i].b>0){
            ans=p[cur][i].a*qpow(p[cur][i].b,M-2)%M;
            // cout<<p[cur][i].v<<" "<<p[cur][i].a<<" "<<p[cur][i].b<<"\n";
            return 1;
        }
    }
    return 0;
}


void solve(){
    clear();
    cin>>n>>m;
    cin>>s;
    for(int i=0;i<m;i++){
        string t;ll v;
        cin>>t>>v;
        insert(t,v);
    }
    build();
    ans=0;
    double l=0,r=1e18;
    while(r-l>1e-8){
        double m=(r+l)/2.0;
        if(check(m))l=m;
        else r=m;
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    cin>>n;
    while(n--)solve();
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 596ms
memory: 123036kb

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
599030808
249640519
332898173
665548146
81272
61572
67112
499196918
748779217
88888
831949361
74929
249622595
499139737
665543594
748765364
60785
748771076
63646
103574
101389
465960640
332787384
249703944
89874
110460
499215461
665540622
41750
78985770
96189
111031999
94537
83443
111657
6...

result:

wrong answer 14th lines differ - expected: '665552405', found: '249622595'