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