做男人不容易系列

做男人不容易系列:是男人就过8题

1737 Problem A Connected Graph
1738 Problem B An old Stone Game
1739 Problem C Tony's Tour
1740 Problem D A New Stone Game
1741 Problem E Tree
1742 Problem F Coins
1743 Problem G Musical Theme
1744 Problem H Elevator Stopping Plan
=========================

男人們努力了

AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA

紀念一下

可惜可距太大

效果不好

由 數正方形 到 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)

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