WC2017 Day1
WC2017 Day1
字符串算法
0x00 字符串的性質(zhì)
- 字符串的周期（period）:例如abcabca 周期為3
- 字符串的border ：相同前后綴
- 顯然如果一個(gè)長為s字符串有長度為r的border，則其有長度為s-r的period
border有什么用？KMP
- 后綴數(shù)組：可以求兩個(gè)子串的最長公共前綴（LCP）
LCP和周期性：如果一個(gè)字符串有周期p，則i與i+p的LCP為s-p-i+1
- Weak Periodicity Lemma：p和q都是s的周期，p+q<=|s|，則gcd(p,q)也是s的周期
- Periodicity Lemma（周期引理）：p和q都是s的周期，p+q-gcd(p,q)<=|s|，則gcd(p,q)也是s的周期
這兩個(gè)定理都十分顯然，弱化版可以先證p-q也是周期，然后輾轉(zhuǎn)相減，標(biāo)準(zhǔn)版不予證明
- 字符串匹配 引理：u,v滿足2|u|>=|v|，則u在v中所有匹配位置組成一個(gè)等差數(shù)列，用border的性質(zhì)和周期引理可證
- border的結(jié)構(gòu)：s所有不小于|s|/2的border長度構(gòu)成等差數(shù)列，同樣用border性質(zhì)和周期引理可證
把border按長度分類：[1,2),[2,4),[4,8)…….每一類里長度都是等差數(shù)列，則周期也有類似性質(zhì)（這一個(gè)沒聽懂，下面所有涉及這個(gè)的都沒懂）
- 如果|v|>=|w|/2，|v|是2的冪次，且w,v都是s的子串，如何求v在w中的匹配位置？
可以用類似倍增求后綴數(shù)組的做法，把w中長度為|v|的拎出來排序
0x01 字符串循環(huán)移位
- 字符串的循環(huán)移位：一般有n種，如果最小周期p|n，則只有p種不同的循環(huán)移位，每種出現(xiàn)n/p次
- 循環(huán)同構(gòu)？破環(huán)成鏈，在鏈上匹配（等差數(shù)列）
- 可以優(yōu)化，需要用到上面沒聽懂的那個(gè)性質(zhì)
0x02 回文串
- Manacher
回文樹
- 引理：s是回文串，s的后綴（前綴）t是回文串當(dāng)且僅當(dāng)t是s的border，用顯然法證明
推論：任意字符串所有回文后綴的長度是logn個(gè)等差數(shù)列（又是你！）
最小回文串拆分：manacher+dp，dp[i]=min{dp[j]+1，s[j..i]是回文串}，復(fù)雜度O(N^2)，可以用上面的推論優(yōu)化成nlogn
- 判斷是否存在非平凡（l>=2）回文串拆分：顯然有個(gè)n^2 dp做法，和上面的問題一樣，然而存在線性做法
- 顯然的想法：維護(hù)從每個(gè)點(diǎn)出發(fā)的最短（>=2）回文串，貪心取最短串，嘗試證明：
- 設(shè)從一點(diǎn)出發(fā)實(shí)際段長為d，最短段長為f[i]
- 若f[i]>=d/2 可以找到一個(gè)更短的前綴回文串：d-f[i]是周期=>2(d-f[i])是周期=>d-2(d-f[i])是border=>d-2(d-f[i])是一個(gè)更短的前綴回文串，這里要特判d=2f[i]-1的情況
- 若f[i]i],f[i]+1..d-f[i],d-f[i]+1..d，都是回文串，這里要特判d=2f[i]+1的情況
單純貪心不太好使，三種情況，O(3)轉(zhuǎn)移dp
- 雙回文串：a,b都是回文串，則ab是一個(gè)雙回文串
- s=x1x2=y1y2=z1z2，如果y1,y2,x2,z1都是回文串，x1
- 判斷s能否拆成不超過4個(gè)回文串？
窮舉中間斷點(diǎn)，判斷前后能否用兩個(gè)以內(nèi)的回文串組成，預(yù)處理。
0x03 字典序
- 全是后綴數(shù)組，沒怎么聽懂
Ulam 猜數(shù)游戲
0x00 內(nèi)容
- 回答方選擇一個(gè)數(shù)x
- 詢問方詢問一個(gè)集合s，回答方回答x是否在s內(nèi)
- 回答方可以撒謊不超過k次
- 回答方可以變更選擇的數(shù)(必須合法)
- 拓展：詢問必須事先確定（離線詢問）
0x01 策略
先考慮離線情況
提問方
樸素策略:每次詢問二進(jìn)制位上的一位，每次詢問重復(fù)k+1次，最壞次數(shù)是$ \left ( k+1 \right ) \log_2{n}+1\(，對所有k和離線都適用，離線的話要詢問k+2次，最壞次數(shù)\)\left ( k+2 \right ) \log_2{n}$
- 0 1 2 3 4 5 6 7
- 1 3 5 7 倒數(shù)第一位為1？
- 2 3 6 7 倒數(shù)第二位為1？
- 4 5 6 7 倒數(shù)第三位位1？
問題轉(zhuǎn)化
- 傳輸一個(gè)長為$ log_2{n}$的01串，傳輸有噪音，有不超過k位被修改
- k=1的情況
- 算法0:樸素算法，每個(gè)位置詢問3次
- 算法1:每個(gè)位置詢問2次，加一個(gè)奇偶校驗(yàn)，詢問最終01串中1的奇偶性
- 算法2:每個(gè)位置詢問1次，把詢問位置1到n標(biāo)號，設(shè)立$ log_2(log_2{n}+1)$個(gè)奇偶校驗(yàn)，第k個(gè)奇偶校驗(yàn)用于檢查二進(jìn)制位上第k位為1的位置構(gòu)成的串的奇偶性，同時(shí)對整個(gè)串設(shè)一個(gè)奇偶校驗(yàn)
- 算法3:hamming code
細(xì)化模型
- 是一個(gè)信道編碼問題
- 編碼 傳輸 譯碼
編碼要求:傳輸過程中受到噪聲影響仍能正確譯碼
等價(jià)于將n維空間中的$ 2^n$個(gè)點(diǎn)映射到m個(gè)點(diǎn)上
在線情況
- k=1時(shí)，離線與在線算法的最優(yōu)解滿足:在線<=離線<=在線+1，我不會證
回答方的策略？
- 回答方有兩種選擇，將游戲引向兩種狀態(tài)
- 哪個(gè)狀態(tài)對詢問方更不利？信息熵（不確定性）更大的那個(gè)。
- 一個(gè)重要的評判策略:如果這個(gè)數(shù)是x，那回答方還能撒謊的次數(shù)p
- 記當(dāng)前p為i的數(shù)有$ w_{i}\(個(gè)，W是\) w_{i}$的有序集合
- 一個(gè)狀態(tài)可以用W表示，開始時(shí)的狀態(tài)$ \left { n,0,0,0,0..... \right }$
- 詢問方可以直接得到答案的W滿足$ \sum wi=1$
如何維護(hù)W？
- 考慮回答者的視角，按一次詢問是否涉及一個(gè)數(shù)把W分成A詢問到,B沒詢問到兩個(gè)集合
- yes？相當(dāng)于你對所有b撒謊了
- no？相當(dāng)于你對所有a撒謊了
- 以yes為例，$ w_{i}=a_{i}+b_{i-1}$，相當(dāng)于b被右移一位
如何量化信息熵？
設(shè)$ V_{q}\left(W\right)=\sum_{i}^{k}w_{i}\sum_{j}^{i}\binom{q}{j}$
- q表示在q次詢問內(nèi)得出答案
- 此為估價(jià)函數(shù)(搜索空間的體積)
- 這個(gè)玩意取對數(shù)就是信息熵
感性認(rèn)識:后面那個(gè)組合數(shù)就是撒謊方式的數(shù)量
Vq的性質(zhì)
- $ V_{q}\left(W\right)=V_{q-1}\left(W_{yes}\right)+V_{q-1}\left(W_{no}\right)$
- $ V_{q}\left(W\right)\leqslant 2^q$是能在q次詢問內(nèi)得出解的必要條件
根據(jù)第二條性質(zhì)，可以用$ V_{q}$評價(jià)一個(gè)狀態(tài)
這就可以搞了，回答方根據(jù)這個(gè)估價(jià)函數(shù)決定回答策略
再回頭看詢問方的策略？
- 相當(dāng)于n個(gè)數(shù)$ a_{i}$，分成兩堆，要求差最小
- 沒有多項(xiàng)式做法，可以貪心(論文《論一類啟發(fā)式算法在信息學(xué)競賽中的應(yīng)用》)
0x02 Ulam游戲的實(shí)質(zhì)
- k=1時(shí)，其實(shí)是容錯(cuò)的二分搜索
- 如果$ k\neq 1$？
- 變成了一個(gè)k+1劃分問題
- 回答方:性質(zhì)2變成$ V_{k,q}\left(W\right)=\sum_{i}^{k}wi\sum_{j}^{i}\left(k+1\right) \binom{q}{j}\leqslant k^q$
0x03 其他問題
有一堆球，其中有一個(gè)比其他球輕一些，要求只用一架天平，用最少的次數(shù)找出這個(gè)球
- 三叉搜索，要求其中兩個(gè)集合大小一樣
- 如果天平有不超過k次會出錯(cuò)？
- 容錯(cuò)三叉搜索問題
N個(gè)數(shù)，大小未知，比較器會有不超過e次出錯(cuò)，用最少的比較次數(shù)求其中最大項(xiàng)
- 樸素策略，每次瘋狂詢問，直到一個(gè)返回值出現(xiàn)大于e+1次
- 理論復(fù)雜度(e+1)(n-1)+e
- 然而這是理論最優(yōu)
- 構(gòu)造一個(gè)回答策略，前(e+1)(n-1)-1次詢問如實(shí)回答
- 定義“負(fù)票”這個(gè)概念：如果比較器返回了a比b小，則稱a收到一張負(fù)票
- 顯然如果一個(gè)數(shù)收到e+1張負(fù)票，那這個(gè)數(shù)不可能是最大值
- 前面的一階段的詢問中顯然有一個(gè)$ x_{m}\(收到的負(fù)票小于等于e，且有一個(gè)數(shù)\) x_{n}$沒有收到負(fù)票
- 在后面的e個(gè)詢問中，運(yùn)用撒謊不讓$ x_{m}$收到的負(fù)票超過e
- 最后詢問方無法確定$ x_{n}\(還是\) x_{m}$是最大值，需要再詢問一次，總數(shù)是(e+1)(n-1)+e
容錯(cuò)排序，沒有重復(fù)元素，不考慮常數(shù)
- 隨便選一個(gè)$ nlog_2{n}\(比較排序，運(yùn)用前面的思路可以得到一個(gè)\) enlog_2{n}$排序
- 考慮插入排序，平衡樹維護(hù)序列
- 插入時(shí)不考慮出錯(cuò)問題
- 插入后和前驅(qū)后繼元素O(e)比較一下
- 最終復(fù)雜度$ O((n+e)log_2{n}+(n+e)e)$ log是插入，e是判錯(cuò)
IOI2016 題解
練習(xí)賽前三題都是傻逼題，按下不表
練習(xí)賽T4
有一個(gè)01串S，你每次可以詢問一個(gè)01串是不是S的子串，最終要求輸出S
- 36分，貪心向后加01，不能加了以后向前加01，期望復(fù)雜度2n
- 100分：
- 做法1:貪心加01，但只詢問一次，如果連續(xù)詢問k次都不對，就認(rèn)為長度過長了，在這個(gè)后綴里二分求出最長長度，k取15可過
- 做法2:確定性算法，先二分出最長全0串長度為l，向后加1并判斷，如果連續(xù)l+1個(gè)不合法就說明過長，復(fù)雜度貌似很大，實(shí)際是$ n+2log_2{n}$可過
D1T1
有n個(gè)數(shù)$ a_{i}\(，要求找出一個(gè)集合B使\) \sum bi \in [L,R]\(，滿足\) R-L>a_{max}-a_{min}$
- 從小到大排序，貪心往里加直到加不下，設(shè)當(dāng)前加不進(jìn)去的一個(gè)數(shù)是$ a_{k}\(，由于題目給出的性質(zhì)，\) a_{k}-a_{1}\(肯定能加進(jìn)去，那把\) a_{k}\(加進(jìn)去，\) a_{1}$刪掉，繼續(xù)往后掃
- 答案一定是一個(gè)連續(xù)區(qū)間或者是前綴和+后綴和
- 做法多種多樣
D1T2
有一些鐵軌，每個(gè)鐵軌i要求進(jìn)入速度不大于$ s_{i}\(，出來速度會變成\) t_{i}$，初始速度為1，你可以用1的代價(jià)使速度-1，要求最小化代價(jià)通過所有鐵軌，通過的順序任意安排
- Subtask3：判斷代價(jià)是否為0，對每個(gè)速度建一個(gè)點(diǎn)，初始速度為0，最終速度為INF，鐵軌看作邊，中間點(diǎn)補(bǔ)上向速度+1的邊，判斷0到INF是否聯(lián)通
歐拉路徑
100分，還用剛才的模型，現(xiàn)在可以用1的代價(jià)添加一條i到i-1的邊，現(xiàn)在唯一的問題是不聯(lián)通
現(xiàn)在可以用一定的代價(jià)使i到i+1聯(lián)通(離散化之后)，最終的目標(biāo)是是整個(gè)圖聯(lián)通，由于中間是歐拉路徑，等價(jià)于一個(gè)無向圖，這是什么東西？MST！
D1T3
一條鏈，每個(gè)點(diǎn)上額外掛一個(gè)點(diǎn)，每條邊有權(quán)，在兩個(gè)鏈上的點(diǎn)之間加一條邊長為c，要求最小化兩點(diǎn)間最短距離的最大值
- 二分答案，分類討論兩點(diǎn)與邊兩端的位置關(guān)系，轉(zhuǎn)化為對邊兩端的位置限制，two pointers搞一搞，枚舉限制關(guān)系可過3000
- 求限制關(guān)系的時(shí)候可以枚舉j，線段樹詢問i，可過300000
- two pointer優(yōu)化尋找i，j限制，可A
D2T1
一個(gè)長為n黑白串，給出一些位置的顏色，并且順序給出所有k段極大連續(xù)黑色的長度，問哪些位置的顏色可以確定
- O(nk) DP，判斷每個(gè)位置是否能為黑/白，
- 白色很好判斷，掃一遍
- 黑色的話，窮舉k，前綴和打標(biāo)記，開始+1末尾-1
D2T2
交互題，有個(gè)機(jī)器，支持輸入一個(gè)長度為n的01串，查詢是否存在一個(gè)長度為n的01串，這個(gè)機(jī)器會把你輸入的01串按照一個(gè)排列$ p_{1}p_{2}p_{3}p_{4}p_{5}...p_{n}$重排，求這個(gè)排列
- 分治，每次把區(qū)間二分，對左半?yún)^(qū)間內(nèi)每個(gè)數(shù)i，構(gòu)造一個(gè)數(shù)第i位為1，這個(gè)區(qū)間內(nèi)其他數(shù)為0，區(qū)間外的數(shù)為1
- 復(fù)雜度$ nlog_2{n}$
D2T3
一個(gè)大正方形中有一些點(diǎn)，要求用不超過k個(gè)小正方形覆蓋這些點(diǎn)，小正方形的對角線必須在大正方形對角線上，最小化小正方形面積并
不妨把左下的關(guān)鍵點(diǎn)翻折到右上，并把無用的點(diǎn)刪除，則每個(gè)正方形會覆蓋一段連續(xù)的點(diǎn)，考慮dp，直接轉(zhuǎn)移是$ kn^2$，滿足決策單調(diào)性，斜率優(yōu)化得kn
這種選取不超過k的dp，如果dp[n][k]是一個(gè)關(guān)于k的凸函數(shù)，可以用二分一個(gè)斜率去切這個(gè)函數(shù)，直到切點(diǎn)為k時(shí)即為答案，
這里可以二分每個(gè)小正方形的代價(jià)c，用c去切每個(gè)dp位置，最終復(fù)雜度為$ nlog_2{nk}$
BM算法
- 口音太重，啥都聽不懂
感想
- 冬眠營，掉線營
- 聽個(gè)頭啊
- 怎么口音這么重
轉(zhuǎn)載于:https://www.cnblogs.com/LoveYayoi/p/6745455.html
總結(jié)
以上是生活随笔為你收集整理的WC2017 Day1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ci框架——辅助函数
- 下一篇： C# 反射与dynamic最佳组合