10.29
WZOI第一次模擬賽, 2h -> 0
卡第一題, 現在頭暈中. 思路錯誤, 很快的得到了題意, 對斐波那契數列取模. 然后用特征方程搞出了遞推式, 然后發現n>=20后的情況, 嘗試對無理數取模, 然后各種頭暈.
*這是NOIp, 不是CMOp, 怎么會考這么蛋疼的東西. 找時間重寫吧, 限時2.5h. -> 應該往周期數列的方向上想
*感覺現在需要系統復習, 又是瓶頸狀態
10.30
調教Ubuntu in VMware, TeX中文無能
姜碧野論文<SPFA算法的優化及其應用>, 學習差分約束系統
*還有兩種優化SLF和LLL, 真心覺得不如打dij+heap
butter, 復習SPFA.
*關于數據結構的整理
(1)鄰接表 first/next/u/v/w/Cnt -> addEdge()
(2)SPFA d/q/inq
(3)初始化 first/d
*沒有考慮雙向邊, 不可達的情況. 在敲代碼之前應盡可能完善算法.
poj3259[DEC06, Gold, SPFA找負環]
(1) BFS做法
數組count[]記錄每個點的入隊次數, 由定義易知, 若count[i]>=N, 則圖必然存在負環.(<算法之道>上有個很好的例子)
*標程直接按照Bellman-Ford的定義做, 復雜度O(NM). 網上的一次BFS的做法是錯的, 比如兩個強連通分量的情況:
1
6 4 2
1 2 2
1 3 2
2 3 2
4 5 2
5 6 10
6 4 10
*因而N次SPFA的效率O(kNM)可能不如裸的Bellman-Ford O(NM); 更好的做法是Tarjan+SPFA, 即只對每個強連通分量進行SPFA, O(N + kM)
*優化:
1) d[]可以初始化為0, 速度比(3)要快
2) 入隊次數不超過2(M+N), 可能錯誤
(2) DFS做法, WC09姜碧野論文涉及, 實現無能.(網上的做法又是錯的)
(3) Bellman-ford, O(VE)
三重循環, 對每條邊更新V次, 效果好于(1)
*SPFA找負環, 利用vis標記每個點是否被訪問過, 僅對當前未訪問的點進行SPFA, 這樣的話效率應該高于O(VE) //期望情況下
10.31
poj1201[差分約束系統], 25min, 1Y //參見WC06馮威論文
關鍵在于建模, 令d(i)表示0..i的整數個數, 可得
d(b) - d(a-1) >= c_i
d(i) - d(i-1) >= 0
d(i-1) - d(i) >= -1
即
w(a-1, b) = c_i
w(i-1, i) = 0
w(i, i-1) = -1
按照定義, 求整數個數最小值, 即求SPFA最長路.
*注意更新最小標號idS, 最大標號idE, 第二類邊要對1..idE的情況賦值
*關鍵在于找出差分方程組
http://blog.csdn.net/kk303/article/details/6864199
*一般的解題步驟: (1)建模 (2)設計數據結構 (3)寫出大致流程
po3169[差分約束系統], 35AC, 3WA
(1) 建模
題目中給出兩種邊(a, b) , d
對于第一種, (a, b) >= d
對于第二種, (a, b) <= d, 即(b, a) >= d
*SPFA求最短路, 還是最長路, 由不等號方向決定
(2) 討論各種解的情況
1) 正常
2) -1, 存在負環
3) -2, 無法連通
*對于負環, 小范圍Bellman-Ford(多進行一輪松弛操作), 大范圍一次SPFA(count[i]>=N)
*各種字母打錯, 變量打錯 -> 對于點, MAXn; 對于邊, MAXEdge;
東方幻想鄉Stage2, P4, suika[分層圖最短路+SPFA], 1h
(1) 建圖
1) 點從奇時刻到偶時刻(U,U'), 從偶時刻到奇時刻(U',U)
*需要注意黑洞停留消耗體力s[U], 白洞不消耗
2) 邊, 兩種情況
A. 端點顏色&重量相異(正負號取決于題意)
奇時刻到偶時刻 (U, V') = w(U, V) ± delta
偶時刻到奇時刻 (U', V) = w(U, V) ± delta
B. 端點顏色相同/重量相同
奇時刻到偶時刻 (U, V') = w(U, V)
偶時刻到奇時刻 (U', V) = w(U, V)
(2) SPFA最短路
*注意讀題(題意/算法流程/數據結構)
*Nettle標程的做法, 規定2*U為偶時刻點, 2*U-1為奇時刻點, SPFA起點由起點狀態決定. 可以避免建圖時的討論.
*算法三依舊理解不能.
NOIp09, trade
(1) 傳遞閉包+枚舉, 40
1) O(kN^3), 利用鄰接矩陣更新連通性
2) O(N^2), 對每個點找最大旅費, max{w[i] - min{w[j]}} ((j,i) (1,j) (i,N)連通)即為答案
(2) 兩次SPFA維護連通性+枚舉, AC
1) 從起點1開始SPFA, d[i]表示(1,i)是否連通;
A. 對于正環的處理
按照定義, count[i]>=N則不再入隊.(這樣70, 利用r<=2*N不再入隊可以AC)
B. 記錄遇到的最小價值Min{A[j]}
2) 從終點N開始SPFA, 將之前的邊反向(添邊時使用last和prev數組, 替代first和next數組), 維護連通性
3) 枚舉min{A[i] - min{A[j}}, (j,i)連通, 1<=i<=N的最大值即為答案.
*題解給出了兩種做法
(1) 求強連通分量縮點, 轉化為DAG, 然后求解
(2) d[i] = min{d[i], d[j], a[j]}作為松弛操作, SPFA
SPFA專題結束, 明天開始Tarjan和dij+heap
11.1
agrinet[Kruskal], 20min, 復習Kruskal
11.2
Tyvj, Sept09, P2[Kruskal + 并查集]
需要理解Kruskal的過程， 做法如下：
(1) 間接排序（邊集數組）
(2) 按照Kruskal， 從w[i]最小的邊開始統計，并查集維護聯通性
p[x] = y;//并集
num[y] += num[x];//統計每個集合的點的個數
maxe[y] = max{maxe[y], maxe[x], w[i]};//維護每個集合的最大邊
ans += (C(2,num[x]+num[y]) - C(2,num[x]) - C(2,num[y]) - 1) * (maxe[y] + 1);//統計沒有聯通的邊
*沒有間接排序WA了一次，可以通過小數據檢驗(比如深度不同的樹、鏈)
*各種卡long long, 可以計算最大值為10^6C(2,10^6)
-> long long的類型轉換, long long類型的計算中, 數字必須標識ll, 否則會導致計算錯誤.(也就是說可能爆int范圍的地方都要用long long)
-> [by gXX] 可以這么分析, (long long) = (int) * (int) / (int); 于是中間的寄存器會掛掉
*深度大于1的樹的生成 by Ylen
和深度為1的樹的做法相同, 然后記錄葉節點, 對葉節點隨機伸長
NOIp10, P3[并查集]
*需要明確并查集能干什么, 并查集可以合并, 但是不能隔開 -> 把分隔操作轉化為合并操作
(1) 間接排序（邊集數組）
(2) 利用sep[i]記錄i的敵人, 對于(u,v)
i) sep[u]存在, 那么merge(v, sep[u]) //u的敵人們是朋友
ii) sep[u]不存在, 那么sep[u] = v//v是u的敵人
v同理, 遇到find(u) == find(v)的情況, 直接輸出答案即可
*需要注意特判沖突的情況, 不妨用flag標記, 若沒有輸出答案, 則輸出0
王曉東練習題, 序關系計數[DP]
f(i, j) = (j+1) * (f(i-1, j-1) + f(i-1, j))
f(i-1, j)很好解釋, f(i-1, j-1)解釋無能
[狀態]f[i][j]表示i個數加j個小于號
*Covi給出一個結論, 禁止小于號加在一堆等號內部, 證明無能 -> 在zjy的提示下解決了
*注意到序列中已添加的數的值是不變的
i)f[i-1][j]的話, 已有的數被分成j+1組, 顯然每組只能添加1個等號
ii)f[i-1][j-1]的話, 已有的數被分成j組, 因為要添加<號, 所以只有(j-1)+2=j+1個位置可以(即每組的邊界)
Contest OPEN11 Silver, llang[并查集]
(1) 讀入分別以 奶牛 和 語言 為關鍵字, 用鄰接矩陣存儲(這里必須用到vector)
(2) 合并說相同語言的牛, 得到m個集合, m-1即為最少數量
(3) 遍歷N個點, 若該節點所在集合未被遍歷, 則標記遍歷并輸出
*vector的用法: 非常適合稀疏圖的鄰接表的數組實現
(0) 聲明變量: vector<int> A;
(1) 加入元素: A[i].push_back(elect);
(2) 獲取某列元素個數: A[i].size();
(3) 獲取某個具體元素: A[i][j] //0 <= j < A[i].size(), 注意范圍
還有一道kruskal和兩道tarjan以及dij+heap
11.3
NOIp07真題, 3h, 300
P1: 模擬, AC
P2: 字符串, AC
利用flag表示是否輸出(僅標記), 然后Expand函數三重循環即可.
*考慮這種情況1-2-7, 以及A-B
P3: DP, 90(本地壓四位后90)
[狀態] f[k][i]表示當前行長度為k, 行首編號為i
[方程] f[k][i] = max{f[k-1][i+1] + A[i] * 2^(L-k+1), f[k-1][i] + A[i+k-1] * 2^(L-k+1)}
[初始化] f[1][1..N] = 2^L * A[i]
*變量打混, 務必靜態查錯
*高精度寫掛
(1) 進位
(2) 輸出0(去掉前導0的時候, 保證len>0)
*print可以特判len<0輸出0
(3) 雙目運算符必須const, 這是一個很好的習慣, 避免值發生不必要的改變;
*返回的bign盡量新建.
*最大測試點, 本地0.9s, RQ0.4s, Tyvj0.0s
P4: Floyd+亂搞, 50minAC(計時賽無分數)
(1) Floyd求任意點最短路, 記錄最大值(即直徑)
(2) 對d(i, j)=直徑的邊, 求路徑
(3) 對于每個直徑, 求出它的所有路徑, 然后對每個路徑求其他點到此路徑的最大值(dist操作, 某點到此路徑的最小值)
*點的情況需要特判
*注意區分最大/最小值, 這題考的就是對于抽象模型的理解能力
*有線性時間做法
東方幻想鄉Stage2, P3, 60棧崩潰
11.4 & 11.5
叉姐模擬賽, 140/300
P1: 字符串處理, 卡通配符含義, 30
(1) 讀入, 可以利用數組+標記字符 或者 vector
for (int i = 0; i < n; ++ i) {
begin[i] = sumLen;
scanf("%s", str + begin[i]); //給出字符串首指針
len[i] = strlen(str + begin[i]);
sumLen += len[i];
}
*str記錄字符串, begin記錄起始位置, len記錄長度
*vector必須手工轉換, 不能直接利用scanf讀入
(2) 標記*位置(初始化為strlen(p), 注意沒有*的情況)
(3) 從起始位置掃描一次, 區間[0, pos)
從終止位置掃描一次, 區間(pos, len-1]
P2: 最大帶權生成樹, Kruskal變種. 寫了一個生成子集, 40
[AC做法]
(1) 判斷無解[鄰接表 + BFS]
*注意變量名
(2) 邊i的權值為w[A[i]] + w[B[i]], 根據度的定義容易得到.
之后套用Kruskal, 降序排序即可.
[40%做法]
(0) 判斷無解
(1) 位運算生成子集(N <= 20) -> 亦可DFS生成C(N-1, M)集合
(2) BFS驗證連通性
(3) 計算權值
*一開始看錯范圍, 認為必須用O(N)算法, 然后不考慮排序. 權值最大 -> 度最大, 貪心無能.
P3: 動態規劃, AC
利用恒等式\sum{x_i * x_j} = 1/2(\sum{x_i}^2 - \sum{x_i ^ 2})
可以通過觀察, 或者數學證明最值只在極值點取到.(60%算法, 直接枚舉)
因而要求\sum{x_i * x_j}最小值, 即求\sum{x_i}^2的最小值
\sum{x_i}的最小值, 可以對所有數進行容量為\sum{A_i}/2的0/1背包, \sum{A_i}/2 - 2 * f[\sum{A_i}/2]即為答案.
*gXX給出了利用一次函數的證明方法, (待補)
*對于此類數據類型誤導題目, 可以通過數學推導, 或者編程實驗證明.
[標程做法] by ftiasch
(1) 討論極值位置
固定x_1, x_2, ..., x_{n - 1} .
f(x_n) = (x_1 + x_2 + ... + x_{n - 1}) * x_n + () ...
這是個關于x_n的一次函數, 所以只有在端點處才會有極值.
x_1 * x_2 + (x_1 + x_2) * x_3 + (x_1 + x_2 + x_3) * x_4 + ...
(2) DP
dp[i][j]表示前i個數, 在x_1 + x_2 + ... + x_i = j的情況下的答案, 轉移就是枚舉現在是弄個+a_i還是-a_i。
NOIp06真題, 3h, 120 >_<
P1: 環狀區間DP, 10
(1) 方程
f[i][j]表示合并第i顆珠子的頭標記到第j顆珠子的尾標記的最大值
f[i][j] = max(f[i][k] + f[k][j] + A[i]*A[k]*A[j]) (i <= k <= j)
(2) 實現
改寫方程
f[l][i]表示從i開始, 合并l顆珠子(指頭標記)的最大值
f[l][i] = max(f[k][i] + f[l-k][i+k] + A[i]*A[i+k]*A[i+l]) (1 < k < l)
*注意下標; i的枚舉范圍是[1, 2n-1], 環狀; -> 當成鏈做只有50
*和一般的區間模型最大的不同, 在于頭尾標記, 事實上比較可行的方法是在草稿上按照要求畫出珠子, 以檢驗下標;
P2: 簡化版孩子背包 -> 分組背包, AC
*Nettle的某道模擬題和此題的命題思路如出一轍, 都有兩種做法, 一種是直接套用更復雜的模型, 另一種是改變現有模型. 要充分挖掘問題性質.
P3: 模擬, 10
(1) 找空擋
從time[opt[k]][count[opt[k]]]開始
驗證區間長度
++Time //這里類似字符串匹配
(2) 在空擋標記時間
(3) 更新完成時間, finish[opt[k]][count[opt[k]]] = Time + time[opt[k]][count[opt[k]]] - 1;
(4) 更新最后完成時間
*一定要在草稿紙上寫出流程和關鍵語句
P4: 遞推, 沒時間, 6h
題目中第二次描述給了很關鍵的暗示(看了BYVoid的題解豁然開朗, 捶胸頓足中):
[狀態] f[i][j]表示i為2^k進制數最高位為j
[方程] f[i][j] = \sum{f[i-1][m]} (j+1 <= m < 2^k)
ans = \sum{f(m, 0)} (3 <= m <= w/k + 1) + \sum{f(w/k + 1, i)} (1 <= i < 2^(w%k)-1)
*可以直接利用記憶化, calc[][]標記是否計算, int70, 高精90
*由于題目的范圍很大, 考慮滾動數組(注意每次計算初始化), 遞推計算f[][], 累加同時進位, 高精度壓位, 大概第10個點1.35s. 去掉了運算符重載, 第10個點0.9s.
*這題屬于典型卡常數, 賽場上, 能觀察出方程并調出70分即可, 時間充裕可以考慮調試90分.
*注意運算符優先級(10)
*高精度調試技巧
(1) 初始化(初始化位置)
(2) 進位(模擬手算)
(3) const(防止修改不應修改的值)
rqnoj 341[SPFA], 40min
(1) 無向圖看成有向圖
(2) 漏打循環隊列
(3) first[]初始化錯位
*草稿紙很重要!!!
11.6
叉姐模擬賽, 210/300
P1: 2個trick, long long, 還有范圍
P2: 0/1背包變形
預處理, 以c[i] - v[i]為關鍵字升序排序
P3: 二分圖判定
*無向圖, 考慮兩條邊
*描述歧義, 特判沒寫, 不說了, 浪費了2h
NOI 2001 食物鏈[并查集], WA
和之前的做法完全不同, 題目是環狀依賴.
*尼瑪今天寫check.bat都不check..
[題解]http://winterlegend.blog.hexun.com/25409221_d.html
NOIp04 合并果子[小根堆, STL實現]
學習STL中的優先隊列:
[聲明] priority_queue<int, vector<int>, greater<int> > q;
*小根堆, greater; 大根堆, less;
[彈出隊首] q.top(); q.pop();
[加入元素] q.push(k);
ftiasch, 2010114模擬賽
P1: NOIp10第三題, 判定二分圖
P2: 找個兔子, 在不超過L的范圍斷開, 直接驗證
P3: 把每個時刻的蘿卜加入堆(當前時刻沒有, 則添加下一時刻), 維護當前時刻最大值, 累加即可.
P4: 最小生成樹 + 背包
對于一條路(i, j), 需要消耗D(i, j)個同類型的蘿卜, 因而需要一次0/1背包.
NOIp04 合并果子[小根堆, 手寫heap]
堆只維護隊首元素最小值, 不對隊中其他元素負責.
up() 直接上翻
down() 盡量取2*k+1(目的就是找到最小值), 然后下翻
11.7
Contest MAR11 packdel[dij+heap], 1h
(1) dij+heap元素出隊時, 標記已計算(done[k])
(2) 手寫可以用cmp函數比較, 注意A[k]與k的區別
叉姐模擬賽,
*手工修正了50%的數據..什么狀況
NOIp10, 引水入城[BFS+貪心+分析]
*認真讀題, 題目僅考慮最下面一行是否有水, 卡了40min
(1)無解, 30
對第一行進行floodfill即可, 可以BFS實現
(2)有解, M <= 10, 50, 25min
二進制生成子集, 然后利用floodfill填充, 并判定是否滿足題意, 維護最小值即可
(3)有解, AC, 2.5h
[重要結論]有解當且僅當, 第一行某個城市流經最后一行城市的結果連續.(若不連續, 必然不滿足題意)
因而可以將題目轉化為最少線段覆蓋問題.
利用鄰接表維護當前點的線段(注意退化為點的情況), 貪心過程如下:
1) 從L = 1開始, 對于(L, R), 維護最大的R_Max
2) 更新L = R, R = R_Max+1(左閉右開區間)
3) 重復以上步驟, 直到R > M
*貪心問題, 以及和區間有關的問題不熟悉, 待閱<淺談信息學中的區間問題>
*要在紙上寫出關鍵條件和大致算法流程以及語句, 不要把時間浪費在調試上
待閱<淺談信息學中的區間問題>
*閱畢, 涉及到了白書上三類區間問題
11.8
Tyvj1038[RMQ -> ST], 1.5h
ST算法(RMQ問題, 離線算法, O(NlogN)建表, O(1)查詢)
[狀態] f[i][j]表示從[i, i + 2^j - 1]的最值
[方程] f[i][j] = max{f[i][j-1], f[i + 2^(j-1)][j-1]} (以j為階段; 1+(1<<j)<=N, 保證實際意義合法)
[查詢] 對于區間[i, j], 令k = [log2(j-i+1)], 答案即為max{f[i][k], f[j - (1<<k) + 1][k]}
*不要相信樣例的調試性, 寫make, 或者打小數據手算
Tyvj1297[ST], 40min
*log_2打錯, 不妨自己寫函數
Tyvj國慶新賽制模擬賽, Day2P2, game[單調棧+ST], 1.5h
(1) 單調棧, 維護L[i], 表示A[L[i]..i-1] <= A[i]
while(A[L[i] - 1] < A[i])
L[i] = L[L[i] - 1];
(2)ST
*檢查方程和查詢的寫法, 靜態調試, 別盲目做
*認真讀題
NOIp08, message[雙進程DP],50min
[狀態]f[k][i][j]表示從(1,1), 兩人分別走到(i, k-i), (j, k-j)的最大值
[方程]f[k][i][j] = max{f[k-1][i][j], f[k-1][i-1][j], f[k-1][i][j-1], f[k-1][i-1][j-1]} + A[i][k-i] + A[j][k-j] (i != j)
[答案]max{f[M+N][M-1][M], f[M+N][M][M-1]}
*注意狀態的實際意義
*注意不要隨便用簡化寫法, 事實上簡化寫法是最可能出問題的地方
Tyvj國慶新賽制模擬賽, Day1P3, maze1[雙進程DP], 1h
*注意讀題, 每個格子可能有不只一個面包圈
方程和上一題一樣, 說一下如何記錄方案:
利用數組t1[k][i][j], t2[k][i][j]分別表示兩個人走的途中可以吃到的最多的面包圈, 答案在其中取最大值即可. 標程把對每個格子面包圈的個數的計算加入了方程中, 從而避免了討論.
*這兩天做陳題發現問題, 由于對于題目殘存的印象導致的讀題問題非常多.
Tyvj國慶新賽制模擬賽, Day2P1, ship[計算幾何], 15min
典型的卡讀題的題目, 穩定的定義是, 正多邊形的幾何重心落在最高的柱子們構成的多邊形中(不能在邊界).
直接檢查下標即可, 連續兩最高柱子的下標只差小于(N+1)/2
Tyvj國慶新賽制模擬賽,Day2P3, maze2[二分+BFS]
*學習了白書上的二分查找上下界的方法, 并注意到是左閉右開區間.
-> 按照當時帖子的說法, 標程錯誤, 修正一處后仍然WA.
11.9
叉姐模擬賽Stage4, 50 + 40 + 0 >_<
P1: 高精度
裸的高精度. 自己寫個30%算法跑一下可以發現, f[A][B] = A*B-1(好吧那個奇葩的遞推式怎么YY出來的)
*三處寫掛: (1)數組范圍 (2)len的計算(乘法和加法不同, 要命的是還手工屏蔽了小數據) (3)進位(其實不需要特判)
*一句話總結高精度寫法
[加法]更新位值, 累加, 進位, 退位
[乘法]更新位值(不同), 累乘, 進位, 退位
*注意的情況, 進位(比如10)
[背景]其實是有塊a * b的巧克力, 你要把他掰成1 * 1的巧克力, 求要掰多少次
P2: 枚舉
[關鍵結論]值最小的聚集點一定在某個點的x上, 某個點的y上(可以考慮證明一維的情況, 然后推廣)
*昨晚的討論不充分, 錯誤的認為值最小的聚集點一定和某個點重合, 且任意多點在某點聚集等價(事實上僅在兩點的時候成立, 今天發現30%程序是錯的)
然后枚舉每個x,y, 計算每個點和他們的曼哈頓距離, 排序后累加前k個, 維護最小值.
復雜度大概是O(N^2 * NlogN)
*改寫程序務必注意循環變量是否打錯
P3: DP
*現場的時候NC了, 寫了一個DFS, 大概能處理N <= 8的情況
(1) 50%做法
[狀態]f[i][j][k]表示取到A[i], B[j], C[k]的最小值
[方程]f[i][j][k] = min{f[i-1][j][k] + A[i]*p, f[i][j-1][k] + B[j]*p, f[i][j][k-1] + C[k]*p} (p = i+j+k)
[初始化]f[0][0][0] = 0;
(2) 100%做法
[狀態]f[i][j]表示取到A[i], B[j]的最小值
[方程]f[i][j] = min{f[i-1][j] + A[i]*p, f[i][j-1] + B[j]*p} (p = i+j)
[初始化]f[0][0] = 0;
[記錄方案]按照f[i][j] == f[i-1][j] + A[i]*p倒推, 循環即可, 注意邊界.
*直接記錄t[i][j] = i的話, 需要注意i==j的情況, 這里應該按照方程的實際轉移處理, 而這樣的情況很多, 所以沒必要使用;
*先對序列A,B進行一次DP, 得到A和B合并后的序列D, 然后對C,D進行DP, 即可得到結果
*想不出來的題目可以敲暴力觀察, 或者畫畫圖; 暴力程序一定要寫, 一方面啟發思路, 另一方面驗證正確性.
叉姐模擬賽Stage3, 20 + 60 + 0 >_<
*從哪里跌倒要從哪里爬起來...
P1: 模擬, 求外表面積(不考慮內部表面積)
[1] 對每個立方體的邊界染色, 然后從六個面逼近
*對于有洞的情況會掛, gXX表示不會, 原因不知.
[2] 正確做法
(1) 對每個立方體的邊界染色, 維護最大坐標
(2) 從(0, 0, 0)開始BFS,
i, 已染色的點不標記已讀(遇到的Cnt++, 但不入隊)
ii, 未染色的點標記已讀
*標程范圍開小, 已經更新數據
P2: 枚舉
考慮僅有三個數的情況:
操作前a, b, c 差分為(b-a, c-b)
操作后a, a+c-b, c差分為(c-b, b-a)
可以發現操作的實質就是交換差分.
不妨設d[i] = A[i+1] - A[i],
那么A[i] = A[1] + \sum{A[j]}(1 <= j < i)
即\sum{A[i]} = N*A[1] + \sum{d[i] * (N-i)}(1 <= i < N)
*注意范圍會爆int, 要用long long; 注意下標;
P3: 查找中位數[數據已修正]
(1)60%做法
對每個區間復制一次, 然后qsort
(2)AC做法 by gXX, 實現無能
大意就是想把所有區間的中位數搞出來。其實可以用堆吧？
就是枚舉一個左端點, 一個一個往里面加, 然后用兩個堆來維護中位數。就是一個最大堆一個最小堆, 然后不斷丟來丟去的過程。
呃。大概就是相當于要維護第k大這樣的吧。開一個最小堆, 里面只有k個元素, 而且是最大的k個, 然后其他的丟到最大堆里面。
然后當你k要增大的時候,就把最大堆的堆頂拿過來。要減小的話, 就把最小堆的堆頂丟過去。
就是這個意思, 此消彼長, 道法自然。
11.10
NOIp09 靶形數獨[DFS+剪枝]
*手工指定搜索順序, 1.5h調試無能
*題目中不考慮對角線, 手工順序無效!!!
利用frist[][], second[][], grid[][]分別表示每個行/列/小九宮格的填數情況, countX[], countY[]統計一開始行列的填充情況.
(1) BFS生成score[][]
(2) 讀入數獨, 統計countX[], conutY[], 記錄填充情況
(3) 對countX[], countY[]進行降序間接排序
(4) DFS, 狀態DFS(x, y, sum)
1) x == N+1, 統計答案
2) y == N+1, 換行
3) (x, y)已填充, 更新sum
4) 枚舉A[mapX[x]][mapY[y]], 所有涉及值的地方按照map_[]順序
*[動機]不必要的枚舉量, 優化搜索順序
*90%的測試點在1s內, 1h內可以調試完
NOIp04 蟲食算[DFS+剪枝], N h
*注意讀題, 是N進制加法, 每個字母代表的數字不同
(1) 70分做法
DFS枚舉序列1..N代表的數字, 利用used[]判斷當前數字是否使用過
[剪枝]對于豎式上同一列的三個數a,b,c, 顯然滿足c - (a+b) < 2
*注意各種回溯細節
(2) 80分做法
對每一位進行枚舉, 判重和可行性剪枝
*回溯只需一解的情況下, 要注意恢復修改值的時間
*進位要用delta記錄, 可能出現多次進位的情況
*else和if的匹配錯誤, 注意花括號!!!!!!!!
*70分做法的剪枝用了沒效果, 網上還有一個剪枝, 同一列三數知二的情況下, 看剩下那個數的兩種情況能否使用, 可能可以AC
東方幻想鄉Stage1P4[強連通分量, kosaraju實現], 40min
(1) 正向對每個點進行DFS, 搜索完該點后加蓋時間戳
(2) 邊反向, 按照時間戳逆序DFS, 標記根節點
*NOIp09第三題用了類似的邊反向的做法
WZOIStage2 P2[SPFA], 20min
范圍很大, 題解給出的AC做法是DAG的DP,事實上SPFA可以AC.
11.12
敲Day1P2三種版本, 實測ST+鄰接表, N <= 30000; 裸的做法, N <= 15000