数论
快速幂
int quickPower(int a, int b)//是求a的b次方
{
int ans = 1, base = a;//ans为答案，base为a^(2^n)
while(b > 0)//b是一个变化的二进制数，如果还没有用完
{
if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
{
ans *= base;//把ans乘上对应的a^(2^n)
//ans %= p; //如果需要取模
}
base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
//base %= p; //同上，取模运算
b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
}
return ans;
}
高精度
加法
string add(string str1,string str2)//只能是两个正数相加
{
string str;
int len1=str1.length();
int len2=str2.length();
//前面补0，弄成长度相同
if(len1<len2)
{
for(int i=1;i<=len2-len1;i++)
str1="0"+str1;
}
else
{
for(int i=1;i<=len1-len2;i++)
str2="0"+str2;
}
len1=str1.length();
int cf=0;
int temp;
for(int i=len1-1;i>=0;i--)
{
temp=str1[i]-'0'+str2[i]-'0'+cf;
cf=temp/10;
temp%=10;
str=char(temp+'0')+str;
}
if(cf!=0) str=char(cf+'0')+str;
return str;
}
减法
string sub(string str1,string str2)////只能是两个正数相减，而且要大减小
{
string str;
int tmp=str1.length()-str2.length();
int cf=0;
for(int i=str2.length()-1;i>=0;i--)
{
if(str1[tmp+i]<str2[i]+cf)
{
str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
cf=1;
}
else
{
str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
cf=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(str1[i]-cf>='0')
{
str=char(str1[i]-cf)+str;
cf=0;
}
else
{
str=char(str1[i]-cf+10)+str;
cf=1;
}
}
str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
return str;
}
乘法
string mul(string str1,string str2)//只能是两个正数相乘
{
string str;
int len1=str1.length();
int len2=str2.length();
string tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr="";
int temp=str2[i]-'0';
int t=0;
int cf=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(str1[j]-'0')+cf)%10;
cf=(temp*(str1[j]-'0')+cf)/10;
tempstr=char(t+'0')+tempstr;
}
if(cf!=0) tempstr=char(cf+'0')+tempstr;
}
str=add(str,tempstr);
}
str.erase(0,str.find_first_not_of('0'));
return str;
}
除法
//compare比较函数：相等返回0，大于返回1，小于返回-1
int compare(string str1,string str2)
{
if(str1.length()>str2.length()) return 1;
else if(str1.length()<str2.length()) return -1;
else return str1.compare(str2);
}
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
void div(string str1,string str2,string "ient,string &residue)
{
quotient=residue="";//清空
if(str2=="0")//判断除数是否为0
{
quotient=residue="ERROR";
return;
}
if(str1=="0")//判断被除数是否为0
{
quotient=residue="0";
return;
}
int res=compare(str1,str2);
if(res<0)
{
quotient="0";
residue=str1;
return;
}
else if(res==0)
{
quotient="1";
residue="0";
return;
}
else
{
int len1=str1.length();
int len2=str2.length();
string tempstr;
tempstr.append(str1,0,len2-1);
for(int i=len2-1;i<len1;i++)
{
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty())
tempstr="0";
for(char ch='9';ch>='0';ch--)//试商
{
string str,tmp;
str=str+ch;
tmp=mul(str2,str);
if(compare(tmp,tempstr)<=0)//试商成功
{
quotient=quotient+ch;
tempstr=sub(tempstr,tmp);
break;
}
}
}
residue=tempstr;
}
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()) quotient="0";
}
线性筛素数
埃氏筛法 O(nlglgn)
const int MAXN = 1000000；
void get_list()
{
int i, j;
for (i=0; i<MAXN; i++) prime[i] = 1;
prime[0] = prime[1] = 0;
for (i=2; i<MAXN; i++)
{
if (!prime[i]) continue;
for (j=i*2; j<MAXN; j+=i) prime[j] = 0;
}
}
最大公约数(gcd)
int gcd(int a,int b)
{
if(a==0) return bl
return gcd(b%a,a);
}
最小公倍数(lcm)
int lcm(int a,int b)
{
int c = a/gcd(a,b);
return c*b;
}
扩展欧几里德
int exgcd(int a,int b,int &x,int &y){
if (b==0){
x=1,y=0;
return a;
}
int d=gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
数据结构
并查集
int n, m;
int fa[200005];
int find(int x) //寻找祖宗节点
{
if (fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
void add(int x, int y)
{
fa[find(x)] = find(y);//将y的祖宗节点变成x祖宗节点的父节点
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
fa[i] = i; //初始化，使每一个节点的父节点都是自己
}
for (int i = 1; i <= m; i++)
{
int z, x, y;
cin >> z >> x >> y;
if (z == 1)
add(x, y);
if (z == 2)
if (find(x) == find(y))
cout << 'Y' << endl;
else
cout << 'N' << endl;
}
}
树状数组
单点修改
int n,m;
int tree_array[1000010];//树状数组
int lowbit(int x){return x&(-x);}
void update(int point,int num)//在序列第point的位置加num
{
while(point<=n)
{
tree_array[point] += num;
point += lowbit(point);
}
}
int sum(int point)//计算序列中1~point的和
{
int res=0;
while(point > 0)
{
res += tree_array[point];
point -= lowbit(point);
}
return res;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
{
int num;
scanf("%d",&num);
update(i,num);//初始值是0，直接更新即可
}
for(int i = 1;i<=m;i++)
{
int z,x,y;
scanf("%d %d %d",&z,&x,&y);
if(z == 1)
{
update(x,y);
}
if(z == 2)
{
int ans = sum(y)-sum(x-1);//用[1,y]的和减去[1,x-1]的和就是[x,y]的和
printf("%d\n",ans);
}
}
return 0;
}
区间修改
洛谷P3368
差分处理
int n,m;
int a[500005];
int t[2000005];
int lowbit(int x){
return x&(-x);
}
void update(int i,int num)
{
for(;i<=n;i+=lowbit(i))
{
t[i] += num;
}
}
int search(int i)
{
int res = 0;
for(;i;i-=lowbit(i))
{
res += t[i];
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++)
{
scanf("%d",a+i);
update(i,a[i]-a[i-1]);
}
for(int i = 1;i<=m;i++)
{
int type;
scanf("%d",&type);
if(type==1)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
update(l,k);
update(r+1,-k);
}
if(type==2)
{
int x;
scanf("%d",&x);
printf("%d\n",search(x));
}
}
return 0;
}
线段树
long long n,m;
long long a[100010];
struct TREE
{
long long l,r,num,lazy;
}tree[400050];
void build(long long left,long long right,long long index)
{
tree[index].l = left;
tree[index].r = right;
if(left == right)
{
tree[index].num = a[left];
return;
}
long long mid = (tree[index].l+tree[index].r)/2;
build(left,mid,index*2);
build(mid+1,right,index*2+1);
tree[index].num = tree[index*2].num+tree[index*2+1].num;
}
void spread(long long index)
{
if(tree[index].lazy)
{
long long nowlazy = tree[index].lazy;
tree[index*2].num += nowlazy*(tree[index*2].r-tree[index*2].l+1);
tree[index*2+1].num += nowlazy*(tree[index*2+1].r-tree[index*2+1].l+1);
tree[index*2].lazy += nowlazy;
tree[index*2+1].lazy += nowlazy;
tree[index].lazy = 0;
}
}
void add(long long index,long long left,long long right,long long value)
{
if(left<=tree[index].l && right>=tree[index].r)
{
tree[index].num += value*(tree[index].r-tree[index].l+1);
tree[index].lazy += value;
return;
}
spread(index);
long long mid = (tree[index].l+tree[index].r)/2;
if(left <= mid) add(index*2,left,right,value);
if(right > mid) add(index*2+1,left,right,value);
tree[index].num = tree[index*2].num + tree[index*2+1].num;
}
long long search(long long index,long long left,long long right)
{
if((left <= tree[index].l) && (right >= tree[index].r))
{
return tree[index].num;
}
spread(index);
long long mid = (tree[index].l+tree[index].r)/2;
long long res = 0;
if(left <= mid) res += search(index*2,left,right);
if(right > mid) res += search(index*2+1,left,right);
return res;
}
int main()
{
n = read();
m = read();
for(long long i = 1;i<=n;i++)
{
a[i] = read();
}
build(1,n,1);
for(long long i = 1;i<=m;i++)
{
long long type,x,y,k;
type = read();
if(type == 1)
{
x = read();
y = read();
k = read();
add(1,x,y,k);
}
if(type == 2)
{
x = read();
y = read();
long long ans = search(1,x,y);
printf("%lld\n",ans);
}
}
return 0;
}
ST表
int n,m;
ll a[100010];
ll f[100010][21];
int l,r;
void init()
{
for(int i = 1;i<=n;i++)
{
f[i][0] = a[i];
}
for(int i = 1;i<21;i++)
{
for(int j = 1;j+(1<<i)-1<=n;j++)
{
f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
}
int search()
{
int k = log2(r-l+1);//<cmath>头文件不要忘
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%lld",a+i);
init();
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",search());
}
return 0;
}
图论
单源最短路
dijkstra
int n,m,s;
ll d[100010];
int num;
int head[100010];
bool vis[100010];
struct EDGE{
int v,ne;
ll w;
}e[200010];
priority_queue<P,vector<P>,greater<P> >q;
void add(int x,int y,ll z)
{
num++;
e[num].ne = head[x];
e[num].v = y;
e[num].w = z;
head[x] = num;
}
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
void dij()
{
d[1] = 0;
for(int i = 2;i<=n;i++)
{
d[i] = INF;
}
q.push(make_pair(0,1));
while(!q.empty())
{
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x];i;i = e[i].ne)
{
int v = e[i].v;
ll w = e[i].w;
if(d[v]>d[x]+w)
{
d[v] = d[x]+w;
q.push(make_pair(d[v],v));
}
}
}
}
int main()
{
n = read();
m = read();
s = read();
for(int i = 1;i<=m;i++)
{
int x,y;
ll z;
x = read();
y = read();
z = read();
add(x,y,z);
}
dij();
for(int i = 1;i<=n;i++)
{
printf("%lld ",d[i]);
}
return 0;
}
SPFA
int n,m,s;
int num,head[10010];
ll d[10010];
bool v[10010];
queue<int> q;
struct EDGE{
int v,ne,w;
}e[500010];
void add(int x,int y,int z)
{
num++;
e[num].v = y;
e[num].w = z;
e[num].ne = head[x];
head[x] = num;
}
void spfa()
{
for(int i = 1;i<=n;i++)
{
d[i] = INF;
}
d[s] = 0;
v[s] = 1;
q.push(s);
while(!q.empty())
{
int x = q.front();
q.pop();
v[x] = 0;
for(int i = head[x];i;i=e[i].ne)
{
int ver = e[i].v;
int w = e[i].w;
if(d[ver]>d[x]+w)
{
d[ver] = d[x]+w;
if(!v[ver])
{
v[ver] = 1;
q.push(ver);
}
}
}
}
}
int main()
{
n=read();m=read();s=read();
for(int i = 1;i<=m;i++)
{
int x,y,z;
x=read();y=read();z=read();
add(x,y,z);
}
spfa();
for(int i = 1;i<=n;i++)
{
printf("%lld ",d[i]);
}
return 0;
}
多源最短路
floyd
int d[310][310],n,m;
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
cin>>n>>m;
//把d数组初始化为邻接矩阵
memset(d,0x3f,sizeof(d));
for(int i=1;i<-=n;i++) d[i][i] = 0;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
d[x][y] = min(d[x][y],z);
}
floyd();
//d[x][y]就是x到y的最短距离
return 0;
}
最小生成树
kruskal
int n,m;
int fa[5005];
int ans = 0;
struct EDGE{
int x,y,w;
friend bool operator<(EDGE A,EDGE B)
{
return A.w>B.w;
}
};
priority_queue<EDGE> q;
int find(int x)
{
if(fa[x]==x)return x;
return fa[x] = find(fa[x]);
}
void add(int x,int y)
{
fa[find(x)] = find(y);
}
bool kurscal(){
int cnt = 0;
while(!q.empty())
{
int x = q.top().x;
int y = q.top().y;
int w = q.top().w;
q.pop();
if(find(x)!=find(y))
{
ans += w;
add(x,y);
cnt++;
}
}
return cnt==n-1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) fa[i] = i;
for(int i = 1;i<=m;i++)
{
EDGE e;
scanf("%d%d%d",&e.x,&e.y,&e.w);
q.push(e);
}
if(kurscal()){
printf("%d",ans);
}else{
puts("orz");
}
return 0;
}
最近公共祖先(LCA)
int n,m,s;
int next_edge[INF*2],head[INF*2],ver[INF*2],num;
int dep[INF];
int f[INF][21];//f[x][k]表示从x节点走2^k步到达的节点
void add(int x,int y) //邻接表存
{
num++;
next_edge[num] = head[x];//next_edge[num]存与num起点相同的上一条边
head[x] = num; //通过head[x]能找到从x出发的最后一条边
ver[num] = y;//第num条边指向的点
}
void dfs_init(int p,int father)//预处理
{
dep[p] = dep[father]+1;
for(int i = 0;i<=19;i++)
{
f[p][i+1] = f[f[p][i]][i];//向上走2^i+1 <=> 走2^i 再走2^i
}
for(int e = head[p];e;e = next_edge[e])//对以p为起点的边遍历
{
int v = ver[e];
if(v == father) continue;
f[v][0] = p; //v向上跳2^0就是p <= p是v的父节点
dfs_init(v,p);
}
}
int LCA(int x,int y)
{
if(dep[x] < dep[y]) swap(x,y);//保证x深度更大
for(int i = 20;i>=0;i--)//让x跳到与y同层
{
if(dep[f[x][i]] >= dep[y]) x=f[x][i];
if(x == y) return x;//如果y是x的祖先
}
for(int i = 20;i>=0;i--)
{
if(f[x][i] != f[y][i])//f[x][i]和f[y][i]不同才跳
{
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];//x,y是深度最浅且不同的点
}
int main()
{
scanf("%d %d %d",&n,&m,&s);
for(int i = 1;i<=n-1;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs_init(s,0);
for(int i = 1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",LCA(a,b));
}
return 0;
}
基础算法
离散化
const int N=1e5+7;
int t[N],a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],t[i]=a[i];
sort(t+1,t+n+1);
m=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(t+1,t+m+1,a[i])-t;
}
KMP(P.s.懒得开字符串了)
char a1[2000000],a2[2000000];
int kmp[2000000];
int main()
{
scanf("%s%s",a1,a2);
kmp[0]=kmp[1]=0;//前一位，两位失配了，都只可能将第一位作为新的开头
int len1=strlen(a1),len2=strlen(a2);
int k;
k=0;
for(int i=1;i<len2;i++)//自己匹配自己
{
while(k&&a2[i]!=a2[k])k=kmp[k];//找到最长的前后缀重叠长度
kmp[i+1]=a2[i]==a2[k]?++k:0;//不相等的情况，即无前缀能与后缀重叠，直接赋值位0（注意是给下一位，因为匹配的是下一位适失配的情况）
}
k=0;
for(int i=0;i<len1;i++)
{
while(k&&a1[i]!=a2[k])k=kmp[k];//如果不匹配，则将利用kmp数组往回跳
k+=a1[i]==a2[k]?1:0;//如果相等了，则匹配下一位
if(k==len2)printf("%d\n",i-len2+2);//如果已经全部匹配完毕，则输出初始位置
}
for(int i=1;i<=len2;i++)printf("%d ",kmp[i]);//输出f数组
return 0;
}
奇技淫巧
快读
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
对拍
rand.cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("data.in","w",stdout);
srand((int)time(0));
int n;
n=rand()%100+1; // 1<=n<100
printf("%d",n);
fclose(stdout);
return 0;
}
cmp.bat
@echo off
:loop
rand.exe>data.in
01.exe<data.in>01.out
02.exe<data.in>02.out
fc 01.out 02.out
if not errorlevel 1 goto loop
pause
goto loop
常用头文件
#include<iostream>
#include<algorithm>
#include<cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <iterator>
#include <bitset>
