由 數正方形 到 Map, Hash, Set

事源是發生在 pku 2002 Squares，和 gguy 剛做了的 pku 3432 Count Squares

題目大意是有 N 點，問 N 點中有多少個正方形 ?

對於已知的兩點，可能組成的正方形只有兩個，

我的方法是兩個 for loops，然後看看這兩點對應可能組成的正方形的另外兩點是否存在。

所以 time complexity 是 O(n*n*?)。 ? depend on the method you implemented.

我試了三種方法，

1) Map，把 point map 去 bool，試時看看 map 完後是否 return true ;

2) Hash，把 point 用 hash 放入 array 中，試時看看找不找到該 point ;

3) Set，把 point 放入 set，試時看看該 point 是否在 set 之中;

結果

1) Map => TLE ，不知 time complexity

2) Hash => Accept , 超快 ，O(1)

3) Set => Accept , 中速， O(logN)

數據如下 :

===================================

Result Memory Time Code Length
Set AC 476K 3000MS 517B
Hash AC 1388K 641MS 1081B
Map TLE 684B

===================================

Map 不是不好，只是在這情況下這樣用 Map 不好，
當 array 可能要開到 a[1000000000]時，但又不是每個元素都用得著，
這時用 Map 模仿 array ，可以省下很多 Memory。

另外，也難保有第二種方法用 Map 可以在這題表現得比 Set 好。

===================================

Map 基本用法 :
1) include map

轉貼 - 大牛給的計劃

在 google 搵到，來自 猴哥樂園的好東西，值得參考一下 !

看完，就知道自己識的只是皮毛 ......


-------------

大牛給的計劃——
一般要做到50行以內的程序不用調試、100行以內的二分鐘內調試成功.ACM主要是考算法的,主要時間是花在思考算法上，不是花在寫程序與debug上。

下面給個計劃你練練：

第一階段：練經典常用算法，下面的每個算法給我打上十到二十遍，同時自己精簡代碼，
因為太常用，所以要練到寫時不用想，10-15分鐘內打完，甚至關掉顯示器都可以把程序打
出來.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用並查集，不好寫)
3.大數（高精度）加減乘除
4.二分查找. (代碼可在五行以內)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡)
7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.
8. 調用系統的qsort, 技巧很多，慢慢掌握.
9. 任意進制間的轉換

第二階段：練習復雜一點，但也較常用的算法。
如：
1. 二分圖匹配（匈牙利），最小路徑覆蓋
2. 網絡流，最小費用流。
3. 線段樹.
4. 並查集。
5. 熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類算法。博弈樹，二進制法等。
7.最大團，最大獨立集。
8.判斷點在多邊形內。
9. 差分約束系統.
10. 雙向廣度搜索、A*算法，最小耗散優先.
===========================================================


ACMer必備知識（這麼多呀，慢慢學了……

圖論

路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特征
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優化
差分約束系統
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造

生成樹問題
最小生成樹
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹

連通性問題
強大的DFS算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基

有向無環圖
拓撲排序
有向無環圖與動態規劃的關系

二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優匹配
穩定婚姻

網絡流問題
網絡流模型的簡單特征和與線性規劃的關系
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流

弦圖的性質和判定


組合數學

解決組合數學問題時常用的思想
逼近
遞推 / 動態規劃
概率問題
Polya定理


計算幾何 / 解析幾何

計算幾何的核心：叉積 / 面積
解析幾何的主力：複數

基本形
點
直線，線段
多邊形

凸多邊形 / 凸包
凸包算法的引進，卷包裹法

Graham掃描法
水平序的引進，共線凸包的補丁

完美凸包算法

相關判定
兩直線相交
兩線段相交
點在任意多邊形內的判定
點在凸多邊形內的判定

經典問題
最小外接圓
近似O(n)的最小外接圓算法
點集直徑
旋轉卡殼，對踵點
多邊形的三角剖分


數學 / 數論

