1 高精运算:
2 typedef struct //为方便处理,用结构体
3 {
4 int len ;
5 long num [1024] ;
6 } HNum ;
7 //万进制高精加法, 注意输出高位补0, printf ("%04d" …) ;
8 void HPlus (HNum &a, HNum &b, HNum &c)
9 {
10 int i, len = a.len > b.len ? a.len : b.len ;
11 memset (&c, 0, sizeof (HNum)) ;
12 for (i = 1 ; i <= len ; i ++)
13 {
14 c.num [i] += a.num [i] + b.num [i] ;
15 if (c.num [i] >= BASE)
16 {
17 c.num [i+1] += c.num [i] / BASE ;
18 c.num [i] %= BASE ;
19 }
20 }
21 c.len = len ;
22 while (c.num [c.len+1] > 0)
23 c.len ++ ;
24 }
25 //万进制高精乘法
26 void HMul (HNum &a, HNum &b, HNum &c)
27 {
28 int i, j ;
29 memset (&c, 0, sizeof (HNum)) ;
30 for (i = 1 ; i <= a.len ; i ++)
31 for (j = 1 ; j <= b.len ; j ++)
32 {
33 c.num [i+j-1] += a.num [i] * b.num [j] ; //注意+号
34 if (c.num [i+j-1] >= BASE)
35 {
36 c.num [i+j] += c.num [i+j-1] / BASE ; //注意+号
37 c.num [i+j-1] %= BASE ;
38 }
39 }
40 c.len = a.len + b.len - 1 ;
41 while (c.num [c.len+1] > 0) //
42 c.len ++ ;
43 }
44 //万进制高精减法
45 void HSub (HNum &a, HNum &b, HNum &c)
46 {
47 int i, len = a.len ; //保证a >= b
48 memset (&c, 0, sizeof (HNum)) ;
49 for (i = 1 ; i <= len ; i ++)
50 {
51 c.num [i] += a.num [i] - b.num [i] ; //注意+号
52 if (c.num [i] < 0)
53 {
54 c.num [i+1] -= 1 ; //注意-号
55 c.num [i] += BASE ;
56 }
57 }
58 c.len = len ;
59 while (c.len > 0 && c.num [c.len] == 0)
60 c.len -- ;
61 }
62 //万进制高精减法, 直接就 long long….
63 --------------------------------------------------------------------------------
64 //Fibonacci, Fibo [i] = Fibo [i-1] + Fibo [i-2], Fibo [3] = 3 ;
65
66 // Catalan数列S[n] = C(2n,n)/(n+1)
67 long Catalan (long n)
68 {
69 long i, x, y ;
70 x = y = 1 ;
71 for (i = 2 ; i <= n ; i ++)
72 x *= i ;
73 for (i = n ; i <= 2*n ; i ++)
74 y *= i ;
75 return y/x/(n + 1) ;
76 }
77 //最小公倍数
78 long lcm (long a, long b)
79 {
80 return a*b/gdc (a, b) ;
81 }
82 //最大公约数, 辗转相除法
83 long gdc (long a, long b)
84 {
85 return (a%b == 0)? b : gdc (b, a%b) ;
86 }
87 ------------------------------------------------------------------------------------------------------------
88 //堆操作
89 void In (HeapDT dt) //进堆
90 {
91 int i ;
92 list [++ len] = dt ;
93 i = len ;
94 while (i > 1) //向上调整
95 {
96 if (list [i].w < list [i/2].w)
97 Swap (i, i/2) ;
98 else
99 break ;
100 i /= 2 ;
101 }
102 }
103 HeapDT Out () //出堆
104 {
105 HeapDT ret = list [1] ;
106 Swap (1, len) ; //NOTE: 最重要的一步, 最后(最大)一个元素与第一个元素交换
107 len -- ; //堆长度减1
108 int i, pa = 1 ;
109 for (i = pa * 2 ; i <= len ; i *= 2) //向下调整
110 {
111 if (i < len && list [i+1].w < list [i].w)
112 i ++ ;
113 if (list [i].w < list [pa].w)
114 Swap (pa, i) ;
115 else
116 break ;
117 pa = i ;
118 }
119 return ret ;
120 }
121 ------------------------------------------------------------------------------------------------------------
122 //二分查找, 注意等号
123 while (low < high)
124 {
125 mid = (low + high) >> 1 ;
126 if (strcmp (spname, name [mid]) <= 0)
127 high = mid ;
128 else
129 low = mid + 1 ;
130 }
131 ------------------------------------------------------------------------------------------------------------
132 //快排
133 void QSort (int low, int high)
134 {
135 int l, r ;
136 Milkcow p = cow [low] ;
137 l = low, r = high ;
138 while (l < r)
139 {
140 while (l < r && cow [r].price >= p.price)
141 r -- ;
142 cow [l] = cow [r] ;
143 while (l < r && cow [l].price <= p.price)
144 l ++ ;
145 cow [r] = cow [l] ;
146 }
147 cow [l] = p ;
148 if (l-1 > low)
149 QSort (low, l-1) ;
150 if (l+1 < high)
151 QSort (l+1, high) ;
152 }
153 --------------------------------------------------------------------------------------------
154 //优化并查集
155 int FindSet (int i)
156 {
157 if (Parent [i] != i) //状态压缩
158 Parent [i] = FindSet (Parent [i]) ;
159 return Parent [i] ;
160 }
161 void UnionSet (int a, int b)
162 {
163 int i, j ;
164 i = FindSet (a) ;
165 j = FindSet (b) ;
166 if (i != j)
167 if (Rank [i] > Rank [j]) //启发式合并:让深度较小的树成为深度较大的树的子树
168 Parent [j] = i ;
169 else
170 {
171 Parent [i] = j ;
172 if (Rank [i] == Rank [j])
173 Rank [j] ++ ;
174 }
175 }
176 -------------------------------------------------------------------------------------------
177 图论:
178 //MST
179 double Kruscal ()
180 {
181 int i, k = 0 ;
182 double s = 0 ;
183 for (i = 0 ; i <= n ; i ++)
184 Parent [i] = i ;
185 for (i = 0 ; i < m && k < n-1; i ++) //m为总边数
186 {
187 if (FindSet (Edge [i].a) != FindSet (Edge [i].b))
188 {
189 s += Edge [i].v ;
190 if (s > S) //是否超出范围
191 return 0 ;
192 UnionSet (Edge [i].a, Edge [i].b) ;
193 k ++ ; //记录合并的边数
194 }
195 }
196 if (k != n-1)
197 return 0 ;
198 return s ;
199 }
200 int Prim (int s)
201 {
202 int mstlen, min, imin, i, j ;
203 int closedge [MAX] = {0} ; //保存与MST集合邻接的边
204
205 mstlen = 0 ;
206 for (i = 0 ; i < N ; i ++)
207 closedge [i] = INFINITE ;
208
209 for (i = 0 ; i < N ; i ++)
210 if (G [s][i] != INFINITE)
211 closedge [i] = G [s][i] ;
212 imin = s ;
213 closedge [imin] = 0 ;
214 for (i = 0 ; i < N ; i ++)
215 {
216 min = INFINITE ;
217 for (j = 0 ; j < N ; j ++) //找与MST集合邻接最小的边
218 if (closedge [j] && closedge [j] < min)
219 {
220 imin = j ;
221 min = closedge [j] ;
222 }
223 mstlen += closedge [imin] ;
224 closedge [imin] = 0 ; //并入MST集合
225 for (j = 0 ; j < N ; j ++) //跟新邻接边
226 if (G [imin][j] != INFINITE && G [imin][j] < closedge [j])
227 closedge [j] = G [imin][j] ;
228 }
229 return mstlen ;
230 }
231 ------------------------------------------------------------------------------------------------------------
232 //最短路径:
233 //Bellman + Queue
234 //note:队列版不能做change的优化
235 //用队列和邻接表改进Bellman_Ford算法=> Spfa算法
236 int Bellman_Ford_Spfa (int s)
237 {
238 int i, n ;
239 //初始化
240 for (i = 0 ; i <= P ; i ++)
241 DIST [i] = INFINITE ;
242 DIST [s] = 0 ;
243
244 CQueue Q ;
245 int p, nextp, tmp ;
246 bool INQ [PMAX] = {0} ; //判断是否已经在队列内
247
248 Q.EnQueue(s) ; //原点入队列
249 while (! Q.IsEmpty ())
250 {
251 p = Q.OutQueue() ;
252 INQ [p] = false ;
253
254 //遍历队列出来这个节点的所有邻接点
255 for (i = 1 ; i <= CONN [p][0] ; i ++)
256 {
257 nextp = CONN [p][i] ;
258 tmp = DIST [nextp] ;
259 Relax (p, nextp , G [p][nextp]) ;
260 if (DIST [nextp] != tmp && ! INQ [nextp])
261 {
262 Q.EnQueue(nextp) ;
263 INQ [nextp] = true ;
264 }
265 }
266 }
267 return ….
268 }
269 //DIJ + 小顶堆
270 int DIJ (int v0)
271 {
272 int i, vmin, min, vnext ;
273 bool PASSED [PMAX] = {false} ;
274
275 for (i = 1 ; i <= P ; i ++)
276 DIST [i] = INFINITE ;
277 HeapDT hdt ;
278 CMinHeap heap ;
279 //源点先进堆
280 hdt.v = v0 ;
281 hdt.w = 0 ;
282 heap.In (hdt) ;
283 DIST [v0] = 0 ;
284 while (! heap.IsEmpty ())
285 {
286 hdt = heap.Out () ; //堆顶出堆,即DIST [v]最小的那个, 栈自动调整
287 vmin = hdt.v ;
288 min = hdt.w ;
289 PASSED [vmin] = true ;
290 for (i = 1 ; i <= CONN [vmin][0] ; i ++) //遍历邻接点
291 {
292 vnext = CONN [vmin][i] ;
293 if (! PASSED [vnext] && min + G [vmin][vnext] < DIST [vnext]) //松弛
294 {
295 DIST [vnext] = min + G [vmin][vnext] ;
296 hdt.v = vnext ;
297 hdt.w = DIST [vnext] ;
298 heap.In (hdt) ; //进队,并向上自动调整
299 }
300 }
301 }
302 return … ;
303 }
304 //Floyed, 传递闭包(a>b, b>c, to a>c)
305 void Floyed ()
306 {
307 int i, j, k ;
308 for (k = 0 ; k < N ; k ++)
309 for (i = 0 ; i < N ; i ++)
310 for (j = 0 ; j < N ; j ++)
311 {
312 if (G [i][j] > G [i][k] + G [k][j])
313 G [i][j] = G [i][k] + G [k][j] ;
314 }
315 }
316 --------------------------------------------------------------------------------------------
317 //欧拉回路, 按节点序号递增删边, 如果没此要求可用邻接表
318 void FindCircuit (int v)
319 {
320 if (! FENCE [v][0])
321 {
322 STACK [++ STACK [0]] = v ; //节点度为, 入栈
323 }
324 else
325 {
326 int i ;
327 //遍历邻接点
328 for (i = 1 ; i <= NMAX && FENCE [v][0] ; i ++)//NOTE: 按节点序号递增删边
329 {
330 if (FENCE [v][i])
331 {
332 //删除遍历到的边
333 FENCE [v][i] -- ;
334 FENCE [i][v] -- ;
335 FENCE [v][0] -- ;
336 FENCE [i][0] -- ;
337 //邻接点再调用欧拉回路搜索
338 FindCircuit (i) ;
339 }
340 }
341 STACK [++ STACK [0]] = v ;
342 }
343 }
344 --------------------------------------------------------------------------------------------
345