2.6
poj 3660[Floyd]
[題意]
給定n個點, m條有向邊, 判斷有多少個點的位置唯一確定.
[做法]
從對每個節點的度分析入手. 利用Floyd傳遞閉包, O(N^3)足矣, 統計所有 入度+出度 = 頂點數-1 的點的個數, 顯然如果一個點x, 與其他n-1個點的關系確定, 那么這個點的位置可以確定.
*一開始從度的分析入手(這是對的, 但是要傳遞閉包), 之后認為是拓撲排序, 在這之后就沒有思路了. 但事實上這時候不應該看題解, 至少應該進行30min的思考.
*傳遞閉包有O(N^2)的做法, 參見去年的shock, 大意是每增加一條邊(x, y), 對于任意(a, x), 使得(a, y)連通; 對于y的處理同理.
*每周的訓練時間大致是周一下午, 周三一節課.
2.8
poj 3661[DP]
比較奇怪的DP, 去年查閱各種題解后A了, 今年還是不會做 = =|||
[狀態]f[i][j]表示第i秒后, 體力值為j時的可以到達的最大距離.
很自然的得到了第一個方程
f[i][j] = max{f[i-1][j-1] + d[i], f[i+j][0]}
很明顯兩個狀態要求的規劃方向矛盾.
于是自然的YY了一個錯誤的方程
f[i][j] = max{f[i+1][j+1] + d[i], f[i+j][0]}
但事實上應該這樣考慮
f[i][j] = f[i-1][j-1] + d[i]
f[i][0] = max{f[i-1][0], f[i-j][j]} (i-j >= j && j <= m) => (j <= min(i/2, m))
即對不同的規劃方向分別處理.
*本題的關鍵即對不同規劃方向的處理, 其實想一想不見得想不出來
2.13
poj 3663[數學/二分/枚舉], 1h
很簡單的題目, 但是由于各種細節考慮不周, 連對拍在內寫了1h = =|||
[1] 顯然可以O(N^2)枚舉, 然后隨便排序一下, 就可以0.6s通過了.
[2] 我想到的一種很疼的O(N)做法
(1) Cnt[n]表示1..n的值的個數, 可以利用前綴和得到
(2) 對于每個L_i, 累加Cnt[S - L_i] - (2*L <= S), 需要討論S - L_i >= Max{L_i} 和 S - L_I <= 0的情況
(3) 顯然每對數都被計算兩次, 輸出ans/2即可
[3] 官方題解的O(NlogN)做法
(1) 排序
(2) 對于每個Lower, 計算滿足題目的最小Higher, 累加Higher - Lower即為答案
poj 3664[排序]
利用qsort對A[]間接排序, 然后利用O(K)的時間循環檢查最大值即可, 復雜度O(NlogN)
poj 3665[模擬]
很像是數據結構題的小范圍寫法 = =|||
按照題目模擬即可.
2.20
poj 3662[最短路+二分]
[題意]
給定N個點, P條雙向帶權邊, 其中K條邊的權可以為0, 求最大邊權的最小值.
[做法]
根據描述很容易想到二分, 注意到題目對前K條邊的具體情況沒有要求. 用f(M)表示最大邊權為M時是否可行, 把邊權大于M的邊賦值為1, 小于M的邊賦值為0, 求最短路即可.
*這里并不能使用BFS求最短路, BFS僅在無全圖中可求最短路.
*注意二分的寫法, 可以打出f(M)的值觀察條件
*注意無解和0的區別
3.5
MAR12 Silver[未實現]
P1
[Brief]
在1000*1000棋盤上從(x, y)到(1, 1), 給定N個定點, 最少通過N個定點中的幾個點.
[Solution]dij+heap, O(ElogV)
對每個點u, 如果其周圍有定點v則 w(u, v) = 1, 否則w(u, v) = 0. 易知|V| <= 4*1000^2, 直接求(x, y) 到 (1, 1) 的單源最短路即可.
P2
不會做...
P3
同上 > <
3.12
MAR12 Bronze[我墮落了...]
P1: std將17拆分為16+1, 從而避免了進制轉換.
P2
[Brief]
從(0, 0)開始, 僅在N個頂點可以轉彎(90或180), 求有多少序列可以僅經過一次所有點, 并回到原點.
[Solution]
O(N!)生成序列, 直接利用坐標判斷是否合法即可.
P3
[Brief]
給出一個序列(L <= 10^5), 每個字符可能是三個操作符F/L/R其中之一, FJ打錯了一個字符, 試統計可能到達多少種不同的終點.
[Solution]
(1) 掃描序列, 記錄每個點的位置, 可以得到任意兩點之間的向量.
(2) 枚舉每個位置可能的錯誤字符, location(n-1) + (n -> dimension)即為答案.
(3) 記錄每個可行終點, 利用排序去重.
總復雜度O(N+N+NlogN) = O(NlogN).
3.15
MAR12 Silver
flowerpot[Heap/二分+RMQ]
[Brief]
給定N個坐標, 滿足|y_j - y_i| >= D, 求|x_i - x_j|的最小值, 若不存在最小值則輸出-1.
*題目真心看不懂, 看了樣例才懂了.
[Solution]
[1] O(N^2)暴力枚舉每個坐標
[2] O(NlogN)
(1) 對x升序排序
(2) 求出y的區間最大/小值
(3) 二分|x_i - x_j|, 這里需要記錄對于每個x_i, x_i+D的位置(可能不存在)
-> 這個思路非常麻煩, 不可行
[3] O(NlogN), 利用Heap
和我最初的想法一致.
(1) 對x升序排序
(2) 對于每個x_i, 找到最近的x_j, 滿足|y_i - y_j| >= D
事實上(2)可以進一步強化為|max{y} - min{y}| >= D, 也即若區間[i, j]滿足題意, 但|y_i - y_j|不滿足題意, 則其中必有子區間滿足|y_i - y_j| >= D
[譯自官方題解]
我們首先對所有點的x進行排序, 然后利用一對豎直的掃描線, 從左至右遍歷整個平面. 一對掃描線之間的點的y值, 利用一個能夠快速查找最大/最小值的數據結構存儲, 例如STL multiset(如我們在下文所使用), 或者一對堆. 每當最大和最小的y的差至少為D時, 我們檢查此時是否得到目前位置的最優結果, 之后將左掃描線向前移動. 否則, 我們將右掃描線向前移動. 算法總的運行時間為O(NlogN).
*對(2)進行強化后, 可以避免大量冗余操作
*強化后, (2)可以直接使用Sparse Table在O(1)得到最值. 效率應略高于官方題解.
3.19
[利用qsort對結構體排序]
int cmp(const void *a, const void *b){
point *A = (point*)a, *B = (point*)b;
return (A->x > B->x) ? 1 : -1;
}
*A是一個指針, *A = (point*)a表示把無類型指針a轉換為point型的指針
int cmp(const void *a, const void *b){
int i = *(int*)a, j = *(int*)b;
return (i > j) ? 1 : -1;
}
i = *(int*)a表示先把無類型指針a轉換為int型的指針, 然后利用*得到指針所對應的值
flowerpot[區間掃描+RMQ(Sparse Table)], 40min
(1) 對x升序排序(由于之后需要得到區間最值, 直接對結構體排序, 而非間接排序)
(2) sprase_table
*f[i][j] = max{f[i][j-1], f[i + 2^(j-1)][j-1]}, 初始化f[i][0] = P[i].y
(3) 區間掃描, 初始區間[i = 1, j = 1]
i) 若區間[i, j]滿足題意, 嘗試更新答案, ++i
ii) 若區間[i, j]不滿足題意, ++j
*對于操作i, 此時區間合法, 為了得到最短區間, 左指針右移.
landscape[DP, 編輯距離], 1h
[Brief]
給定一個長度為N(N<=100)的序列, 序列中的每個元素權重為a_i(Σa_i <= 1000), 對A_i加1需要付出代價X, 對a_i減1需要付出代價Y, 把1個單位從a_i移動到a_j需要代價(j-i)*Z, 求把序列a_i變換為序列b_i(Σb_i<=1000)的最小代價.
[Solution]
[1] 最初由N的范圍猜測是DP, 用f[i][j]表示前i-1個元素已符合題意時, 第i個元素權重為j時的代價. 遂發現此時存在后效性, 無果而終. 進而猜測可能是網絡流模型, 參看題解.
*和GDKOI 2012 Day1一樣, 最初的想法是正確的, 略深入的想法是錯誤的, 但此時切換角度思考就能得到正確結果.
[2] 換一種角度, 我們考慮每個代價的位置序列A_i, 變換為B_i. 序列A_i和B_i單調不降. 考慮到題目中的三種操作, 套用"編輯距離"模型.
[狀態] f[i][j]表示A_1..i和B_1..j符合題意時的最小代價
[方程] f[i][j] = min{f[i-1][j] + Y, f[i][j-1] + X, f[i-1][j-1] + Z*|A[i] - B[j]|}
[初值] f[i][0] = Y*i, f[0][j]= X*j
*對于確定大致方向的題目, 可以分別考慮題目中涉及的幾個量, 進而得到解法.