玖的数学&算法录
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;
}