最大公約數
Euclid算法
擴展的Euclid算法
同餘方程 / 二元一次不定方程
同餘方程組

線性方程組
高斯消元法
解mod 2域上的線性方程組
整系數方程組的精確解法

矩陣
行列式的計算
利用矩陣乘法快速計算遞推關系

分數
分數樹
連分數逼近

數論計算
求N的約數個數
求phi(N)
求約數和
快速數論變換
……

素數問題
概率判素算法
概率因子分解


數據結構

組織結構
二叉堆
左偏樹
二項樹
勝者樹
跳躍表
樣式圖標
斜堆
reap

統計結構
樹狀數組
虛二叉樹
線段樹
矩形面積並
圓形面積並

關系結構
Hash表
並查集
路徑壓縮思想的應用

STL中的數據結構
vector
deque
set / map


動態規劃 / 記憶化搜索

動態規劃和記憶化搜索在思考方式上的區別

最長子序列系列問題
最長不下降子序列
最長公共子序列
最長公共不下降子序列

一類NP問題的動態規劃解法

樹型動態規劃

背包問題

動態規劃的優化
四邊形不等式
函數的凸凹性
狀態設計
規劃方向


線性規劃

常用思想

二分
最小表示法

串

KMP
Trie結構
後綴樹/後綴數組
LCA/RMQ
有限狀態自動機理論

排序
選擇/冒泡
快速排序
堆排序
歸並排序
基數排序
拓撲排序
排序網絡

Dijkstra, less查

今天做一題dijkstra時，第一次submit TLE，然後加了一句優化再submit就變15ms了
其實那句平時都有打，只是剛好這次懶沒打... 想不到影響這麼大

假設用pair作為heap的index，first=path length，second=node number ; dis[x] 為 dis[start] 到 x 暫時的shortest path

while (!q.empty())
     t=q.top();
     q.pop();
     if (t.first>dis[goal]) break;
     for all v visit by t.second
          if (e[t.second][v]+t.first<dis[v])
                dis[v]=e[t.second][v]+t.first;                
                push v into q;

加了紅色那句後，原理是如果heap頂的shortest path distance己經大於己找到去終點的shortest path distance，由於沒有negative edge，之後找到的path都不會比現有的更短，因此可以查少幾條path

所以 Dijkstra 又名 less查 是有道理的

swap 比一比

以下有三種把 x 和 y 數值交換的方法及交換 400000000 次的時間 :

1 : t = x; x = y; y = t; ==> 2.55s
2 : swap(x,y); ==> 3.40s
3 : x^=y^=x^=y; ==> 4.20s

第一句最基本，最快
第二句是方便 C++ 人的東西，中速
第三句是型人專用，竟然最慢 .....

結論，想快用第一句，但我會用第二句，因為方便一點又清楚一點

反斗奇兵: Exhausion & Patterning

小弟一直都不喜歡做剪枝的exhaustion題... 所以今次想介紹一些不是直接exhaustion的頹題但又不是用剪枝法的題型

還記得JOE神講過的 HKOI 2006 Senior - Toggle 嗎?

題目大意:

有一個N*N的matrix﹐初始時每一格的value都是0 or 1
每一步可以把一整列或一整欄的0變做1，1變做0
目標是找出一種方法使整個matrix所有value變做0
(N<=18)

Sample:
N=4
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0

解法: 反第3欄和第3列

這題是dp? greedy?
如果沒估錯的話，以上2種方法都做不到的... 那就只剩下exhausion了... 但 O(2^(2n)) 又會TLE

Observation 1: 反row/column的次序不影響結果 事實上，m[i][j] 的最終value 只是取決於反row i 與反column j 的次數之和

Observation 2:
每column/row不會反>1次
明顯地，反2次=白反(不是白飯)，反3次=反1次...

所以，正確解法就是
exhaustion反哪些column，之後對於每一row，若全部=0就不反，全部=1就反，部份=1就代表exhaustion出來的反column組合不正確

