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