1、 POI2001未完整解決的有：wys 做過但不記得了lan 數學kop 未實現題號核心算法具體細節prz貪心 以左端點遞增，右端點遞減排序，然后貪心即可。ant搜索題意：劉書P228 2.2.4 反素數。定理：a1k1*a2k3*的約數個數為(k1+1)*(k2+1)*(k3+1)*結論：k1=k2=k3= 故最多用到前9個質數，直接搜索即可。map矩陣部分和算法si,j=si,j-1+si-1,j-si-1,j-1+ai,jS矩陣(a,b)-(c,d)=sc,d-sa-1,d-sc,b-1+sa-1,b-1gra博弈+圖論+迭代設Fi表示從i開始時Ann是否有必勝策略。那么當ia時 Fi=

2、Fs1 and Fs2 and 但該圖存在環，故直接計算是不行的。考慮迭代求解，初始時令所有綠點F值為true，按上述遞推式計算所有可以計算的F值，然后將不符合遞推式的綠點F值賦為false，不停計算直到所有為true的綠點都滿足遞推式為止。簡要證明：遞推函數是積性的，即綠點中為true的點越多，所有點中為true的也越多。由此可知初始解為極大解，任意可行解均可由其調整出。每個點最多一次從true變成false，至多n次調整后即可得出結果。gol素數測試+背包2*1010內相鄰質數距離不超過1000，故可找出比N小的第一個質數(Miller-Rabin)，對剩余部分做背包即可，背包時找到盡量小

3、的質數作為轉移即可。spo2-Sat問題對于所有的不和關系i,j，聯邊 ，表示選了前者就必須選后者。求強連通分量并縮點。若存在x使得x與x在同一強連通分量，無解。對新圖進行拓撲排序，然后倒序進行選擇，每次將x選出時將x及其祖先刪除，正確性論文中作了證明。wys構造mro模擬+樹形DP每次移動，以降落點為根做DFS，求出fi表示i的子樹中離i最近的螞蟻中編號最小的在哪個節點上，再DFS一次求出ki=min(hfj-hj j在i至根的路徑上)。然后對于所有的i滿足dfi-di=ki，將fi上的螞蟻移至i上，同時f根上的螞蟻趕走蚜蟲次數加1即可。時間復雜度O(l*(k+n)。pod構圖+最短路將每輛

4、車（包括不同時間出發）的路線上相鄰兩個城市間連一條的有向邊，表示該車在ds分鐘時到達s，dt分鐘后到達t。可以證明，該問題具有最優子結構，故利用SPFA求最短路即可，注意轉移有兩種情況：當前分鐘數nowds，那么等待時間為60-now+dspch最小表示法 因為每個點出度均為1，故圖必然是若個個圈，以每個圈上的每一個點為根一棵外向樹，故判斷這樣兩個圖的同構我們可以這樣做： 每個圈枚舉斷掉一條邊形成一棵樹，利用括號序列求其最小表示并取最小的，最后將所有的圈的最小表示從小到大排序，這樣處理后，兩個圖同構當且僅當它們的圈數相同，相對應的每個圈上的點數相同且每個圈的最小表示相同。 具體實現時利用ans

5、istring可以降低編程復雜度。（括號序列見牛書P288）nas若干匹配算法+最小表示法原問題：兩個串是否循環同構，使用最小表示法的思想可解決，詳見周源論文。對于擴展問題，我們在原算法的基礎上進行以下改動：1：結論：串的最小表示的起始點不可能位于每個重復部分的第一個段落或最后一個段落。故匹配失敗后任一指針落入此位置，可移至最后一個段落。2：利用KMP算法。以Lt*S與Ls*T的匹配為例，此二串完全匹配當且僅當pre(k * Lt) mod Ls = Lt 1=kNow則，借錢Mi-Wi-Now，然后Now:=Now+Wi。假設我們求出了K種貨幣的一個解Ans1,Ans2Ansk，我們首先直接借這么多錢，然后對于第K+1種貨幣，我們在K種貨幣均滿足Mi-Wi=Ans的貸款中找出Mi-Wi,K+1最小的，并用類似一種貨幣時的情況處理。由于要維護動態的最小值，故需要使用堆。zwi歐拉回路+Raney 引理由于所有點度均為4，故必存在歐拉回路。若L-S0，且該循環起點為A的部分和的最小值后面。所以只需求出任一條歐拉