Time complexity: O(N^2 * 2^N)

做這些題目，重點就是觀察形狀和特性，甚至不用exhaustion也能solve到

例子:

pku 3363 - Annoying painting tool
pku 3279 - Fliptile

加多題，

pku 3600 - Subimage Recognition

下面是這2條的解法

-------------------------------------------------------

pku 3363 - Annoying painting tool

題目大意:
和 Toggle 差不多，不過每次反一個r*c的長方形

(反該點 = 以該點為r*c長方形左上角來反)

Observation:
照舊，同一點不會反>1次，反的順序沒關係...

解法:
由最左上方至最右下方的次序來做，如果該點=1就反
因為若「此時不反，時機己晚」，由於是"左至右，上至下"的做，做到此時只剩下反這點可以使這點變做0
當然，反這點的長方形不能出界...
若果最後不能把所有變做0，則是no solution

sample:
4 3 2 1
011
110
011
110

011 // 不用反
110
011
110

001 // 反!
100
011
110

000 // 反!
101
011
110

000
001 // 反!
111
110

000
001 // 不用反
111
110

000
000 // 反!
110
110

000
000
010 // 反!
010

000
000
000 // 反!
000

000
000
000 // 不反
000

最後一列也要做，check有沒有漏下'1'未反，若有，即no solution

至於反後怎樣update個matrix
若O(r*c) 的反，整個time complexity = O(N^2*M^2)，很慢

其實每次反可視為把那該長方形內每格的count[i][j]+1
做到(i,j)時，該格的最新數值 = (matrix[i][j]+count[i][j])%2

要做到[修改一堆，query 1點]...
當然是...
2D BIT!
當然segment tree也可...
[修改一堆，query 1點] 的細節另文再談或等BIT之神whh講...

Time complexity = O(N*M*lg(N)*lg(M))

-------------------------------------------------------

pku 3279 - Fliptile

也是和 toggle 差不多，不過每次是反一個十字 (可反出界)

解法:
exhaustion第一列的反pattern，之後由第2行往下做，每一行左至右的掃，反不反是"沒有選擇餘地的"

Time complexity = O(2^N*M*N)

總結: 做這些題目要夠狠心，要令那些格沒有「反不反」的選擇餘地

談匈牙利算法 Hungarian Algorithm

匈牙利算法是小弟今天放學剛剛學會的一種算法，其實以前都略略聽過 ......

那是像匈牙利輕騎兵一樣，強得很的東西。

它可以用來解決二分圖模型的問題，包括部份網絡流問題 !

我看過幾個網頁，嘗試理解，

根據 匈牙利算法@百度，

匈牙利算法是無比抽象的東西，

增廣路徑、匹配M、集合M，just to name a few，我郁悶了。

再看看 匈牙利算法@維基，

雖然沒有文字解釋，但用心去解讀後，相信比較易去明白，

也明白了這個算法的運作很難只用文字表達......

建議看百度大概理解這算法是什麽，再看維基了解詳細運作。

算法輪廓 : 若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑。
(1) 置M為空
(2) 找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M
(3) 重復(2)操作直到找不出增廣路徑為止

看不懂還是看 WIKI 的 pascal code 吧。

---------------------------------------

例題 :

1 : pku 1274 The Perfect Stall

問題是有 N 隻母牛，M個倉，每日，每隻牛只會去某幾個倉渣一單位奶。
當中一個倉只能容納一隻母牛，請問最多可以渣多少單位奶 ?

解法 : 把二分圖，左邊為母牛，右邊為倉，牛倉關係為頂點路徑，製成二分圖，
利用匈牙利算法便輕鬆可解決。
(用網絡流也可以做到)

2 : pku 3041 Asteroids

問題是有 N*N 的距陣，某些格子有小行星，
現在最強武器褶櫈，它可以剷除一行或一列的小行星，
問最少要多少最強武器才可以消滅所有小行星 ?

