QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#505859 | #9111. Zayin and String | Lavender_Field | RE | 0ms | 0kb | C++20 | 3.1kb | 2024-08-05 12:33:08 | 2024-08-05 12:33:08 |
answer
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define Mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
using namespace std;
int rd() {
int r = 0; bool w = false; char ch = getchar();
while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
return w ? -r : r;
}
#define MAXN 10000
#define MAXM 10000
#define MAXS 40000
#define MAXW 40000
const int mod = 998244353;
inline int quick_pow( int a , int p ) {
int ret = 1;
for(;p;p>>=1) {
if( p & 1 ) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
}
return ret;
}
char w[MAXW+5]; char s[MAXN+5];
const double INF = 1e12;
const double eps = 1e-6;
int n, m;
struct AC{
int t[MAXS+5][26], tot;
int fail[MAXS+5], val[MAXS+5]; vector<int> to[MAXS+5];
double dp[2][MAXS+5];
// int g[MAXN+5][MAXS+5];
void clear() {
FOR(i,0,tot) {
memset(t[i], 0, sizeof(t[i]));
fail[i] = val[i] = 0;
to[i].clear();
}
tot = 0;
}
void insert( char *s , int V ) {
int len = strlen(s+1);
int u = 0;
FOR(i,1,len) {
if( !t[u][s[i]-'a'] ) t[u][s[i]-'a'] = ++tot;
u = t[u][s[i] - 'a'];
}
val[u] = V;
}
void dfs( int u ) {
for(auto v: to[u]) {
val[v] += val[u];
dfs(v);
}
}
void build() {
queue<int> q; while( !q.empty() ) q.pop();
FOR(i,0,25) if( t[0][i] ) q.push(i), fail[t[0][i]] = 0;
while( !q.empty() ) {
int u = q.front(); q.pop();
FOR(i,0,25) {
if( t[u][i] ) fail[t[u][i]] = t[fail[u]][i], to[t[fail[u]][i]].pb(t[u][i]);
else t[u][i] = t[fail[u]][i];
}
}
dfs(0);
}
bool chk( double x ) {
int r = 0;
FOR(i,0,tot) dp[r][i] = -INF;
dp[r][0] = -eps;
FOR(i,1,n) {
memcpy(dp[r^1], dp[r], sizeof(dp[r]));
int k = s[i] - 'a';
FOR(j,0,tot) {
dp[r^1][t[j][k]] = max(dp[r^1][t[j][k]], dp[r][j] + val[t[j][k]] - x);
}
r ^= 1;
}
FOR(i,0,tot) if( dp[r][i] > 0 ) return true;
return false;
}
int getm( double x ) {
int r = 0;
FOR(i,0,tot) dp[r][i] = -INF;
dp[r][0] = -eps;
FOR(i,1,n) {
memcpy(dp[r^1], dp[r], sizeof(dp[r]));
// memset(g[i], -1, sizeof(g[i]));
int k = s[i] - 'a';
FOR(j,0,tot) {
if( dp[r^1][t[j][k]] < dp[r][j] + val[t[j][k]] - x )
dp[r^1][t[j][k]] = dp[r][j] + val[t[j][k]] - x;
// g[i][t[j][k]] = j;
}
r ^= 1;
}
int pos;
FOR(i,0,tot) if( dp[r][i] >= 0 ) pos = i;
ll now = 0, len = 0;
// ROF(i,n,1) {
// now += (g[i][pos] != -1) ? val[pos] : 0;
// len += (g[i][pos] != -1) ? 1 : 0;
// pos = (g[i][pos] == -1) ? pos : g[i][pos];
// }
return 1ll * now * quick_pow(len, mod-2) % mod;
}
}K;
void solve() {
n = rd(), m = rd();
// K.clear();
scanf("%s", s+1);
FOR(i,1,m) {
scanf("%s", w + 1);
// K.insert(w, rd());
}
// K.build();
double l = 0, r = INF, arge = 0;
while( r - l > eps ) {
double mid = (l + r) / 2;
if( K.chk(mid) ) {
l = mid; arge = mid;
} else r = mid;
}
printf("%d\n", K.getm(arge));
}
int main() {
int T = rd(); while( T-- ) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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...