QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#622034 | #9111. Zayin and String | black_king1 | WA | 118ms | 11076kb | C++17 | 3.7kb | 2024-10-08 19:35:59 | 2024-10-08 19:36:00 |
Judging History
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'