解法 : 非常巧妙地把題目的距陣和小行星化成二分圖，
左邊為行，右邊為列，行星出現為路徑。
再利用輕騎戰術便解決了。

解釋 : 對於每一行 (橫向的row)，都會盡量去選除一粒小行星，分 A,B,C 三個 CASES :
A : 如果選到而小行星不是該行最後一個小行星，即代表最強武器會水平發射擊中該行所有小行星;
B : 如果小行星是該行最後一個小行星，即代表該行前部份的小行星已被上方的最強武器射中，最強武器會垂直射中該列所有小行星。
C : 如果沒有小行星被選中，即所有小行星被之前的最強武器的垂直攻擊打中。

3 : pku 2239 Selecting Courses

和 3041 相似的題目

4 : pku 2446 Chessboard

5 : pku 1466 Girls and Boys

6 : pku 1325 Machine Schedule

7 : pku 1469 COURSES

由 中國餘數定理 到 PKU 1006 Biorhythms

PKU 1006 Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006

題意是，給定 n 除以 23,28,33 的餘數及 d，現在要求 n-d 的最小值。

----------------------------------------------------------

說起中國餘數定理，就必定會想起"韓信點兵"。

用日常生活例子來說，你不知你朋友的年紀 y ，但問他 (y mod 3) --> r3, (y mod 5) --> r5 及 (y mod 7) --> r7 三個數可以輕易快速地計算 y。

y = (r3*70+r5*21+r7*15) mod 105

For example, 你朋友年紀 29 , r3 = 2, r5 = 4 , r7 = 1,

(r3*70+r5*21+r7*15) mod (3*5*7) = (140+84+15) mod 105 = 29。

原理是 :
70 除以 3 餘 1 ，並是其他兩數的倍數 ;
21 除以 5 餘 1 ，並是其他兩數的倍數 ;
15 除以 7 餘 1 ，並是其他兩數的倍數 ;

因此 15 無論加多少次都不會影響除以 3 及 5 的餘數。
而把 15 乘以 r7 便可以控制到除以 7 的餘數。
如此類推......

不妨稱 70 是 3 的"好數"，21 是 5 的"好數"，15 是 7 的"好數"。

現在問題是如何找出給定除數的"好數"。

例如新的一個系統給定除數 5,11,13,17， (除數最好要互質，否則有機會出現茅盾，如除4餘1，同時除2除0)

又給出 y,r5,r11,r13,r17，如何求 y 呢?

問題即是如何找出 r5,r11,r13,r17，

利用上述原理寫個程序，

for (i=1;i<5;++i) 5="=" y="(r5*2431+r11*9945+13*11220+17*715)" style="font-weight: bold;">一般化後的式子為，除數是 x1,x2,....xn，兩兩互質。

y = sum(rxi*xi的好數) mod product(xi) , for 1<= i <=n
--------------------------------------------

回到 PKU 1006，解決方法是找出 23,28,33 的"好數"，然後一條式子......

用以上方法代替暴力法，時間複雜度即可由 O(21252) 降至 O(1)。

輕鬆解決。

--------------------------------------------
題外話 :

若果這題的除數也是變量的話，則把預先計好的 rx1,rx2 .... rxn 的過程包含在程序中。

用這個方法代替暴力法，時間複雜度由 O(rx1 * rx2 * ... * rxn) 降至 O(rx1 + rx2 + ... rxn)。

基因改造優化粟米

http://acm.pku.edu.cn/JudgeOnline/problem?id=2019

pku 2019 - 粟米田 (con-field)

這題的特別之處，是有很多不同的algo都可以AC，所以想分享一下不同algo的做法和效率

題目大意:
有個N*N的matrix，每格儲住一個integer
現有K個query，每次抽問一個B*B的範圍中的max-min

(B<=N<=250, K<=100000) ------------------------------------------------------------------------

Algorithm 1: 直接搜索

