QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554720#9111. Zayin and StringPurslaneWA 550ms6016kbC++142.0kb2024-09-09 15:00:542024-09-09 15:00:56

Judging History

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

  • [2024-09-09 15:00:56]
  • 评测
  • 测评结果:WA
  • 用时:550ms
  • 内存:6016kb
  • [2024-09-09 15:00:54]
  • 提交

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'