1.gcd（最大公因数）
int gcd(int a,int b) {
if (b == 0)return a;
else return gcd(b, a%b);
}
2.判断素数（不是素数筛）
bool prime(ll it) {
if (it < 2)return false;
for (ll i = 2; i*i <= it; i++)
if (it%i == 0)return false;
return true;
}
3.素数筛
（1）埃氏筛
void Eratosthenes(int it) {
int cnt = 0, int prime[10000], f[10000];
for (int i = 2; i*i <= it; i++)
if (!f[i])for (int j = i * 2; j <= it; j += i)f[j] = 1;
for (int i = 2; i <= it; i++)
if (!f[i])prime[cnt++] = i;
}
（2）欧拉筛
void Euler(int n) {
int cnt = 0, prime[100000], f[100000];
for (int i = 2; i <= n; i++) {
if (!f[i]) prime[cnt++] = i;
for (int j = 0; j < cnt; j++) {
if (prime[j] * i > n)break;
f[prime[j] * i] = 1;
if (i%prime[j] == 0)break;
}
}
}
4.高精度（java BigInteger）
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
BigInteger bigInteger = scanner.nextBigInteger();
BigInteger bigInteger2 = scanner.nextBigInteger();
System.out.println(bigInteger.add(bigInteger2));
}
}
5.并查集
int tree[1005];
void union_find(int a,int b) {
if (a == b)return;
else if (a < b)tree[b] = a;
else tree[a] = b;
}
int find_root(int it) {
if (tree[it] == -1)return it;
else return tree[it] = find_root(tree[it]);
}
int main() {
memset(tree, -1, 1000);
union_find(find_root(10), find_root(5));
return 0;
}
6.dijkstra
void dijkstra(int s,int e) {
dis[s] = 0; //起点距离赋值为0
int it = s; //迭代器
while (!f[it]) {
f[it] = 1; //标记it的信息已经用过了
for(int i=0;i<100;i++) //用it的信息更像图像距离
if (dis[it] + graph[it][i] < dis[i]) {
dis[i] = dis[it] + graph[it][i];
pre.clear(); //如果找到更近的点，此前的需要清空
pre[i].push_back(it);
}
else if (dis[it] + graph[it][i] == dis[i]) {
pre[i].push_back(it); //距离一样的点，加入i的前驱集合
}
int minl = INF, next = it; //开始寻找下一个点
for(int i=0;i<100;i++)
if (!f[i] && dis[i] < minl) {
minl = dis[i];
next = i;
}
it = next;
}
}
7.DFS路径回溯
int graph[100][100],f[100];
vector<int>path, ans;
void dfs(int s,int e) {
if (s == e) {
ans = path;
return;
}
for(int i=0;i<100;i++)
if (!f[i]) {
f[i] = 1;
path.push_back(i);
dfs(i, e);
f[i] = 0;
path.pop_back();
}
}
8.Manacher
int Mannncher(char s[],int length) {
int id, mx = 0, len = 1, p[100] = { 0 }; //mx：最大回文串的右边界 id：回文串的中心
string str="\n"; //这里以回车符为填充符号
for (int i = 0; i < length; i++) {
str.push_back(s[i]);
str.push_back('\n');
}
for (int i = 1; i < str.size(); i++) {
if (i < mx)p[i] = min(p[id*2-i],mx-id);
//第一个if为第一类情况，大串套小串，而且对称位置的小串已经算出来了。
else p[i] = 1;
//不然就是初始为1赋值
while (str[i - p[i]] == str[i + p[i]])++p[i];
if (p[id] < p[i]) { //以str[i]为中心向两边拓展
id = i;
mx = p[id] + i;
}
len = max(len,p[i]-1);//更新最大值
}
}
9.后中建树（前中同理）
int poster[100], inorder[100];
struct node {
int v;
node* left, *right;
};
node *tree;
void build(int inl,int inr,int posl,int posr,node* &tree) {
if (inl > inr)return;
int v = poster[posr],it = inl;
for (; it <= inr&&inorder[it] != v; it++);
tree = (node*)malloc(sizeof(node));
tree->v = v;
tree->left = tree->right = NULL;
build(inl,it-1,posl,posl+it-inl-1,tree->left);
build(it + 1, inr, posl + it - inl, posr - 1, tree->right);
}
