高精运算:
typedef struct //为方便处理,用结构体
{
int len ;
long num [1024] ;
} HNum ;
//万进制高精加法, 注意输出高位补0, printf ("%04d" …) ;
void HPlus (HNum &a, HNum &b, HNum &c)
{
int i, len = a.len > b.len ? a.len : b.len ;
memset (&c, 0, sizeof (HNum)) ;
for (i = 1 ; i <= len ; i ++)
{
c.num [i] += a.num [i] + b.num [i] ;
if (c.num [i] >= BASE)
{
c.num [i+1] += c.num [i] / BASE ;
c.num [i] %= BASE ;
}
}
c.len = len ;
while (c.num [c.len+1] > 0)
c.len ++ ;
}
//万进制高精乘法
void HMul (HNum &a, HNum &b, HNum &c)
{
int i, j ;
memset (&c, 0, sizeof (HNum)) ;
for (i = 1 ; i <= a.len ; i ++)
for (j = 1 ; j <= b.len ; j ++)
{
c.num [i+j-1] += a.num [i] * b.num [j] ; //注意+号
if (c.num [i+j-1] >= BASE)
{
c.num [i+j] += c.num [i+j-1] / BASE ; //注意+号
c.num [i+j-1] %= BASE ;
}
}
c.len = a.len + b.len - 1 ;
while (c.num [c.len+1] > 0) //
c.len ++ ;
}
//万进制高精减法
void HSub (HNum &a, HNum &b, HNum &c)
{
int i, len = a.len ; //保证a >= b
memset (&c, 0, sizeof (HNum)) ;
for (i = 1 ; i <= len ; i ++)
{
c.num [i] += a.num [i] - b.num [i] ; //注意+号
if (c.num [i] < 0)
{
c.num [i+1] -= 1 ; //注意-号
c.num [i] += BASE ;
}
}
c.len = len ;
while (c.len > 0 && c.num [c.len] == 0)
c.len -- ;
}
//万进制高精减法, 直接就 long long….
--------------------------------------------------------------------------------
//Fibonacci, Fibo [i] = Fibo [i-1] + Fibo [i-2], Fibo [3] = 3 ;
// Catalan数列S[n] = C(2n,n)/(n+1)
long Catalan (long n)
{
long i, x, y ;
x = y = 1 ;
for (i = 2 ; i <= n ; i ++)
x *= i ;
for (i = n ; i <= 2*n ; i ++)
y *= i ;
return y/x/(n + 1) ;
}
//最小公倍数
long lcm (long a, long b)
{
return a*b/gdc (a, b) ;
}
//最大公约数, 辗转相除法
long gdc (long a, long b)
{
return (a%b == 0)? b : gdc (b, a%b) ;
}
------------------------------------------------------------------------------------------------------------
//堆操作
void In (HeapDT dt) //进堆
{
int i ;
list [++ len] = dt ;
i = len ;
while (i > 1) //向上调整
{
if (list [i].w < list [i/2].w)
Swap (i, i/2) ;
else
break ;
i /= 2 ;
}
}
HeapDT Out () //出堆
{
HeapDT ret = list [1] ;
Swap (1, len) ; //NOTE: 最重要的一步, 最后(最大)一个元素与第一个元素交换
len -- ; //堆长度减1
int i, pa = 1 ;
for (i = pa * 2 ; i <= len ; i *= 2) //向下调整
{
if (i < len && list [i+1].w < list [i].w)
i ++ ;
if (list [i].w < list [pa].w)
Swap (pa, i) ;
else
break ;
pa = i ;
}
return ret ;
}
------------------------------------------------------------------------------------------------------------
//二分查找, 注意等号
while (low < high)
{
mid = (low + high) >> 1 ;
if (strcmp (spname, name [mid]) <= 0)
high = mid ;
else
low = mid + 1 ;
}
------------------------------------------------------------------------------------------------------------
//快排
void QSort (int low, int high)
{
int l, r ;
Milkcow p = cow [low] ;
l = low, r = high ;
while (l < r)
{
while (l < r && cow [r].price >= p.price)
r -- ;
cow [l] = cow [r] ;
while (l < r && cow [l].price <= p.price)
l ++ ;
cow [r] = cow [l] ;
}
cow [l] = p ;
if (l-1 > low)
QSort (low, l-1) ;
if (l+1 < high)
QSort (l+1, high) ;
}
--------------------------------------------------------------------------------------------
//优化并查集
int FindSet (int i)
{
if (Parent [i] != i) //状态压缩
Parent [i] = FindSet (Parent [i]) ;
return Parent [i] ;
}
void UnionSet (int a, int b)
{
int i, j ;
i = FindSet (a) ;
j = FindSet (b) ;
if (i != j)
if (Rank [i] > Rank [j]) //启发式合并:让深度较小的树成为深度较大的树的子树
Parent [j] = i ;
else
{
Parent [i] = j ;
if (Rank [i] == Rank [j])
Rank [j] ++ ;
}
}
-------------------------------------------------------------------------------------------
图论:
//MST
double Kruscal ()
{
int i, k = 0 ;
double s = 0 ;
for (i = 0 ; i <= n ; i ++)
Parent [i] = i ;
for (i = 0 ; i < m && k < n-1; i ++) //m为总边数
{
if (FindSet (Edge [i].a) != FindSet (Edge [i].b))
{
s += Edge [i].v ;
if (s > S) //是否超出范围
return 0 ;
UnionSet (Edge [i].a, Edge [i].b) ;
k ++ ; //记录合并的边数
}
}
if (k != n-1)
return 0 ;
