算法板子目录
基础算法
高精度加法
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;
}
|