日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > 互聯(lián)網(wǎng) > uva 11468 - Substring(AC自動機(jī)+概率)

uva 11468 - Substring(AC自動機(jī)+概率)

來源:程序員人生   發(fā)布時間:2014-09-08 01:35:11 閱讀次數(shù):3814次

題目鏈接:uva 11468 - Substring

題目大意:給出一些字符和各自字符對應(yīng)的選擇概率,隨機(jī)選擇L次后得到一個長度為L的字符串,要求該字符串不包含任意一個子串的概率。

解題思路:構(gòu)造AC自動機(jī)之后,每隨機(jī)生成一個字母,等于是在AC自動機(jī)上走一步,所有子串的結(jié)束位置的節(jié)點(diǎn)標(biāo)記為禁止通行,然后問題轉(zhuǎn)換成記憶搜索處理。

#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int sigma_size = 62; const int maxn = 405;; double pi[sigma_size], dp[maxn][105]; int vis[maxn][105]; int sz; int ac[maxn][sigma_size]; int fail[maxn], last[maxn]; inline int idx (char ch) { if (ch >= '0' && ch <= '9') return ch - '0'; if (ch >= 'a' && ch <= 'z') return ch - 'a' + 10; if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 36; return 0; } void ahoc_insert (char *s) { int u = 0, n = strlen(s); for (int i = 0; i < n; i++) { int v = idx(s[i]); if (ac[u][v] == 0) { last[sz] = 0; memset(ac[sz], 0, sizeof(ac[sz])); ac[u][v] = sz++; } u = ac[u][v]; } last[u] = 1; } void ahoc_fail () { queue<int> que; for (int i = 0; i < sigma_size; i++) { int u = ac[0][i]; if (u) { fail[u] = 0; que.push(u); } } while (!que.empty()) { int r = que.front(); que.pop(); for (int i = 0; i < sigma_size; i++) { int u = ac[r][i]; if (u == 0) { ac[r][i] = ac[fail[r]][i]; continue; } que.push(u); int v = fail[r]; while (v && !ac[v][i]) v = fail[v]; fail[u] = ac[v][i]; last[u] |= last[fail[u]]; } } } void init () { int n, x; char str[sigma_size]; memset(pi, 0, sizeof(pi)); memset(vis, 0, sizeof(vis)); sz = 1; fail[0] = last[0] = 0; memset(ac[0], 0, sizeof(ac[0])); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", str); ahoc_insert(str); } ahoc_fail(); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", str); scanf("%lf", &pi[idx(str[0])]); } } double getProb (int u, int dep) { if (dep == 0) return 1.0; if (vis[u][dep]) return dp[u][dep]; vis[u][dep] = 1; double& ans = dp[u][dep]; ans = 0; for (int i = 0; i < sigma_size; i++) { if (last[ac[u][i]] == 0) ans += pi[i] * getProb(ac[u][i], dep - 1); } return ans; } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { init(); int n; scanf("%d", &n); printf("Case #%d: %.6lf ", kcas, getProb(0, n)); } return 0; }
生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 国产特级毛片aaaaaaa高清 | 国产99久久久久久免费看农村 | 久久久久久久久久久久久九 | 国产美女永久免费 | 中文字幕在线一区 | 亚洲精品一区二区三区 | 日韩欧美亚洲国产精品字幕久久久 | 亚洲成av人片在线观看香蕉 | 亚洲国产精品网站 | 成人毛片网站 | 成人国产亚洲精品a区天堂华泰 | 国产精品黄在线观看 | 成人国产精品久久久 | 欧美在线一区二区三区 | 欧美高清视频在线 | 中文字幕中文字幕 | 久久一区精品 | 91成人免费 | 日本精品免费 | 亚洲电影中文字幕 | 午夜伊人 | 视频一区在线播放 | 黄色三级在线 | 欧美精品福利视频 | 欧美三级网站 | 日韩精品在线看 | 国产日本亚洲 | 成人久久av | 日韩久久久精品 | 国产成人精品免高潮在线观看 | 国产视频久久久久久久 | 国产精品美女久久久久aⅴ国产馆 | 一级毛片免费完整视频 | 91精品国产成人 | 这里只有精品免费视频 | 久热免费视频 | 88888888国产一区二区 | 亚洲视频国产 | 欧美精品在线一区二区 | 亚洲国产日韩精品 | 国产欧美精品国产国产专区 |