解題報告
【奮戰2013regional】 hdu 1662 計算幾何
摘要: 給出一個“一筆畫”軌跡，沒有線段重疊。求這個軌跡將平面分成了幾部分。
閱讀全文
posted @
2013-05-06 14:07 西月弦 閱讀(312) |
評論 (0) 編輯
uva 12583 可持久化treap
摘要: 對一個字符串S(初始為空)，有Q次操作(Q<=50,000)，操作分三種：
1. 在某個位置p后面插入一個長度不大于100的字符串。
2. 刪除一段字符[l,r]
3. 輸出在第k次操作時，字符串(S_l ... S_r) 插入的字符不超過1,000,000個。
閱讀全文
posted @
2013-03-19 22:15 西月弦 閱讀(1578) |
評論 (1) 編輯
動態規劃求解背包類問題(更新中...)
摘要: 我理解的背包類問題，大概有兩類：
(1) 在N組物品中，挑選出M個，使得某些性質最優。
(2) 在N組物品中，挑選出M個，求并符合某條件的方案數。
閱讀全文
posted @
2012-12-03 13:40 西月弦 閱讀(446) |
評論 (0) 編輯
codeforces 145C DP+數論
摘要: 給長度為n的數列，(n<1e5)。讓你求選擇沒有相同的lucky number的子序列的方法數 mod 1e9+7。
閱讀全文
posted @
2012-11-30 18:39 西月弦 閱讀(470) |
評論 (0) 編輯
topcoder srm 561 div1
摘要: topcoder srm 561 div1
閱讀全文
posted @
2012-11-21 16:02 西月弦 閱讀(523) |
評論 (3) 編輯
2012亞洲區成都現場賽原創題解
摘要: 2012亞洲區成都現場賽原創題解
閱讀全文
posted @
2012-11-17 23:04 西月弦 閱讀(1138) |
評論 (6) 編輯
codeforces #148 (坑。。)
摘要: codeforces #148 (坑。。)
閱讀全文
posted @
2012-11-05 20:25 西月弦 閱讀(436) |
評論 (0) 編輯
2012天津賽區原創題解
摘要: 題目連接
http://acm.hdu.edu.cn/search.php?field=problem&key=2012%20Asia%20Tianjin%20Regional%20Contest&source=1&searchmode=source
閱讀全文
posted @
2012-10-30 00:07 西月弦 閱讀(1012) |
評論 (8) 編輯
codeforces #147 div2
摘要: codeforces #147 div2
閱讀全文
posted @
2012-10-28 16:01 西月弦 閱讀(423) |
評論 (3) 編輯
poj 3415 SAM
摘要: 詢問兩個長度為100,000的字符串，不小于k的公共子串有多少個。
閱讀全文
posted @
2012-10-25 19:23 西月弦 閱讀(569) |
評論 (0) 編輯
topcoder srm 558 div1
摘要: topcoder srm 558 div1
閱讀全文
posted @
2012-10-24 16:22 西月弦 閱讀(246) |
評論 (0) 編輯
codeforces #146 div1
摘要: codeforces #146 div1
閱讀全文
posted @
2012-10-24 14:13 西月弦 閱讀(557) |
評論 (2) 編輯
topcoder srm 557 div1
摘要: topcoder srm 557 div1
閱讀全文
posted @
2012-10-18 14:00 西月弦 閱讀(464) |
評論 (0) 編輯
codeforces #145
摘要: codeforces #145
閱讀全文
posted @
2012-10-17 13:47 西月弦 閱讀(637) |
評論 (1) 編輯
poj 2949 spfa求正環
摘要: 題目描述：
有N個串，兩個尾首兩個字母相同的串可以連接。求最大均值圈。
閱讀全文
posted @
2012-10-10 19:32 西月弦 閱讀(307) |
評論 (0) 編輯
fzu 2042 數位DP
摘要: 題目描述：
給出五個數（不超過2^63-1），讓你求下面代碼的sum值
for(ll i = a; i <= b; i++)
for(ll j = c; j<= d; j++)
if((i ^ j) > e)
sum += i^j;
閱讀全文
posted @
2012-10-10 14:56 西月弦 閱讀(433) |
評論 (0) 編輯
codeforces #139
摘要: codeforces #139
閱讀全文
posted @
2012-10-08 15:00 西月弦 閱讀(229) |
評論 (0) 編輯
codeforces #140
摘要: codeforces #140
閱讀全文
posted @
2012-10-07 16:10 西月弦 閱讀(552) |
評論 (10) 編輯
codeforces #141
摘要: codeforces #141
閱讀全文
posted @
2012-10-04 00:51 西月弦 閱讀(276) |
評論 (0) 編輯
codeforces #142
摘要: codeforces #142
閱讀全文
posted @
2012-10-03 14:47 西月弦 閱讀(386) |
評論 (0) 編輯
topcoder srm 555 div1 [pratice]
摘要: topcoder srm 555 div1 [pratice]
閱讀全文
posted @
2012-10-02 23:42 西月弦 閱讀(263) |
評論 (0) 編輯
codeforces #137 div2
摘要: codeforces #137 div2
閱讀全文
posted @
2012-09-11 21:39 西月弦 閱讀(384) |
評論 (3) 編輯
hdu 4285 插頭DP
摘要: 求12×12矩陣上的互不嵌套的k個哈密頓回路的方案數。
閱讀全文
posted @
2012-09-10 21:09 西月弦 閱讀(1148) |
評論 (5) 編輯
zoj 1063 廣搜
摘要: 狗狗四十題第六題
閱讀全文
posted @
2012-09-10 11:33 西月弦 閱讀(233) |
評論 (0) 編輯
zoj 1021 遞歸
摘要: 狗狗四十題第一題
閱讀全文
posted @
2012-09-03 19:58 西月弦 閱讀(297) |
評論 (0) 編輯
codeforces #136 div1
摘要: codeforces #136 div1
閱讀全文
posted @
2012-09-01 12:57 西月弦 閱讀(605) |
評論 (7) 編輯
topcoder srm 552 div1 比賽小記
摘要: topcoder srm 552 div1 比賽小記
閱讀全文
posted @
2012-08-17 13:17 西月弦 閱讀(396) |
評論 (1) 編輯
hdu 4127 迭代加深搜索
摘要: 玩flood-it游戲, 一個8*8的帶6種顏色的格子. 每次占領與已占領的聯通塊相鄰的聯通塊, 問最少幾次可以全部占領完. 第一次占領左上角.
閱讀全文
posted @
2012-08-15 20:56 西月弦 閱讀(420) |
評論 (0) 編輯
codeforces #133 div2
摘要: codeforces #133 div2
閱讀全文
posted @
2012-08-15 16:25 西月弦 閱讀(267) |
評論 (0) 編輯
codeforces 213E 多項式哈希+線段樹
摘要: 給兩個長度為200,000的全排列a,b. 尋找整數k的個數,使a的每個數加上k以后,是b的子序列.
閱讀全文
posted @
2012-08-10 22:54 西月弦 閱讀(481) |
評論 (0) 編輯
codeforces #132 div2
摘要: codeforces #132 div2
閱讀全文
posted @
2012-08-10 10:42 西月弦 閱讀(339) |
評論 (0) 編輯
codeforces 213D 計算幾何
摘要: 要求一筆劃畫出N(N<100)個五角形，輸出方案(畫的軌跡)。
閱讀全文
posted @
2012-08-06 22:25 西月弦 閱讀(290) |
評論 (0) 編輯
hdu 4116 計算幾何 + 掃描線
摘要: 在無限平面上有N(N<1,000)個圓。問一條直線最多可以“穿過”幾個圓，相切也算。
閱讀全文
posted @
2012-08-06 14:58 西月弦 閱讀(1246) |
評論 (0) 編輯
codeforces 212D 線段樹 + 棧的應用
摘要: 給1,000,000個數，大小不超過10^9。詢問1,000,000次，長度為k的區間最小值的期望。
閱讀全文
posted @
2012-08-05 19:57 西月弦 閱讀(328) |
評論 (0) 編輯
hdu 3712 計算幾何
摘要: 給一個點光源(x0,y0)，向(x1,y1)處發射射線。p0,p1,p2三個點是三棱鏡，折射率為n。求最后光線與x軸的交點。
閱讀全文
posted @
2012-08-05 14:35 西月弦 閱讀(461) |
評論 (0) 編輯
hdu 4060 二分圖最小點覆蓋
摘要: 由于題目描述過于imba，這里直接給出鏈接吧
http://acm.hdu.edu.cn/showproblem.php?pid=4060
閱讀全文
posted @
2012-08-04 06:14 西月弦 閱讀(370) |
評論 (0) 編輯
hdu 3694 計算幾何
摘要: 求四個點的費馬點與這四個點的距離和。
閱讀全文
posted @
2012-08-03 16:26 西月弦 閱讀(184) |
評論 (0) 編輯
codeforces #131 div1
摘要: codeforces #131 div1
閱讀全文
posted @
2012-08-03 15:36 西月弦 閱讀(273) |
評論 (0) 編輯
hdu 3683 極大極小過程 + 搜索
摘要: 在一個15*15的棋盤上下五子棋。3步之內誰能贏。
閱讀全文
posted @
2012-07-30 21:31 西月弦 閱讀(313) |
評論 (0) 編輯
hdu 4126 最小生成樹 + 樹形DP + 優先級隊列
摘要: 求N<3,000個點的稠密圖的最小生成樹的每條邊的最佳替換邊。
閱讀全文
posted @
2012-07-30 13:46 西月弦 閱讀(410) |
評論 (0) 編輯
hdu 4305 計算幾何 + 高斯消元求行列式 + 逆元
摘要: 平面上有N<300個點。每個兩個點如果距離小于R且之間沒有共線的另一個點，則這兩點之間有一條邊。求這個圖的生成樹的個數mod 10007。
閱讀全文
posted @
2012-07-29 22:29 西月弦 閱讀(437) |
評論 (0) 編輯
codeforces 212C 遞推
摘要: 有一個長度為100的只含A和B的環行串。如果這個串含有AB，那么就變為BA。 給一個串，問有多少種串可以變為這個串。
閱讀全文
posted @
2012-07-29 18:41 西月弦 閱讀(358) |
評論 (0) 編輯
codeforces 204E 后綴數組+線段樹
摘要: 給N個串(N<100,000)，總長不超過100,000。對于每個串，求至少在其他k個串中作為子串出現過的子串個數。
閱讀全文
posted @
2012-07-26 10:20 西月弦 閱讀(760) |
評論 (1) 編輯
codeforces #130 div2
摘要: codeforces #130 div2
閱讀全文
posted @
2012-07-24 17:23 西月弦 閱讀(305) |
評論 (2) 編輯
hdu 4117 AC自動機 + DP
摘要: 有N(N<20,000)個只含有小寫字母的字符串，總長不超過300,000，每個字符串Si有權值Vi。現在讓你刪除一些字符串，滿足對于相鄰的串，前一個串是后一個串的子串。求最大權值和。
閱讀全文
posted @
2012-07-23 12:52 西月弦 閱讀(1349) |
評論 (2) 編輯
codeforces 212E 樹形DP + 背包
摘要: 題目描述：
一棵N(N<5,000)個節點的樹，染兩種顏色，不同顏色不能相鄰且要給盡可能多的節點染色。求顏色A和顏色B可能的染色節點個數。
閱讀全文
posted @
2012-07-21 22:47 西月弦 閱讀(287) |
評論 (0) 編輯
codeforces 204D 動態規劃
摘要: 有一個長度為n(n<1,000,000)的字符串A。有三種字符，'B','W','X'。現在讓你將所有的X要么變成B，要么變成W，構造字符串，使得其存在a<=b
閱讀全文
posted @
2012-07-21 19:13 西月弦 閱讀(337) |
評論 (0) 編輯
codeforces 200A 并查集
摘要: 給一個大小為n*m(n,m < 2000)的棋盤，有k(K<100,000)次操作。每次在位置（x,y）加入一個點，如果x,y已經有點了，那么加入的點需要滿足：
1. 與x,y的曼哈頓距離最近。
2. 如果滿足條件1的點有多個，那么要求x最小。
3. 如果滿足條件2的點有多個，那么要求y最小。
閱讀全文
posted @
2012-07-21 15:02 西月弦 閱讀(319) |
評論 (0) 編輯
hdu 4008 樹形DP + LCA
摘要: 題目描述：
給一顆結點數為(100,000)的樹，最多詢問100,000次。每次詢問對兩個結點X,Y，以X為根，Y的最小標號的孩子，Y的最小標號的后代。
閱讀全文
posted @
2012-07-17 10:53 西月弦 閱讀(497) |
評論 (0) 編輯
codeforces #127 div1
摘要: codeforces #127 div1
閱讀全文
posted @
2012-06-30 02:49 西月弦 閱讀(541) |
評論 (0) 編輯
hdu 4087 仿射幾何 + 矩陣乘法
摘要: 定義一種變換向量的語言，其語法有這么幾種：
1. translate tx ty tz 功能：(x,y,z) = (x+tx,y+ty,z+tz)
2. scale a b c 功能：(x,y,z) = (ax,by,cz)
3. rotate tx ty tz angle 功能：讓x,y,z以tx,ty,tz為軸逆時針旋轉angle。
4. rotate k .... end 功能： 重復執行...k次
給若干個向量，輸出對應的變換后的向量。
閱讀全文
posted @
2012-06-24 16:01 西月弦 閱讀(416) |
評論 (1) 編輯
codeforces 198C 二分答案 + 計算幾何
摘要: 有個星球起始位置是（xp,yp），繞原點以速度Vp做勻速圓周運動。不明物體起始位置（x,y），速度為V(V>Vp)。這個物體可以隨意移動，但是任何時刻與原點的距離不能小于r。請問這個物體想要與星球位置重合的最少時間是多少？
閱讀全文
posted @
2012-06-23 19:26 西月弦 閱讀(491) |
評論 (0) 編輯
hdu 3727 主席樹+ 線段樹
摘要: 對一個序列進行維護，要求支持四種操作：
1. 在結尾加入一個數。
2. 詢問區間第K大的數
3. 詢問大小為X的數在序列中的排名
4. 詢問第K大的數
閱讀全文
posted @
2012-06-21 15:47 西月弦 閱讀(1125) |
評論 (4) 編輯
bzoj 2653 二分枚舉 + 可持久化線段樹
摘要: 給長度為20000的序列。求左端點在[a,b]和右端點在[c,d]中所有的子序列，最大的中位數。
閱讀全文
posted @
2012-06-20 16:44 西月弦 閱讀(1240) |
評論 (5) 編輯
hdu 1828 線段樹求矩形周長并
摘要: 給N(N<5000)個矩形，求周長并。
閱讀全文
posted @
2012-06-04 20:54 西月弦 閱讀(457) |
評論 (0) 編輯
2012 黑龍江省賽簡要題解
摘要: 2012黑龍江省賽簡要題解(不斷更新)
閱讀全文
posted @
2012-05-30 10:33 西月弦 閱讀(331) |
評論 (0) 編輯
poj 2831 次小生成樹 or 樹鏈剖分
摘要: 給一個點數為N(N<1,000)的圖,Q次詢問. 每次詢問如果第i條邊的值變為v, 這條邊是否可能會在最小生成樹中.
閱讀全文
posted @
2012-05-20 15:22 西月弦 閱讀(503) |
評論 (0) 編輯
bzoj 2243 樹鏈剖分+線段樹
摘要: 在一顆點數為N<100,000的樹上，每個點有一個顏色。請你實現兩種操作 1. 給一段路徑u->v染色 2. 詢問路徑u->v上有多少種顏色
閱讀全文
posted @
2012-05-16 17:10 西月弦 閱讀(862) |
評論 (1) 編輯
spoj 375 樹鏈剖分+LCA+RMQ(zkw線段樹)
摘要: 在一個點數為N(N<10,000)的帶權樹上，支持兩個操作：1. 改變一個邊權 2. 詢問u和v之間的路徑上的最大邊權
閱讀全文
posted @
2012-05-14 22:17 西月弦 閱讀(828) |
評論 (2) 編輯
poj 3580 splay(重口味)
摘要: 給一個長度為N(N<10,000)的數列，要求支持6種操作： 1. 將區間[l,r]同時加一個數 2. 將區間[l,r]翻轉 3.將區間[l,r]旋轉若干次 4. 插入一個數 5. 刪除一個數 6.求[l,r]的最小值
閱讀全文
posted @
2012-05-12 23:48 西月弦 閱讀(609) |
評論 (0) 編輯
hdu 1890 splay + 懶惰標記
摘要: 給一個長度為N(N<10,000)的數列，每次選取值最小的元素并翻轉前面的數列，然后刪除這個元素。請在每次操作之前輸出這個最小元素的位置。
閱讀全文
posted @
2012-05-10 20:54 西月弦 閱讀(1159) |
評論 (0) 編輯
hdu 4052 線段樹+掃描線
摘要: 10^7 * 10^7 的平面上有N(N<50,000)個不相交的矩形。要在這個平面上放置一個長度為M(M<1,000)的線段，有多少種方法
閱讀全文
posted @
2012-05-09 22:20 西月弦 閱讀(531) |
評論 (0) 編輯
poj 3225 線段樹(zkw版)+ 懶惰標記
摘要: 定義區間的交，并，差操作。假設當前坐標軸區間集合為S(開始為空)，給大量的詢問，格式為 命令+區間T，命令'I'代表S = S交T，'U'代表并，D和C代表S=S-T和S=T-S，S代表S=S-T并T-S。輸出最后的區間集合S。
閱讀全文
posted @
2012-05-07 20:21 西月弦 閱讀(1640) |
評論 (0) 編輯
hdu 3605 二分圖的多重匹配(匈牙利算法)
摘要: 有N(N<100,000)個人要去M(M<10)個星球，每個人只可以去一些星球，一個星球最多容納Ki個人。請問是否所有人都可以選擇自己的星球...
閱讀全文
posted @
2012-05-06 14:20 西月弦 閱讀(1539) |
評論 (0) 編輯
poj 1182 并查集
摘要: 有三個物種 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 給出N(N<50000)個生物，給出X(X<100000)個定論，請問X個定論中有多少是謊話？
閱讀全文
posted @
2012-05-06 02:28 西月弦 閱讀(393) |
評論 (7) 編輯
hdu 3603 二分+RMQ
摘要: 給一個長度不超過1,000,000的數列S。詢問Q(Q<100,000)次，在區間[l,r]里，查詢最長的元素互不相同的字串的長度。
閱讀全文
posted @
2012-05-04 22:59 西月弦 閱讀(240) |
評論 (0) 編輯
poj 1061 求模線性方程的最小整數解
摘要: 在一個長度為L的環上的有兩點x,y。點A的速度是m，點B的速度是n。請問二者相遇的最小整數時間。保證m,n,x,y,l都是int型正整數。
閱讀全文
posted @
2012-05-04 11:20 西月弦 閱讀(452) |
評論 (0) 編輯
poj 2528 線段樹+離散化
摘要: N(N<10000)多線段[l,r](1<=l<=r<=1,000,000,000)相互覆蓋，每個線段顏色不同，請問最后有多少種顏色?
閱讀全文
posted @
2012-05-03 19:21 西月弦 閱讀(541) |
評論 (0) 編輯
hdu 3068 Manacher算法
摘要: 求一個字符串的最長回文串。串長度小于110,000。
閱讀全文
posted @
2012-05-02 21:26 西月弦 閱讀(519) |
評論 (0) 編輯
poj 1741 樹形DP+分治+排序+容斥原理
摘要: 給你一個N(N<10000)個點的有權樹，請問距離不超過K(K<1,000,000,000)的點對有多少個?
閱讀全文
posted @
2012-05-02 16:58 西月弦 閱讀(463) |
評論 (0) 編輯
bzoj 1503 平衡樹(splay)
摘要: 用一個數據結構來統計員工，有四種操作 1. 加入一個初始工資為A的員工 2. 將所有人工資提高一個數 3. 將所有人工資降低一個數 4. 詢問第K多工資的員工是誰。 其間一點某人的工資低于工資下限，就會立刻離開公司...
閱讀全文
posted @
2012-05-01 19:52 西月弦 閱讀(1673) |
評論 (1) 編輯
hdu 4056 線段覆蓋+并查集優化
摘要: 在一個N*M(N<=200,M<=50000)像素的畫板上畫Q(Q<=50000)個圖形，有矩形，圓形，倒等腰三角形，菱形四種，每個圖形有九種顏色可選擇。對于一個像素，后畫的顏色會覆蓋前面的顏色，請求出最后每種顏色的像素有多少個？
閱讀全文
posted @
2012-04-30 17:38 西月弦 閱讀(492) |
評論 (0) 編輯
codeforces 11D 基于路徑的動態規劃+bitmask
摘要: 請問在點數為V(V<20)的無向圖中，長度不小于3的簡單回路有多少個？(保證結果可以用long long表示， 且圖中無自環或者重邊)
閱讀全文
posted @
2012-04-29 22:14 西月弦 閱讀(891) |
評論 (0) 編輯
hdu 3980 組合博弈+動態規劃+SG函數
摘要: 給一個長度為 N<1000 的環。A和B兩個人每次在這個鏈上選一段長度為 M<1000 的未染色區間進行染色。直到某人不能進行此操作時判此人負。假設兩人都足夠聰明，請你判斷誰會取得勝利？
閱讀全文
posted @
2012-04-28 23:14 西月弦 閱讀(442) |
評論 (0) 編輯
hdu 4200 高斯消元法 + 枚舉
摘要: N(N<100)個帶開關的燈泡排成一行，每個燈泡的開關可以轉換自己，左邊連續D個和右邊連續D個燈泡的開關狀態。現在給你每個燈泡的初始狀態{Ai}，請問最少開關多少次能把所有的燈熄滅？
閱讀全文
posted @
2012-04-27 18:26 西月弦 閱讀(608) |
評論 (0) 編輯
hdu 4123 樹形動態規劃+二分+單調隊列
摘要: 給出一個N個點的帶權樹(N <= 50000)。每個點到任意葉子節點的最長距離記為Di。詢問M < 300次，對每次詢問，找到長度最大的區間[l,r]，使得Di(l<=i<=r)的最大值和最小值的差不超過Q。
閱讀全文
posted @
2012-04-26 16:42 西月弦 閱讀(452) |
評論 (0) 編輯
zoj 3541 基于區間的動態規劃
摘要: N個按鈕在一條直線上排列，給出每個按鈕的坐標(Xi,0)。每個按鈕按下之后在Ti秒之后馬上彈起，你一開始在最左端的按鈕上，每移動1個單位長度需要1秒鐘。
請問你能否在某一時刻使所有按鈕都是按下的。如果可以輸出任一方案。
閱讀全文
posted @
2012-04-25 12:01 西月弦 閱讀(925) |
評論 (0) 編輯
hdu 4114 動態規劃+bitmask+最短路
摘要: 給一個點數為N(N<50)的帶權無向圖。其中有K個景點，參觀每個景點有一個代價 Ti。有一些地方可以獲得一些景點的票，如果持票參觀景點i則代價為 FTi。 保證K<=8，FTi <= Ti。 請問從景點1出發,參觀全部的景點，再回到景點1的最小代價是多少。路的權也計算在代價中。
閱讀全文
posted @
2012-04-24 20:11 西月弦 閱讀(1813) |
評論 (0) 編輯
hdu 2829 動態規劃+斜率優化
摘要: 給你一個序列A，請你把序列A分成連續K個子段，每個子段的代價是 sum(A[i]*A[j]) 其中 i < j。請問如何分組使代價最小。
數據范圍|A|,K <100
閱讀全文
posted @
2012-04-24 14:51 西月弦 閱讀(940) |
評論 (3) 編輯