10.1
tyvj迎國(guó)慶新賽制模擬賽, 140min, 預(yù)計(jì)260
excel[模擬], 50min, 預(yù)計(jì)AC
直接模擬, 需要用康托展開(kāi). 可以打表判斷位數(shù)(利用等比數(shù)列求和).
*注意考慮R C的順序
stock[判斷有向圖連通性], 30min, 預(yù)計(jì)60/100, O(N^2*T)
給出N個(gè)點(diǎn), T條邊, 判斷至多添加多少條邊圖仍是DAG.
對(duì)于每條邊(u,v), 利用DFS染色+鄰接表判斷(v,u)是否可達(dá).
maze1[雙進(jìn)程DP+輸出方案], 60min, 預(yù)計(jì)AC, O(N^3)
[狀態(tài)] f[x1][y1][x2][y2]表示從(1,1)兩人走到(x1,y2)和(x2,y2)可以得到的最多的面包圈.
t[x1][y1][x2][y2]表示從(1,1)走到(x1, y1)某人可以得到的最多的面包圈(題目要求最小字典序)
G[x_][y_]表示(x_,y_)是否有面包圈
*注意到(x1,y1)和(x2,y2)地位平等, 故只考慮其中一個(gè)即可.
f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2], f[x1-1][y2][x2][y2-1], f[x1][y1-1][x2-1][y2], f[x1][y1-1][x2][y2-1]} + G[x1][y1] + G[x2][y2]
t[x1][y1][x2][y2] = max{t[x1-1][y1][x2-1][y2], t[x1-1][y2][x2][y2-1], t[x1][y1-1][x2-1][y2], t[x1][y1-1][x2][y2-1]} + G[x1][y1]
NOIp09 Hankson的趣味題[數(shù)論], 1.5h, O(50000N), AC
注意到最大公約數(shù)最小公倍數(shù)的性質(zhì)就是
a = p1^a1*p2^a2…pn^an
a = p1^b1*p2^b2…pn^bn
gcd(a,b) = p1^min(a1,b1)*p2^min(a2,b2)…pn^min(an,bn)
lcm(a,b) = p1^max(a1,b1)*p2^max(a2,b2)…pn^max(an,bn)
這里去年就想到了, 然后去年實(shí)現(xiàn)無(wú)能. 下面對(duì)每個(gè)因子p進(jìn)行討論
(1)對(duì)于min{p_x, p_a0} = p_a1
i)若p_a0 = p_a1, 那么p_x ∈ [p_a1, ∞)
ii)若p_a0 > p_a1, 那么p_x = p_a1
(2)對(duì)于max{p_x, p_b0} = p_b1
i)若p_b0 = p_b1, 那么p_x ∈ [0, p_b1]
ii)若p_b0 < p_b1, 那么p_x = p_b1
利用篩法構(gòu)造小于√(2e9)的素?cái)?shù)表, 對(duì)a0, a1, b0, b1分解質(zhì)因數(shù), 然后分別討論四種情況即可(乘法原理).
*需要注意存在大于√(2e9)的素因子的情況, 利用b0[0]和b1[0]記錄即可, 需要注意b1|b0, ans*=2
*利用factor函數(shù)分解質(zhì)因數(shù)時(shí), 傳遞數(shù)組指針, 此時(shí)不能在函數(shù)內(nèi)對(duì)數(shù)組賦初值, 原因不知.
-> size (int *) = 4, 即一個(gè)內(nèi)存地址的大小, sizeof(char*) = 4. 因而只能利用循環(huán)賦值. by gXX
[另解]把b1分解質(zhì)因數(shù), 然后用質(zhì)因數(shù)枚舉b1的所有約數(shù), 然后挨個(gè)求與a0的最大公約數(shù)和與b0的最小公倍數(shù).
10.2
tyvj迎國(guó)慶新賽制模擬賽, 160min, 預(yù)計(jì)150 -> 60/110
60min時(shí)讀題結(jié)束(大概開(kāi)場(chǎng)25min才開(kāi)始看題)
ship[雜題], 84min, 預(yù)計(jì)?
[題意]給定一個(gè)正n邊形, 在每個(gè)頂點(diǎn)上放高度不同的柱子, 使得高度最高的柱子構(gòu)成的多邊形的重心落在多邊形內(nèi).
1. 所有柱子同高顯然符合條件
2. 高度最高的柱子構(gòu)成正多邊形同樣符合條件, 即重心和正n邊形重合
3. 重心不和正n邊形重合且不在邊界上, 判斷無(wú)能
*需要注意的是2和3, 在看了coderspace的答疑之后才想到.
game[模擬_60/], 160min, 預(yù)計(jì)?
"他就要從自己從左邊記下的數(shù)字和從右邊記下的數(shù)字中分別選取一個(gè)數(shù), 將大的減去小的并大聲喊出來(lái)."
->O(N^2), 60
對(duì)于每個(gè)小朋友, 向左向右記錄符合條件的最值. 如果兩邊同時(shí)記錄了最值, 那么輸出max{MaxL-MinR, MaxR-MinL}. 否則輸出-1.
*這題讀錯(cuò)很多次, 一開(kāi)始的想法并不正確, 之后有認(rèn)為是最長(zhǎng)不下降子序列, 并復(fù)習(xí)了O(NlogN)做法. 但事實(shí)上符合條件的序列不是單調(diào)的. 需要在紙上抽象出條件.
maze2[二分+floodfill/], 120min, 預(yù)計(jì)AC
[題意]從(1,1)到(n,m)存在一條路, 使得途中的曼哈頓距離k最大.
對(duì)于每個(gè)k, 第一次floodfill表示c個(gè)面包圈附近所有曼哈頓距離d<=k的點(diǎn). 然后從(1,1)進(jìn)行第二次floodfill, 已標(biāo)記的點(diǎn)不能通過(guò), 若可以到的(m,n)則滿足題意.
*需要注意可以從上下左右任意方向走, 只通過(guò)右下方向會(huì)忽略很多情況.(by coderspace)
*這題是gXX出的, gXX表示標(biāo)準(zhǔn)做法不是二分
tyvj迎國(guó)慶新賽制模擬賽[170/600] -> 各種問(wèn)題亟待解決
10.17
[BYVoid Stage1] 3h + 2.5h, 位置值25%
寫了2h, 前兩題預(yù)計(jì)AC, 第三題滿分算法需要遞推式, 70%算法看不出來(lái); 第四題類似OPEN11的第一題, 各種心理陰影. 第二題花了20min練習(xí)對(duì)拍.
[summary], 130 = 10 + 100 + 10 + 10;
P1: BFS染色看成DFS染色, 需要注意更新條件(G[kx][ky] > G[x][y]+1), 否則會(huì)超時(shí) -> 涉及最短路徑的問(wèn)題顯然是BFS, DFS會(huì)造成各種奇葩的問(wèn)題
*事實(shí)上還是腦抽了, 標(biāo)準(zhǔn)做法O(MN), 將所有傳染源加入隊(duì)列, 直接BFS即可.
P2: 分組背包問(wèn)題, 差點(diǎn)看成泛化物品. 數(shù)據(jù)很弱, 用來(lái)對(duì)拍的暴搜同樣AC.
*O(ABN), 和標(biāo)準(zhǔn)做法一樣, 而且利用了0/1背包的性質(zhì)直接降維, 減少內(nèi)存使用.
P3: 看了題解, 收獲很多.
(1)從數(shù)學(xué)角度考慮, 70
不妨考慮題目的退化情況, 即不存在棧元素?cái)?shù)量p的限制. 注意到1號(hào)元素比較特殊, 初始時(shí)1號(hào)元素必須先行進(jìn)入b棧, 然后進(jìn)入c棧. 故而可以劃分為兩個(gè)過(guò)程, 過(guò)程I在a元素進(jìn)入c棧之前, 過(guò)程II在a元素進(jìn)入c棧之后. 利用乘法原理f[n] = Σf[k]*f[n-k-1](0<=k<i). 當(dāng)然這東西其實(shí)就是Catalan數(shù).
*白書上給出了另一種推導(dǎo)方式, 利用凸多邊形上的分割. 固定一三角形V1VkVn, 討論其兩側(cè)的多邊形的情況, 故而f[n] = Σf[k][n-k+1](k>=2), f[2]=f[3]=1. 也可以通過(guò)固定對(duì)角線的方式討論, 注意到每條對(duì)角線被重復(fù)計(jì)算了2n-6次(凸n邊形僅有n-3條對(duì)角線), f[n] = Σf[k]*f[n-k+2]*n/(2n-6). 與上式聯(lián)立可知, f[n+1] = f[n]*(4n-6)/n.
*這里的推導(dǎo)方法和第二類stirling數(shù)的推導(dǎo)方式類似, 考慮一個(gè)特殊元素的動(dòng)作, 然后劃分問(wèn)題(利用乘法原理).
加上棧元素?cái)?shù)量的限制, f(i,j)表示i個(gè)元素在棧元素限制為j時(shí)的方法數(shù), 可得f[n][p] = Σf[k][p-1]*f[n-k-1][p](0<=k<n), f[i][0] = 0(0<i<=n), f[0][j] = 1(0<=j<=n)
(2)從動(dòng)態(tài)規(guī)劃角度考慮, AC
考慮到題目中存在三個(gè)棧a\b\c, 設(shè)置狀態(tài)為f(i,j,k)表示a棧中有i個(gè)元素, b棧中有j個(gè)元素, c棧中有k個(gè)元素的方法數(shù), 注意到i+j+k=n, 故只用f(i,j)即可.
若a棧中有i個(gè)元素, b棧中有j個(gè)元素, 可能是a棧中的1個(gè)元素到b棧中, 亦可能是b棧中一個(gè)元素到c棧中, 故而方程為f[i][j] = f[i+1][j-1] + f[i][j+1], f[n][0] = 1, f(0,0)為所求. 這個(gè)方程應(yīng)該同樣適用于無(wú)棧元素限制的情況(即沒(méi)有特別的限制).
*數(shù)學(xué)上的遞推式的思考方式, 往往是固定或者討論1個(gè)元素, 進(jìn)而劃分問(wèn)題或者類似情況. 而DP的思考方式, 建立在狀態(tài)的基礎(chǔ)上, 注重狀態(tài)間的轉(zhuǎn)移, 進(jìn)而找到方程.
*一個(gè)小技巧, a mod 2^p = a & (2^p-1); 直觀上其實(shí)很容易理解, 轉(zhuǎn)化為2進(jìn)制看待, 取模即得到a二進(jìn)制下得后p位, 和位運(yùn)算與的目的是一樣的.
P4: 需要抽象出最短路模型, SPFA即可.(注意此時(shí)的點(diǎn)數(shù)不超過(guò)p*p, 而不是p)
注意到題目中同種能量結(jié)界可以無(wú)損耗傳送, 不妨將每個(gè)能量結(jié)界縮為一點(diǎn), 于是可以得到一個(gè)新的圖. 為了簡(jiǎn)化計(jì)算, 在第一行前增加起點(diǎn), 在最后一行后增加終點(diǎn). 求出從起點(diǎn)到終點(diǎn)的最小點(diǎn)權(quán)覆蓋即為答案. 然后題解中給出了一種很神奇的構(gòu)造, 將起點(diǎn)和終點(diǎn)外的點(diǎn)形成的邊拆成兩個(gè)邊, 邊權(quán)為邊終點(diǎn)的點(diǎn)權(quán), 起點(diǎn)和終點(diǎn)僅考慮單向. 利用鄰接表實(shí)現(xiàn), 可以利用一個(gè)bool型數(shù)組判重. 之后利用SPFA求最短路, h-d[p+1]即為答案, 小于0輸出NO.
*關(guān)鍵在于1) 以能量結(jié)界為點(diǎn)抽象出圖, 轉(zhuǎn)化為最小點(diǎn)權(quán)覆蓋.
2) 拆邊賦權(quán), 轉(zhuǎn)化為最短路模型.
10.18
USACO Contest OPEN11 cornmaze(BFS), 2h
略復(fù)雜的BFS, 寫了約30min, 調(diào)了1.5h. 主要卡在兩個(gè)錯(cuò)誤和STL的語(yǔ)法上.
按照題意, 從起點(diǎn)開(kāi)始, 如果遇到裝置直接跳, 遇到草地繼續(xù)走, 遇到玉米就終止, 直接BFS即可. 注意到題目中的裝置成對(duì)出現(xiàn), 而且遇到裝置必須走, 這和昨天的第四題不同. 可以利用map數(shù)組記錄裝置的對(duì)應(yīng)關(guān)系.
*對(duì)于一對(duì)裝置, 從A到B, 只需標(biāo)記A已讀, 無(wú)需標(biāo)記B已讀, 可能出現(xiàn)跳過(guò)來(lái)又跳回去更短的情況. 但是要使B入隊(duì), 并且更新B的距離, 而不是更新A的距離.
*利用x*n+y對(duì)坐標(biāo)編碼的時(shí)候, 充要條件是n>=m, 否則解碼會(huì)出現(xiàn)錯(cuò)誤. 因而可以利用x*(n*m)+y進(jìn)行編碼, 在不溢出int的情況下. 當(dāng)時(shí)在白書上見(jiàn)到這種寫法, n=m, 并且坐標(biāo)從0開(kāi)始.
10.19
Tyvj新賽制模擬賽 stock, unAC.
10.20
stock[傳遞閉包]
題意就是確保每條需要添加的邊(x,y), (y,x)不連通, 且x!=y(即點(diǎn)上沒(méi)有自環(huán)).
和wx神牛給出的做法一樣, 維護(hù)一個(gè)N*N的矩陣表示連通性, 若加入邊(x,y), 則更新x的前驅(qū)和與y的后繼的集合(x,y分別在集合中)的邊為連通.
*復(fù)習(xí)了對(duì)拍的寫法, 昨天查錯(cuò)查了1h, 寫了O(N^2*T)的寫法:
(1)更改了已連通點(diǎn)的情況
(2)沒(méi)有考慮x的前驅(qū)和y的后繼直接連通的情況
(3)沒(méi)有考慮點(diǎn)的自環(huán)(make中人為避免了這種情況, 審題不清.)
*參照題解寫O(NT), 更新連通情況時(shí)G[A[i]][B[j]]打成G[A[i]][B[i]], 對(duì)拍后發(fā)現(xiàn).
*當(dāng)時(shí)的DFS寫法的問(wèn)題, 修正后50:
(1)沒(méi)有考慮重邊的情況, 因而對(duì)于每一條邊都要重新加入, 數(shù)組必然會(huì)爆. 可以利用矩陣維護(hù)已添邊, 這樣的話復(fù)雜度應(yīng)該為O(N^2*P).
(2)next[]數(shù)組范圍開(kāi)小
[BYVoid Stage2] 1.5h, 完全不會(huì). -> 眼高手低
以下是對(duì)于題意的簡(jiǎn)單判斷, 看起來(lái)和去年差不多, 眼高手低:
P1: 模擬, 但是概率無(wú)能
P2: DP, 沒(méi)想出方程
P3: DP + 多重背包?
P4: 極大強(qiáng)連通分量, Tarjan忘了, 裸的做法不會(huì)(注意到范圍很小)
-> 題解顯示方向判斷基本正確, 基本思路都正確, 但是實(shí)現(xiàn)都卡在某些地方
P1:分為兩個(gè)部分, 求概率和期望, 有1個(gè)trick.
對(duì)于概率可以分四個(gè)部分討論:
(1) 無(wú)事故 -> 按照題意, 乘以無(wú)事故概率分別計(jì)算即可
(2) 同時(shí)事故 -> 平局, 把四個(gè)獨(dú)立事件(故障)乘起來(lái)
(3) 侏儒事故 -> 地精勝利, 地精無(wú)事故*侏儒事故概率 ->需要注意這里不需要考慮無(wú)事故獲勝概率, 仔細(xì)讀題
(4) 地精事故 -> 侏儒勝利, 類似上文
*需要注意利用pow(sum,1/n)開(kāi)n次方的時(shí)候, 必須邊讀入邊計(jì)算, N = 1e6. 可以利用e^((1/n)*ln(a)) = a^(1/n)來(lái)計(jì)算.
*沒(méi)有在分類基礎(chǔ)上結(jié)合題意繼續(xù)討論, 導(dǎo)致理解偏差, 于是沒(méi)想出來(lái).
P2:我想的方程的狀態(tài)是f(i,j)表示疲勞度為i, 行走距離為j, f(i,j)表示所需最小時(shí)間.
所以方程 f(i,j) = min{f(i-1, j+1), f(i+2, j+5), f(i+5, j+10)} + 1 (i ≠ p)
f(p-10, j+10) + 10 (i = p)
以距離為階段, 沒(méi)有后效性, 看起來(lái)如果記憶化, f(0,0)是答案. 但min給初始化造成了一定的麻煩; 更重要的是, 這樣的方程使用滾動(dòng)數(shù)組較為麻煩, 會(huì)爆內(nèi)存.
*事實(shí)上i == p的情況不會(huì)得到最優(yōu)結(jié)果, 即干擾條件. 要避免疲勞度達(dá)到上限.
改進(jìn)做法是這樣, f(i,j)表示行走最大距離, i表示花費(fèi)時(shí)間, j表示疲勞度, 可以得到方程:
f(i, j) = max{f(i-1, j+1)+1, f(i-1, j-2)+5, f(i-1, j-5)+10}
需要利用滾動(dòng)數(shù)組降維, 即for(i = 1, k = 1; i <= S; i++, k = !k)
*需要指出方程不太嚴(yán)謹(jǐn), 考慮S=1, P=1, 條件1的1+1>P, 所以需要特殊處理.
*太久沒(méi)寫DP了, 所以方程細(xì)節(jié)問(wèn)題很多.
10.22
東方幻想鄉(xiāng)Stage1, 2.5h, 215 -> 310, 位置值65%
*發(fā)現(xiàn)solution一個(gè)很好的用途, 比較命題人給出的題意, 鍛煉從題目中抽取信息的能力.
P1: 模擬+分析, 20min, AC
(1) 計(jì)算整個(gè)序列的位移向量a
(2) T/len * a, T%len模擬
*個(gè)人覺(jué)得亦可正交分解, 統(tǒng)計(jì)不同方向向量個(gè)數(shù)(N S對(duì)稱, W E對(duì)稱), 做法同上.
P2: 二分高精除法, 1h, TLE原因不知
*[沒(méi)有注意到范圍] O(LlogANS), 題目中給的ANS<=2*1e9, 而我算的ANS是1e20000. 本來(lái)是20000*9, 范圍錯(cuò)誤后, 20000*20000, 顯然TLE.
*按位除效率高于二分高精除 by qz神牛
*其實(shí)直接寫單精度乘法即可
*題解中二分條件, left+1<right;left = mid;right = mid;
*INT_MAX的另一種寫法, ~0U>>1, U表示無(wú)符號(hào)整數(shù) by WJMZBMR
P3: DP+優(yōu)化(單調(diào)隊(duì)列\(zhòng)優(yōu)先隊(duì)列), 60
f[i]表示在i取得的最大冰凍指數(shù)值
f[i] = max{f[i-j] + A[i]}(L<=j<=R, 0<=i<=n+R)
利用prev[i]記錄f[i]由f[i-j]推得, 遞歸即可記錄方案.
*2個(gè)trick, 存在負(fù)數(shù)(初始化-INF), 可以越過(guò)終點(diǎn)(前驅(qū)必須在終點(diǎn)前) -> 注意數(shù)組大小為f[N+R], 否則溢出
P4: 強(qiáng)連通分量(Floyd傳遞閉包+并查集), 50
利用Floyd傳遞閉包, 對(duì)于每一點(diǎn)對(duì)(u,v), 若是雙向連通則使用并查集合并集合{u},{v}. 統(tǒng)計(jì)元素?cái)?shù)最多Max的集合, 從頭開(kāi)始掃面每個(gè)節(jié)點(diǎn)所屬集合, 遇到所屬集合元素?cái)?shù)量為Max的點(diǎn)直接跳出. 掃描該集合即可輸出方案.
10.23
toj 1169 廣告印刷[單調(diào)隊(duì)列]
NOI導(dǎo)刊(11.5)例題, 使得隊(duì)列中元素大小和下標(biāo)同時(shí)單調(diào). TLE, 原因未知.
[東方幻想鄉(xiāng)S1P2]iceroad, DP+單調(diào)隊(duì)列, AC
維護(hù)區(qū)間[i-R, i-L]的最大值, 先檢查隊(duì)列中元素下標(biāo)的合法性(即滿足q[head]>=i-R), 然后插入元素f[i-L].
*越過(guò)終點(diǎn)的情況必須初始化A[], 否則會(huì)造成答案錯(cuò)誤.
*按照std, 必須初始化為0, 否則最后兩個(gè)點(diǎn)WA. -> 數(shù)組溢出, 必須初始化為-INF, 數(shù)據(jù)弱, wagner的std會(huì)掛
*對(duì)于大數(shù)據(jù)掛掉的情況, 很可能是由于數(shù)組溢出
[東方幻想鄉(xiāng)S1P3]classroom, Floyd+并查集, 60
(1) 一個(gè)錯(cuò)誤,如果存在邊(v,u)會(huì)被刪除.
G[v][u] = (type == 2) ? 1 : 0; -> 考慮之前存在邊(u, v)
*縮略形式很可能是不等價(jià)的, 要考慮全面
(2) 記錄集合元素個(gè)數(shù)的寫法
path[y] = path[x];
tot[x] += tot[y];
可以這么解釋, find(y)會(huì)指向x, 于是更新x的元素個(gè)數(shù).
*想起了Tyvj9月月賽第二題
10.24
東方幻想鄉(xiāng)Stage2, 2.5h, 200, 位置值82%
P1: 簡(jiǎn)化版最大子矩陣, AC.
給出了矩陣大小(R,C), 令s[i][j]表示Σs[1..i][1..j], 只需枚舉[R,N, C,M]作為矩陣頂點(diǎn)計(jì)算大小即可.
s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + A[i][j]
矩陣大小S = s[i][j] - s[i][j-C] - s[i-R][j] + s[i-R][j-C]
P2: 進(jìn)制轉(zhuǎn)換+同余, AC.
(1) 得到1..L位分別對(duì)于M取余的余數(shù)pow[i]
(2) O(L), 判斷當(dāng)前數(shù)是否整除
余數(shù)rem = Σs[L-i-1]*(A[i]-'A'), 利用傳遞性取余.
(3) O(L^2), 枚舉任意兩個(gè)數(shù)對(duì)(i,j), 交換后計(jì)算余數(shù), 若整除直接輸出結(jié)果
題目要求字典序最小, 指字符串[1..L], 需要注意下標(biāo) -> 這里浪費(fèi)了20min, 多次手工模擬錯(cuò)誤
交換的寫法:
rem += M - ((s[i]-'A') * pow[L-i-1]) % M;//利用補(bǔ)數(shù), 分別減去i,j原來(lái)的位值
rem += ((s[j]-'A') * pow[L-i-1]) % M //加上i,j新的位值
*Win7一個(gè)奇葩的性質(zhì), patchouli因?yàn)橛嘘P(guān)鍵詞patch, 會(huì)默認(rèn)以管理員身份運(yùn)行, 于是調(diào)試無(wú)能.
P3: 似乎是計(jì)算幾何, 只想到了旋轉(zhuǎn)坐標(biāo)系. -> 預(yù)處理[排序]+DP
(1) 利用點(diǎn)斜式得到結(jié)論 d = y - kx, 以d為關(guān)鍵字對(duì)點(diǎn)進(jìn)行排序
(2) f[i]表示1..i點(diǎn)可以取到的最大值
f[i] = max{f[j] + Σvalue[i]*Σmul[i]/(j-i) (這里Σ的范圍是[j-i+1, i])} (0<j<i)
*對(duì)于α=90°的情況, 由于π的精度不夠, 可以不討論. -> 對(duì)x排序即可, 實(shí)現(xiàn)的話可以直接交換坐標(biāo)
*對(duì)于多點(diǎn)d相同的情況, 按solution寫法應(yīng)該討論, 但是參照標(biāo)程特判會(huì)WA, 原因未知?
P4: 圖論題, 有條件的最短路問(wèn)題.
*分層圖最短路
10.27
東方幻想鄉(xiāng)Stage3, 2.5h, 110, 位置值64%
*心不在焉, 多次看錯(cuò)題.
*需要思考看完整套題的意義, 目的是什么, 需要得到什么樣的信息.
P1: 二分+模擬, 95
(1) 記錄被破壞點(diǎn)下一個(gè)被破壞點(diǎn)的位置next[]
(2) 以0為下界, [N/K]+1為上界, 二分答案L -> L=0即未被地震破壞, 考慮不周
(3) 利用next[]對(duì)數(shù)軸染色, 限制次數(shù)為K, 若染色后仍發(fā)現(xiàn)破壞點(diǎn)則無(wú)解
P2: 概率, 15, O(NT) -> 正解是DP
每個(gè)時(shí)刻更新每個(gè)點(diǎn)的概率, 利用鄰接表(矩陣實(shí)現(xiàn)). 不更新的充要條件是vis[v][u][k-1]=1.
用P[i][k]表示第i個(gè)點(diǎn)在第k時(shí)刻的概率, 初始化P[1][0] = 100.
*思路非常混亂, 一開(kāi)始不更新的充要條件找錯(cuò). 錯(cuò)誤原因不知.
*不明白O(NT)的做法為什么會(huì)錯(cuò), 標(biāo)程用類似樹(shù)形DP.
P3: 最小生成樹(shù)+并查集維護(hù)連通性+枚舉 -> 不用并查集
利用Kruskal構(gòu)造最小生成樹(shù), 并查集記錄連通情況, 利用鄰接矩陣維護(hù), 枚舉每個(gè)度大于2的點(diǎn)不斷按照定義更新答案.
*考慮到多邊權(quán)重相等的情況, 可能需要多次計(jì)算.
P4: LCS? -> 搜索+剪枝