很直接，每次query就掃哂整個B*B的地方
Time complexity: O(K*N^2)
由於只有N*N種問法，而K>N*N，所以記錄己問過的結果可以加快少少 (呢個方法同樣適用於下面的algo, i.e. K=N^2)
記錄結果的Time complexity: O(N^4)
雖然time complexity仍是很高，但據聞pku的數據很虧，所以仍是過到的

------------------------------------------------------------------------

Algorithm 2: 2D segment tree/2D binary search tree

由於segment tree的強項就是能O(lg N)地找到一段數據中的max, min，因此把它拓展到2D，就能找出一個2D陣列中的max, min
Time complexity: O(N^2*lg N*lg N)
快了很多，但缺點是2D線段樹很惡code，又易有bug
還有，線段樹的特點是要query的range係幾多都得，但呢題一早俾左個range你，所以應存在比segment tree更簡單的方法

------------------------------------------------------------------------

Algorithm 3: pre-compute 所有水平B格中的max, min

以test case做例子 (B=3)

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

假設先pre-compute 一個 max matrix

5 6 6 * *   // 5=max(5,1,2) ; 6=max(1,2,6) ; 6=max(2,6,3)
5 5 7 * *   // 5=max(1,3,5) ; 5=max(3,5,2) ; 7=max(5,2,7)
7 6 6 * *
9 9 8 * *
9 9 9 * *

這樣的話, 每次找一個正方形區域中的max和min時，只需垂直找一次就得了，因為水平的B格己經找了
例如query(1,2) [左上角為1,2的正方形]

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

最大值 = max(6,5,6) = 6
找min也同樣道理

每次query的time complexity: O(N)

問題是，要怎樣pre-compute?

方法一: 每一次都向右掃B格
Time complexity (pre-compute): O(N^3)

方法二: 用monotone queue (deque)

在找第一列的3個max時，
分別求了 max(5,1,2), max(1,2,6), max(2,6,3)

5 1 2 6 3
5 1 2 6 3
5 1 2 6 3

不難看出1,2,6都重覆求了
事實上，這正是sliding window問題
當要找的max/min的range是固定且在slide的時侯，
就可以用monotone queue找!
Time complexity (pre-compute): O(N^2)

query也有方法優化的
注意到每次query也是在max matrix中找一段的max

所以可以先把它轉化成1D segment tree
這樣，每次query的time只需O(lg N)
Time complexity: O(N^2*lg N)

真的不能再優化?
再看一次個max matrix

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

其實每次query就是找垂直相連B個中的max和min
那可以把他們都pre compute!!!

把max matrix pre compute 後的樣子:

7 6 7 * *    //  7=max(5,5,7)   6=max(6,5,6)   7=max(6,7,6)
9 9 8 * *    //  9=max(5,7,9)   9=max(5,6,9)   8=max(7,6,8)
9 9 9 * *    //  9=max(7,9,9)   9=max(6,9,9)   9=max(6,8,9)
* * * * *
* * * * *

同樣地使用monotone queue去做，總時間O(N^2) compute完畢
每次query: O(1)

Time complexity: O(N^2)

事實上，把max matrix和min matrix都pre compute後，每次query只是

scanf("%d%d",&x,&y);
printf("%d\n",max[x][y]-min[x][y]);

連記錄答案都不用...

monotone queue，繼BIT又一屈機之作

有左monotone，打code好輕鬆

各大 ONLINE JUDGE 連結

已放在各大戰場連結上，分別是:

PCOJ
http://pcoi.no-ip.org/~pcoijc/

POJ
http://acm.pku.edu.cn/JudgeOnline/

UVa
http://icpcres.ecs.baylor.edu/onlinejudge/index.php

ACMWORLD
http://acmicpc-live-archive.uva.es/nuevoportal/

USACO
http://ace.delos.com/usacogate

VIJOS
http://www.vijos.cn/Index.asp

TimusOJ
http://acm.timus.ru/

SGU
http://acm.sgu.ru/index.php

ZOJ
http://acm.zju.edu.cn/