玖的数学&算法录
0%

发表于 更新于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

算法板子目录

  • 基础算法

基础算法

高精度加法
1
2
3
4
5
6
7
8
9
10
11
12
13
string add(string a, string b) {
    string s;//结果
    int c = 0;//进位  
    for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0 || c > 0; i--, j--)
    {
        if (i >= 0) c += a[i] - '0';
        if (j >= 0) c += b[j] - '0';
        s += (c % 10) + '0';
        c /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}
大数阶乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int a[10000] = { 0 };

int main() {
    int n;
    cin >> n;
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        int carry = 0;//进位
        for (int j = 0; j < 10000; j++) {
            a[j] = a[j] * i + carry;
            carry = a[j] / 10;
            a[j] = a[j] % 10;
        }
    }
    int last;
    for (int i = 10000 - 1; i >= 0; i--) {
        if (a[i] != 0) {
            last = i;
            break;
        }
    }
    for (int i = last; i >= 0; i--) cout << a[i];
    return 0;
}
二分

整数二分步骤：

1.找一个区间[L,R]，使得答案一定在该区间中

2.找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。

3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在那个区间；如果不成立，考虑答案在那个区间；

4.如果更新方式写的是R = Mid， 则不用做任何处理；如果更新方式写的是L = Mid,则需要在计算Mid时加上1。

写法一

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

写法二

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

发表于 更新于
本文字数： 6k 阅读时长 ≈ 5 分钟

简单的介绍一下以下几种数列极限的计算方法：

  • 1.Toeplitz定理
  • 2.Stolz定理
  • 3.Wallis公式
  • 4.Stirling公式
阅读全文 »

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

更新：

删去了其他比较trivial的排序，留下了算法竞赛中用的略微多的排序思维。

删掉了useless的排序方法（希尔等等）。

修正了代码语言，Java语言由于当时第一版所写的错误过多，因而删除，再加上在运行速度上不及C++。

1.快速排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作：

(1) 如果区间长度小于等于1直接退出，否则在区间中选择一个数字x作为比较元素。

(2) 将大于x的数字放右边，小于x的数字放左边，等于x的可左可右，将x放在两组数字中间。

**(3)**此时x的位置确认，对其左右两边的区间分别进行递归即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quicksort(int l,int r) {
	if(l >= r) return;
    std::swap(a[l], a[l + rand() % (r - l + 1)]);
    int x = a[l];
    int i = l,j = r;
    while(i < j) {
		while(i < j && a[i] > x) {
            j--;
            if(i < j) {
			 a[i++] = a[j];
            }
        }
        while(i < j && a[i] < x) {
            i++;
            if(i < j) {
                a[j--] = a[i];
            }
        }
    }
    a[i] = x;
    quicksort(l, i - 1);
    quicksort(i + 1, r);
}

2.归并排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作：

(1) 如果区间长度小于等于1直接退出，否则将区间分为[l,m],[m + 1,r]两个部分，其中 m = (l + r) / 2。

(2) 递归对两个子区间进行归并排序。

(3) 将两个已经排好序的子区间进行合并。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void mergesort(int l,int r) {
	if(l == r) return;
    int m = (l + r) / 2;
    mergesort(l,m);
    mergesort(m + 1, r);
    int p1 = l, p2 = m + 1,tot = 0;
    while(p1 <= m && p2 <= r) {
		if(a[p1] <= a[p2])
            c[++tot] = a[p1++];
         else
            c[++tot] = a[p2++];
    }
    while(p1 <= m)
        c[++tot] = a[p1++];
    while(p2 <= r)
        c[++tot] = a[p2++];
   	for(int i=1;i <= tot; i++) {
        a[i + l - 1] = c[i];
    }
}

3.计数排序

思路

计数排序适合于值域范围校的数字排序

(1) 统计每个数字出现了几次。

(2) 统计完每个元素的出现次数后，求一边前缀和，我们就知道了每个数字在排完序后的序列中出现位置的范围。

(3) 把数字填入对应的位置即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define endl "\n"
int n, m, a[N + 1], c[M + 1], r[N + 1];

inline void countingsort() {
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++) {
		++c[a[i]];	
	}
    for(int i=1;i<=m;i++) 
		for(int j=1;j<=c[i];j++) 
			std::cout << i << " ";
   	std::cout << endl;
    
    for(int i=2;i<=m;i++) {
		c[i] += c[i - 1];
    }
    for(int i=n; i; --i) {
         r[i] = c[a[i]]--;
    }
    for(int i=1;i<=n;i++) {
		std::cout << r[i] << " ";
    }
    std::cout << endl;
}

4.基数排序

思路

将每个待排序的元素拆分成m个关键字，然后从后往前依次对这m个关键字进行排序。

特别的

（基数排序经常被用于进行字符串的排序，比如说后缀数组的核心就是基数排序）。

(1) 我们只要把数字按第 i 个及以后的关键字从小到大的顺序放到数组里，再做一次计数排序就好。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n, m, a[N + 1], sa[N + 1], v[N + 1], r[N + 1], c[10];

inline void countingsort() {
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
        ++c[v[i]];
    for(int i=1;i<=9;i++)
        c[i] += c[i - 1];
    for(int i=n;i;--i)
        r[sa[i]] = c[v[sa[i]]]--;
    for(int i=1;i<=n;i++)
        sa[r[i]] = i;
}

inline void radixsort() {
    for(int i=1;i<=n;i++)
        sa[i] = i;
    int x = i;
    for(int i=1;i<=m;i++,x *= 10) {
        for(int j=i;j<=n;j++)
            v[j] = a[j] / x % 10;
    	countingsort();
    }
}