QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554720 | #9111. Zayin and String | Purslane | WA | 550ms | 6016kb | C++14 | 2.0kb | 2024-09-09 15:00:54 | 2024-09-09 15:00:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2000+10,MAXM=10000+10,MOD=998244353;
int T,n,m,v[MAXN],tot=1,tr[MAXM][27],fail[MAXM],pre[MAXM];
string S,w[MAXN];
int qpow(int base,int p) {
int ans=1;
while(p) {
if(p&1) ans=ans*base%MOD;
base=base*base%MOD,p>>=1;
}
return ans;
}
void insert(string S,int v) {
int u=1;
for(auto ch:S) {
if(!tr[u][ch-'a']) tr[u][ch-'a']=++tot;
u=tr[u][ch-'a'];
}
return pre[u]+=v,void();
}
void build(void) {
queue<int> q;
ffor(i,0,25) if(tr[1][i]) fail[tr[1][i]]=1,q.push(tr[1][i]);
else tr[1][i]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
pre[u]+=pre[fail[u]];
ffor(i,0,25) if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
else tr[u][i]=tr[fail[u]][i];
}
return ;
}
ld dp[2][MAXM];
int rl[2][MAXM],s[2][MAXM];
pair<ld,pair<int,int>> query(ld del) {
ffor(i,1,tot) dp[0][i]=dp[1][i]=-10000000000,rl[0][i]=rl[1][i]=s[0][i]=s[1][i]=0;
dp[0][1]=0;
ffor(i,1,n) {
ffor(j,1,tot) dp[i&1][j]=dp[(i-1)&1][j],rl[i&1][j]=rl[(i-1)&1][j],s[i&1][j]=s[(i-1)&1][j];
ffor(j,1,tot) {
int t=tr[j][S[i]-'a'];
if(dp[(i-1)&1][j]+pre[t]-del>dp[i&1][t]) dp[i&1][t]=dp[(i-1)&1][j]+pre[t]-del,rl[i&1][t]=(rl[(i-1)&1][j]+pre[t])%MOD,s[i&1][t]=s[(i-1)&1][j]+1;
}
}
ffor(i,1,tot) if(dp[n&1][i]>0) return {dp[n&1][i],{rl[n&1][i],s[n&1][i]}};
return {0,{0,0}};
}
int solve(void) {
ld L=0,R=300000000;
int ans=0;
while(R-L>1e-7) {
ld mid=(L+R)/2;
auto pr=query(mid);
if(pr.first>0) ans=pr.second.first*qpow(pr.second.second,MOD-2)%MOD,L=mid;
else R=mid;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>T;
while(T--) {
cin>>n>>m>>S;
ffor(i,1,m) cin>>w[i]>>v[i];
memset(tr,0,sizeof(tr)),memset(fail,0,sizeof(fail)),memset(pre,0,sizeof(pre)),tot=1;
ffor(i,1,m) insert(w[i],v[i]);
build();
cout<<solve()<<'\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 550ms
memory: 6016kb
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:
118360 83207 665575476 332898173 665548146 81272 0 0 73114 95033 88888 599022153 249597926 665552405 9252 665543594 332830174 60785 332832625 63646 103574 101389 432700990 332787384 133436 89874 94158 499215461 665540622 41750 782592345 96189 374456533 94537 46762 93595 665560098 21918 62015 6655738...
result:
wrong answer 1st lines differ - expected: '332874949', found: '118360'