最近開始寫trie樹，trie樹還可以和并查集一起運用。
poj 3283是一道典型的trie樹問題，為了節約malloc的時間，我靜態生成需要申請的內存，然后自己管理。由于預估poj的數據比較弱，所以這個方法可行。
為了測試需要開辟空間的大小，我無恥的用小號不斷的刷，終于確定了大小。
用大號提交上去之后，饒有興致的看了一下排名。悲劇的發現，居然是第二名 63ms，而第一名是我無恥的小號littlenumber 47ms。我擦....
posted @
2010-09-22 22:39 margin 閱讀(112) |
評論 (0) |
編輯 收藏
今天做了一個奇怪夢，像看了部電影一般。醒來后居然都記得。故事有點科幻，有幾個主人公，記錄一下。
---------------------------------
在現代化的大城市中心街區中，走來一伙人。有的西裝革履，有的嘻哈打扮，他們的眼神很奇怪。為首的是一個穿白大褂的學者，他高而瘦，帶著眼睛，眼里射出冰冷的目光。這伙人最終在一個立交橋下停了下來，他們好像在鞭打什么。
一旁走來了三男三女，很好奇的，湊上一看。好像其中有三個人在欺負橋下的乞丐。他們拳打腳踢，甚至鞭笞那個乞丐。終于其中一名男子再也忍受不住大喝到“住手”，此人老實敦厚，但看上去正義凌然，應該是一名退伍軍人。其他兩個男人也邁步向前。
教授示意了一下三人停手，然后頭朝來人一拱，示意讓三個手下解決掉多余之人。三人齊上，同正義方三人一起打起來。正義一方中另兩為一個衣著時尚，英俊帥氣，貌似應該在一些聲色場所做DJ之類；另一人呆頭呆鬧，但穿著保安的衣服。三個女人中有一個人是保安的妻子，看上去結婚多年。另一人衣著時尚，面容姣好應該是個小白領；最后一個人簡簡單單，普普通通，但是眼中透著股靈氣，其實是個記者。
保安的妻子擔心丈夫，竟直接向教授進攻去了。很奇怪的戰斗，那伙匪徒每個人都好像在被動挨打，沒有有效的反抗。教授被女人扇了幾個耳光后，嘴角有絲血跡，但是似乎冷笑了一下。
大戰的結局，這伙匪徒居然被幾個人打炮了，而那個乞丐也不見了。莫名奇妙，白領在一旁看著DJ很有愛慕之意想要上去搭訕幾句，被冷冰冰的回絕；女記者心中充滿疑問，詢問了幾個人聯系方式后，向那伙人逃走的方向走去。。。
[從這里開始故事開始分支]
女記者的故事
女記者跟蹤那伙人，居然發現這伙人不是這個世界上的人，或者說他們是另外一個空間的人。有的人是去世后可以到這里獲得新生，有些人卻來這里協助他們在做一些工作。女記者潛入后，發現這個團伙其實在做一些有意義的事情。在她了解到了真想之后，她主動的來到他們的世界。
保安的故事
保安是個憤青，他為自己家庭的生活壓力大而煩惱。但是卻恨自己頭腦簡單而掙不了更多錢，妻子也在外面拼命的打工。女記者來到保安家里，暗示可以去某個地方看看增加自己的競爭力。保安來到后發現是一個教室，教室中有些書籍。（具體的略過）他居然發現講課的人就是白衣教授。教授用那天他對待別人的方式對待保安自己，仿佛在暗示輪回和因果的關系。保安激動的想獲得了真理，并開始在為這個組織做事。后來有拉了他老婆入伙。他老婆入伙的方式也和那天情景相識。
女白領和DJ的故事
（具體的不記得了）DJ是一個有自閉癥的人，不知與別人相處。女白領發現他周圍很多女性，但DJ似乎都沒有什么興趣。DJ死于一次意外后，來到了教授的旗下。女白領在得知消息后，非常沮喪。但居然有一天在街上再次看到DJ的背影后，開始懷疑。（之后略）
退伍軍人的故事
退伍軍人是一個強迫癥患者，他與他的妻子雖然在一起但是沒有任何的感情，他的妻子不了解他。最后在若干年后他才來到教授的世界中，他終于找到了解開心結的方法。
大結局
保安夫妻很幸福，女記者幫助退伍軍人重新認識自己，退伍軍人看到自己的妻子也找到另外一半；女白領付出了很多，DJ終于慢慢的開竅。
--------------------
有很多細節忘記了，但是總之故事很離奇，也很完整。我驚嘆有這樣的夢，懷疑自己是不是被inception了。
posted @
2010-09-19 09:20 margin 閱讀(141) |
評論 (2) |
編輯 收藏
初期:
一.基本算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)
(5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增廣路算法(KM算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸并排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單并查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同余模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中級:
一.基本算法:
(1)C++的標準模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網絡流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高級應用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)
五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩余定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429
)
高級:
一.基本算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和 在線算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移
的
目的). (poj2823)
(4)左偏樹(可合并堆).
(5)后綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲
狀態、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大
、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263
)
posted @
2010-09-01 17:09 margin 閱讀(177) |
評論 (1) |
編輯 收藏
這是一題相當有水平的并查集問題。雖然我一次性ac，但是基本上是沒有任何思路搜索了一下牛人思路才過的。
思考這題時，我陷入到了以下怪圈：
1.并查集應該是無限的，但是貌似這題的并集只有三個
2.當兩者關系未被確認是哪個集合時，會出現無限多的臨時子集
3.如何表示臨時子集
看了看牛人的思路，相當巧妙：并查集基本還是無限集，有限集用關系向量來表示。
1.使用關系向量的方法，讓我獲益匪淺。
2.計算關系向量的方法，又如此的巧合。
3.并查集并不一定是相同的才并一起，又回歸到第一點，當關系向量可以用有限集表示時，并查集里的元素可以不是同一類元素。
最后還要說，這題相當牛B.
#include "stdio.h"
#define MAX 50001
#define Similar 0
#define Enemy 1
#define Food 2
// Food eat Enemy
// Enemy eat Similar
// Similar eat Food
struct _xtree
{
int parent;
int relation;
}xtree[MAX];
int N, K;
void build()
{
int i;
for (i = 1; i <= N; i++)
{
xtree[i].parent = i;
xtree[i].relation = Similar;
}
}
int find(int i)
{
int p = xtree[i].parent;
if (p != i)
{
xtree[i].parent = find(xtree[i].parent);
xtree[i].relation = (xtree[p].relation + xtree[i].relation) % 3;
}
return xtree[i].parent;
}
int check(int x, int y, int r)
{
int root_x, root_y, root_r;
if (x > N || y > N)
{
return 0;
}
root_x = find(x);
root_y = find(y);
if (root_x == root_y) // x relate y
{
return (xtree[x].relation - xtree[y].relation + 3) % 3 == r ? 1 : 0;
}
else
{
root_r = (xtree[y].relation + r + (3 - xtree[x].relation)) % 3;
xtree[root_x].parent = root_y;
xtree[root_x].relation = root_r;
return 1;
}
}
void main()
{
int op, x, y;
int count = 0;
scanf("%d %d", &N, &K);
build();
while (K--)
{
scanf("%d %d %d", &op, &x, &y);
if (!check(x, y, op == 1 ? Similar : Enemy))
{
count++;
}
}
printf("%d\n", count);
}posted @
2010-08-28 21:11 margin 閱讀(160) |
評論 (0) |
編輯 收藏
tle和wa 到麻木.... 又一題并查集。這周做題時間少了很多，原因工作太忙，準備晉升。希望晉升成功！
posted @
2010-08-28 00:18 margin 閱讀(107) |
評論 (0) |
編輯 收藏
上周ac了3道 基本的線段樹。這周開始做并查集，慶祝一下poj達到40題，雖然都是水題居多。
posted @
2010-08-22 23:49 margin 閱讀(81) |
評論 (0) |
編輯 收藏
連續兩天AC了兩道線段樹經典題目。
3277用了157ms居然排到了第三，哈哈哈哈....
posted @
2010-08-18 00:45 margin 閱讀(66) |
評論 (0) |
編輯 收藏
摘要: 線段樹經典解決問題poj1151，計算圖形覆蓋總面積。1.用了半小時寫了一個簡單算法，看了看測試數據沒過，原來理解題意錯誤。（如果提交就是WA）2.然后又用了樸素的枚舉，這次是TLE，看來是水平不行，要學習學習別人的思路了。3.看完別人代碼后，花了半天用自己的思路寫了一遍，RTE。4.原來是數組設小了，再次提交PE。4.最后居然是要輸出兩個換行，暈倒!AC線段樹的應用還有很多，就此題來說基本的思維...
閱讀全文
posted @
2010-08-15 23:38 margin 閱讀(258) |
評論 (0) |
編輯 收藏
Bridge模式看過很多遍，說實話沒看懂過。今天終于覺悟....
Bridge模式的定義是：將抽象和實現解耦。
這個定義是最讓人費解的，抽象和實現解耦和Bridge有什么關系，特別是UML的圖形給出來的時候更讓我感覺到這個定義的匪夷所思。
下面來舉個例子吧：
我很久前遇到的問題就是：寫一個系統，當輸入可能內存、文件.....而輸出可能是內存、文件等等的時候。如果按照C接口的定義方式，你可能要做一下的定義。
MemToMem()
MemToFile()
FileToMem()
FileToFile()
一下就要定義2x2的接口，而如果在增加一個輸入，那么就是2x3的接口，再增加同樣的輸出就是3x3的接口。
如果在C++里面，就是有雙重的集成關系，首先是基類，然后是n中輸入類，再來就是n^2個輸出類。
所以Bridge模式要解決的就是這種變化關系。
Bridge模式的思想就是將n個輸入類和n個輸出類解耦（抽象和實現接口）讓他們分別依賴自己的基類，而最終通過組合的方式讓兩者分離。
簡單的代碼
class Input
{
public:
virtual void Do() = 0;
private:
OutPut pObj;
}
class InMem : public Input
{
public:
virtual void Do()
{
pObj->Out();
}
}
class OutPut
{
virtual void Out() = 0;
}
class outMem
{
virtual void Out()
{
// do something
}
}
ps.此文檔之作為技術的隨筆，供以后搜索，如果疑問概不回答。
posted @
2010-07-31 18:26 margin 閱讀(842) |
評論 (0) |
編輯 收藏
昨天，玩推箱子游戲玩到第四關實在過不去了，用C++寫了一個BFS+DP的算法求解。結果是170步。
其實我一開始是想用python來寫的，但是覺得二位矩陣這個東西很難用python來描述，于是作罷。寫完后看看自己的代碼，覺得惡心的不行。于是在網上搜索了一下，發現大牛居然可以把python寫得如此之簡潔，又一次拜服了！
《
用python求解迷宮問題》
http://v.youku.com/v_show/id_XMTcwMzc5MTAw.html下面是我按照視頻里面敲的python代碼，我的實在垃圾就不拿出來了。
這段代碼最然我感到驚嘆的是他對迷宮模型的表示方式，二位矩陣就如此輕描淡寫的表示出來！
ps,網頁代碼的對齊有點問題。
1ASCII_MAZE = '''
2+----------------+
3| | | |
4| | +--+ ----+ | |
5| | | | |
6| | +---- | | |
7| | | | | E
8+---+ | | | | |
9S | | | |
10+------+--+--+---+
11'''
12PATH,START,EXIT,VISITED, SOLUTION = " SE.o"
13
14class Maze():
15 def __init__(self, ascii_maze):
16 self.maze = [list(row) for row in ascii_maze.splitlines()]
17 self.start_x = [row.count(START) for row in self.maze].index(1)
18 self.start_y = self.maze[self.start_x].index(START)
19
20 def __repr__(self):
21 return "\n".join("".join(row) for row in self.maze)
22
23 def solve(self, x = None, y = None):
24 if x == None:
25 x = self.start_x
26 y = self.start_y
27
28 if self.maze[x][y] in (PATH, START):
29 self.maze[x][y] = VISITED
30 if self.solve(x + 1, y) or self.solve(x - 1, y)\
31 or self.solve(x, y +1) or self.solve(x, y -1):
32 self.maze[x][y] = SOLUTION
33 return True
34 elif self.maze[x][y] == EXIT:
35 return True
36 return False
37
38
39if __name__ == "__main__":
40 import sys
41 sys.setrecursionlimit(10000)
42 m = Maze(ASCII_MAZE)
43 if m.solve():
44 print m
45
46
posted @
2010-07-18 17:20 margin 閱讀(1524) |
評論 (0) |
編輯 收藏