链式前向星
#include<string.h>
#define MAX 10000
struct node
{
int to,nex,wei;
}edge[MAX*+];
int head[MAX+],cnt;
void add(int u,int v,int w)//添加一个单向边u->v 权为w
{
edge[cnt].to=v;
edge[cnt].wei=w;
edge[cnt].nex=head[u];
head[u]=cnt++;
}
int main()
{
memset(head,-,sizeof(head));//初始化为-1
cnt=;//初始化 0
}
tarjan
#include<stack>
#include<algorithm>
#include<string.h>
using namespace std;
stack<int>s;
int dfn[],low[],scc[];//dfn[]时间戳 low[]最浅到达的点的时间戳 scc[]属于第几个scc
int index;//时间戳
int sccnum;//强连通的序号&&数量
void tarjan(int t)
{
dfn[t]=low[t]=++index;//记录时间戳
s.push(t);//入栈
for(int i=head[t];~i;i=edge[i].nex)//遍历儿子
{
int v=edge[i].to;//v是儿子
if(!dfn[v])//如果没走过
{
tarjan(v);//向下递归
low[t]=min(low[t],low[v]);//更新为min(当前，儿子)
}
else if(!scc[v])//如果不在栈中
{
low[t]=min(low[t],dfn[v]);
}
}
if(low[t]==dfn[t])//出栈
{
sccnum++;
while(!s.empty())
{
int x=s.top();
scc[x]=sccnum;
s.pop();
if(x==t)//直到刚刚出去的和现在的一样
break;
}
}
}
int main()
{
index=;
sccnum=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(scc,,sizeof(scc));
//初始化
}
LCA
int dep[MAX+],vis[MAX+],fa[MAX+],f[MAX+][];
int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);//x为较深的
for(int i=;i>=;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y)
return x;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][];
}
void dfs(int t,int d)
{
dep[t]=d;
for(int i=head[t];~i;i=edge[i].nex)
{
int v=edge[i].to;
if(vis[v])continue;
vis[v]=;
fa[v]=t;
dfs(v,d+);
}
}
int main()
{
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
memset(fa,,sizeof(fa));
}
GCD&LCM
//最小公倍数 = a*b / 最大公因数
int GCD(int a, int b)
{
return b == ? a : GCD(b, a%b);
}
long long int lcm(long long int a, long long int b)
{
return (a*b / GCD(a, b));
}
快速幂
#define MOD 1000000007
int ppow(int a, int b)//a^b
{
int ans = , base = a;
while (b)
{
if (b & )
{
ans *= base;
ans %= MOD;
}
base *= base;
base %= MOD;
b >>= ;
}
return ans;
}
大数加法
string add_string(string s1, string s2)
{
if (s1 == "" && s2 == "") return "";
if (s1 == "") return s2;
if (s2 == "") return s1;
string ans = s1, minn = s2;
if (s1.length() < s2.length()) {
ans = s2;
minn = s1;
}
int a = ans.length() - , b = minn.length() - ;
for (int i = b; i >= ; --i) {
ans[a--] += minn[i] - ''; // a一直在减 ， 额外还要减个'0'
}
for (int i = ans.length() - ; i > ; --i) {
if (ans[i] > '') {
ans[i] -= ;//注意这个是减10
ans[i - ]++;
}
}
if (ans[] > '') {
ans[] -= ;
ans = '' + ans;
}
return ans;
}
大数阶乘
typedef long long LL;
/*
在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度
tip: 阶乘都是先求之前的(n-1)!来求n!
初始化Init函数很重要，不要落下
*/
int mult(int num[], int len, int n) {
LL tmp = ;
for (LL i = ; i < len; ++i) {
tmp = tmp + num[i] * n; //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）
num[i] = tmp % ; // 保存在对应的数组位置，即去掉进位后的一位数
tmp = tmp / ; // 取整用于再次循环,与n和下一个位置的乘积相加
}
while (tmp) { // 之后的进位处理
num[len++] = tmp % ;
tmp = tmp / ;
}
return len;
}
int calculating(int n,vector<int>&v)
{
const int maxn = ;
int num[maxn], len;
//initialize
len = ;
num[] = ;
//---------
for (int i = ; i <= n; ++i) {
len = mult(num, len, i);
}
for (int i = len - ; i >= ; --i)
{
//printf("%d", num[i]); // 从最高位依次输出,数据比较多采用printf输出
v.push_back(num[i]);
}
return ;
}
int main()
{
int n;
cin >> n;
vector<int>v;
calculating(n,v);
//n的阶乘，输出到v
}
并查集
int sset[ + ];
int find(int a)//x=find(a) 将x放入a的集合
{
if (sset[a] != a)
{
sset[a] = find(sset[a]);
}
return sset[a];
}
void merge(int a, int b)//合并a,b
{
sset[a] = b;
}
最长上升子序列（LIS）
int b[];
int LIS(int a[], int n) {
int len = ; b[] = a[];
for (int i = ; i < n; i++) {
b[a[i] > b[len - ] ? len++ : lower_bound(b, b + len, a[i]) - b] = a[i]; //非降换为>=和upper_bound
}
return len;
}