zhangxyhp

摘要： 一.前言 早就學(xué)了掃描線了，但是有一道題當(dāng)時沒做，現(xiàn)在才做，于是就來寫寫學(xué)習(xí)筆記。 哎我學(xué)習(xí)筆記前面咋老是這么多廢話啊 二.定義 掃描線其實是一種思想，就是遍歷某個值并將其加入數(shù)據(jù)結(jié)構(gòu)，同時動態(tài)地解決一些問題。 聽起來很抽象，那就看例題吧。 三.例題 [poj1151]亞特蘭蒂斯 求矩形面積并。想象 閱讀全文

摘要： 考慮如果暴力 DP，設(shè) \(f_{i,j}\) 為當(dāng)前的串長為 \(i\)，在 AC 自動機(jī)的 \(j\) 節(jié)點的概率。轉(zhuǎn)移時枚舉在后面加的字符 \(k\)，如果加上 \(k\) 后匹配上了一個禁忌串就直接回到根節(jié)點，同時給答案貢獻(xiàn)，否則就繼續(xù)匹配。\(len\) 在 \(10^9\)，時間復(fù)雜度會 閱讀全文

摘要： 設(shè) \(dp_{i,j,S}\) 表示填了 \(i\) 位，在 AC 自動機(jī)上的 \(j\) 號節(jié)點，當(dāng)前覆蓋的字符串集位 \(S\) 的方案數(shù)。于是有轉(zhuǎn)移： \[\large{dp_{i,j,S}\to dp_{i+1,tr_{j,k},S\operatorname{or}sta_{tr_{j,k 閱讀全文