常用函数&&数据
strrve() 将字符前后颠倒
strtol() 将字符串转换成长整型数
strtoul() 将字符串转换成无符号长整型数
strtod() 将字符串转换成浮点数
strchr() 查找某字符在字符串中首次出现的位置
strlwr() 将字符串字符全部变成小写
strupr()将字符串字符全部变成大写
string b=a.substr(a,b) 把string a的第a到b个字符赋给b;
next_permutution(); prev_permutation();
floor()向下取整； ceil(); 向上取整；
构造 n的5次方的矩阵系数
1 5 10 10 5 1
1 4 6 4 1
1 3 3 1
1 2 1
1 1
1
#pragma GCC optimize(2) O2优化
#pragma GCC optimize(3,"Ofast","inline") O3优化
一.图论
1.最短路径
1.1dijkstra
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn];
void dijkstra(int sta,int edd){
for(int i=0;i<n;i++) lowcost[i]=mp[sta][i];
vis[sta]=1; lowcost[sta]=0;
//寻找距离原点最小的点加进集合 （除原点）
for(int i=1;i<n;i++){
int Min=inf;
int v=-1;
for(int j=0;j<n;j++){
if(!vis[j]&&lowcost[j]<Min){
Min=lowcost[j];
v=j;
}
}
//如果又一次更新失败退出此次循环
if(Min==inf) {
break;
}
vis[v]=1;
//用新加进来的点松弛
for(int k=0;k<n;k++){
if(!vis[k]&&lowcost[v]+mp[v][k]<lowcost[k]){
lowcost[k]=lowcost[v]+mp[v][k];
pre[k]=v;
}
}
}
}
int main(){
sf("%d%d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mp[i][j]=inf;
}
mp[i][i]=0;
}
for(int i=0;i<m;i++){
sf("%d%d%d",&x,&y,&z);
mp[x][y]=mp[y][x]=z;
}
dijkstra(0,n-1);
if(lowcost[n-1]==inf ) cout<<"-1"<<endl;
else cout<<lowcost[n-1]<<endl;
//假设打印起点是0，终点是n-1的路径
int sta=0,ed=n-1;
pre[sta]=-1;
vector<int> ve;
vector<int>::iterator ite;
while(pre[ed]!=-1){
ve.push_back(ed);
ed=pre[ed];
}
reverse(ve.begin(),ve.end());
cout<<sta<<" ";
for(ite=ve.begin();ite!=ve.end();++ite){
cout<<*ite;
if(ite!=ve.end()) cout<<" ";
else cout<<endl;
}
return 0;
}
1.2.floyed
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn],flag=false;
//k是中间结点,i是起点,j是终点
void floyed(int mp[][maxn]){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
}
int main(){
sf("%d%d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mp[i][j]=inf;
}
mp[i][i]=0;
}
for(int i=0;i<m;i++){
sf("%d%d%d",&x,&y,&z);
mp[x][y]=mp[y][x]=z;
}
floyed(mp);
//可以判断是否存在负环
for(int i=0;i<n;i++){
if(mp[i][i]<0){
flag=true;
}
}
if(flag) cout<<"存在负环"<<endl;
else cout<<"不存在负环"<<endl;
// cout<<mp[0][n-1]<<endl;
return 0;
}
1. 3.优先队列优化（记录路径）
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define pa pair<int,int>
int n,m;
const long long inf=0x3f3f3f3f3f3f3f3f;
int fa[10000];//记录路径
long long d[10000];
//int flag[10000];
struct pr{
int to,cost;
};
struct pe{
int x,y;
bool friend operator< (pe s,pe t)
{
if(s.x !=t.x) return s.x>t.x;
else return s.y>t.y;
}
};
vector<pr>ve[10000];
void bfs()
{
priority_queue<pe>q;
fill(d+1,d+n+1,inf);
// memset(flag,0,sizeof flag);
d[1]=0;
//flag[1]=1;
pe c;
c.x =0,c.y=1;
q.push(c);
while(!q.empty() )
{
c=q.top() ;
q.pop() ;
int v=c.y;
if(v==n)
{
break;
}
if(d[v]<c.x ) continue;
for(int i=0;i<ve[v].size();i++)
{
pr e=ve[v][i];
if((d[e.to]>d[v]+e.cost))
{
d[e.to]=d[v]+e.cost ;
fa[e.to]=v ;
// flag[e.to]=1;
c.x =d[e.to];c.y =e.to;
q.push(c);
}
}
}
}
int main()
{
int x,y,s;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&s);
pr c;
c.cost =s;c.to =y;
ve[x].push_back(c);
}
bfs();
printf("%lld\n",d[n]);
printf("%d",n);
while(fa[n]!=1)
{
printf(" %d",fa[n]);
n=fa[n];
}
printf(" 1\n");
return 0;
}
2.拓扑排序
#include<vector>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int in[10100];// 存入度
vector<int>v[10100];// 存关系 构建图
int main()
{
int m,n;
int x,y;
while(cin>>n>>m)// 根据题目要求可以改动
{
memset(in,0,sizeof(in));// 清空入度
for(int i=1;i<=n;i++) v[i].clear() ;// 清空vector
while(m--)// m组数据
{
cin>>y>>x;
in[y]++;// y的关系大于x，x指向y y的入度+1；
v[x].push_back(y);// 就 y 放在 x后面
}
queue<int>q;// 定义一个队列 最为节点的删除
for(int i=1;i<=n;i++)
{
if(!in[i]) { // 入度为零的节点放入 队列
q.push(i);
}
}
while(!q.empty() )
{
int xx=q.front() ; // 如果队列中一次存了大于 2 个节点
q.pop() ; //说明该图有 2->3 && 2->4 这种情况 有点个点之间没有关系
n--; // 总节点数 -1；
for(int i=0;i<v[xx].size() ;i++) // 遍历这个节点后面的 点
{
int yy=v[xx][i];
in[yy]--; // 删除 x 后 yy 的入度就 -1；
if(!in[yy]) { // 如果此时 yy 入度为零放入队列 遍历他的下一个节点
q.push(yy);
}
}
}
if(n) cout<<"该图有环"<<endl; // 如果总结点数没减为零 说明有环的存在
}
return 0;
}
3.LCA
3.1倍增LCA
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define pa pair<int,int>
const int mn=1e5;
int fa[mn][60];//记录2的j次方个节点是谁
int depth[mn];//记录深度
int bit[mn];//作为2进制
int in[mn];//存入度方便找根节点
int dis[mn];
vector<pa>ve[mn];//存图；
void dfs(int x,int y,int s)
{
depth[x]=depth[y]+1;//x是y的儿子 所以深度加一
dis[x]=dis[y]+s;
fa[x][0]=y;
for(int i=1;i<=29;i++) fa[x][i]=fa[fa[x][i-1]][i-1];//这个节点的的第2的j次方等于2的j-1次方的那个值得2的j-1次方；
for(int i=0;i<ve[x].size() ;i++) // 建议画个图理解一下
{
//pa xx=ve[x][i];
int X=ve[x][i].first;
int Y=ve[x][i].second;
if(x==X) continue;//这里用的双向存图所以一旦xx=其父节点
//depth[xx]=depth[y]+1;就可以不管了
dfs(X,x,Y);//继续搜索
}
}
int lca(int x,int y)
{
if(depth[y]>depth[x])//让x比y深
{
swap(x,y);
}
int dif=depth[x]-depth[y];//取差值方便以后进行调深度
for(int i=29;i>=0;i--)
{
if(dif>=bit[i])//调到同一深度
{
x=fa[x][i];
dif-=bit[i];
}
}
//这个也是调到同一深度
if(x==y) return x;//如果现在节点已经相同那么就输出就行了
for(int i=29;i>=0;i--)
{//从大到小慢慢遍历合适的节点；
if(depth[x]>=bit[i]&&fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main()
{
int n,m,t,x,y,d;
bit[0]=1;
for(int i=1;i<=29;i++)
{
bit[i]=bit[i-1]<<1;
}
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
depth[i]=0;
dis[i]=0;
in[i]=0;
ve[i].clear() ;
}
memset(fa,0,sizeof fa);
// printf("%dssssssss\n",bit[8]);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&d);
ve[x].push_back(make_pair(y,d));//因为不确定谁是定点就双向存图；
in[y]++;
}
int s;
for(int i=1;i<=n;i++)
{
if(in[i]==0) {
s=i;
break;
}
}
dfs(s,0,0);
while(m--)
{
scanf("%d%d",&x,&y);
int ss=lca(x,y);
printf("%d\n",dis[x]+dis[y]-2*dis[ss]);
}
}
}
return 0;
}
3.2 tarjan
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
#define in =read()
#define ll long long
const int size = 500000 + 50;
ll n,m,s;
ll site1,site2;
ll head[size],father[size],vis[size],qhead[size],num[size];
struct apoint{
ll x; ll y;
}a[2*size];
struct qpoint{
ll x; ll y; ll z;
}q[2*size];
inline ll read()
{
ll num=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
num=num*10+ch-'0';
ch=getchar();
}
return num*f;
}
ll find(ll x)
{
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
inline void unionn(ll x,ll y)
{
ll xx=find(x),yy=find(y);
father[yy]=xx;
}
inline void add(ll x,ll y)
{
a[++site1].x=head[x];
a[site1].y=y;
head[x]=site1;
}
inline void qadd(ll x,ll y,ll z)
{
q[++site2].x=qhead[x];
q[site2].y=y;
q[site2].z=z;
qhead[x]=site2;
}
inline void tarjan(ll x)
{
vis[x]=1;
int y,z;
for(int i=head[x];i;i=a[i].x){
y=a[i].y;
if(!vis[y]){
tarjan(y); unionn(x,y);
}
}
for(int i=qhead[x];i;i=q[i].x){
y=q[i].y; z=q[i].z;
if(vis[y])num[z]=find(y);
}
}
int main()
{
n in; m in; s in;
int x,y;
for(int i=1;i<n;i++){
x in; y in;
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
x in; y in;
qadd(x,y,i); qadd(y,x,i);
}
tarjan(s);
for(int i=1;i<=m;i++){
printf("%d\n",num[i]);
}
}
4.树的直径
//**************************dfs*********************
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,tot,a,b,ans,pos;
int first[200010],nxt[200010];
struct edge
{
int u,v;
}l[200010];
void build(int f,int t)
{
l[++tot]=(edge){f,t};
nxt[tot]=first[f];
first[f]=tot;
}
void dfs(int k,int fa,int d)
{
if(d>ans)
{
ans=d;
pos=k;
}
for(int i=first[k];i!=-1;i=nxt[i])
{
int x=l[i].v;
if(x==fa)
continue;
dfs(x,k,d+1);
}
}
int main()
{
memset(first,-1,sizeof(first));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
if(a!=0)
{
build(i,a);
build(a,i);
}
if(b!=0)
{
build(i,b);
build(b,i);
}
}
dfs(1,1,0);//第一遍DFS找出树上深度最深的点
ans=0;
dfs(pos,1,0);//第二遍DFS由深度最深的点向上找最长链
printf("%d",ans);
return 0;
}
/////////////////////////////////////bfs************************************
//记录各个节点到其最远的距离
#include<iostream>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> pa;
int n,maxlen,s;
vector<pa>v[100100];
int dp[100100];
int dfs(int x,int y,int l)
{
if(maxlen<=l)
{
maxlen=l;
s=x;
}
pa p;
for(int i=0;i<v[x].size() ;i++)
{
p=v[x][i];
if(p.first ==y) continue;
else
{
dfs(p.first ,x,l+p.second);
dp[p.first]=max(dp[p.first],l+p.second);
}
}
}
int main()
{
while(cin>>n)
{
int x,y;
memset(dp,0,sizeof dp);
for(int i=0;i<=n;i++) v[i].clear() ;
for(int i=2;i<=n;i++)
{
cin>>x>>y;
v[x].push_back(make_pair(i,y));
v[i].push_back(make_pair(x,y));
}
s=0;
maxlen=0;
maxlen=0;
dfs(1,-1,0);
dfs(s,-1,0);
dfs(s,-1,0);
for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
}
return 0;
}
并查集（带权）
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int fa[30500];// 存节点
int a[30500];// 以该节点为父节点的节点一共有几个
int b[30200];// 该节点到其父节点的距离
int find(int x)
{// 整个程序的核心算法 递归用的真是666666
if(fa[x]!=x)
{
int s=fa[x];// 将其上一个节点的值付给s
fa[x]=find(fa[x]);
a[x]+=a[s];//x到其祖先节点的值等于他到他父节点的值加
//上起父节点到其祖先节点的距离
}
return fa[x];
}
void jion(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
fa[yy]=xx;
a[yy]+=b[xx];//因为把yy的父节点接到xx的父节点后面了
b[xx]+=b[yy];//所以yy到最终祖先节点的距离等于他到本来的祖先的距离
} //加上xx到其祖先节点的距离，此时新的祖先节点的子孙
} //数量等于 以前 xx 的子孙加上 yy 的祖孙；
int main()
{
int n,x,y;
char c;
while(~scanf("%d",&n))
{
for(int i=1;i<=30009;i++)
{
a[i]=0;//自己到自己的距离为0；
b[i]=1;//刚开始的时候每个节点都是一个祖先节点包含自己所以为1；
fa[i]=i;//第i个值为自己方便以后找祖先节点
}
while(n--)
{
scanf(" %c",&c);
if(c=='M')
{
scanf("%d%d",&x,&y);
jion(x,y);
}
else {
scanf("%d",&x);
int s=find(x);//查找 x的祖先节点
printf("%d\n",b[s]-a[x]-1);
}// x 下面的节点等于总结点数减去x到祖先节点的个数
}
}
return 0;
}
二，数论
2.1矩阵快速幂
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
long long t;
long long mod=2147493647;
long long n;
long long bb[3];
struct pe{
long long a[8][8];
};
pe mul(pe x,pe y)
{
pe z;memset(z.a,0,sizeof z.a);
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
for(int k=0;k<7;k++)
z.a[i][j]=(x.a[i][k]*y.a[k][j]%mod+z.a[i][j])%mod;
}
}
return z;
}
pe poow(pe x,int b)
{
pe ans;memset(ans.a,0,sizeof ans.a);
for(int i=0;i<7;i++) ans.a[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,x);
x=mul(x,x);
b>>=1;
}
return ans;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>bb[1]>>bb[2];
if(n<=2)
{
cout<<bb[n]%mod<<endl;
continue;
}
pe a,b;//需要自己根据题意构造矩阵
pe x=mul(poow(b,n-2),a);
cout<<x.a[0][0]<<endl;
}
return 0;
}
2.2博弈论
Bash–两人从一堆a个石子里面轮流取石子，每次最多去b个，取到最后一个石子获胜
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b,flag;
scanf("%d%d", &a, &b);
if (a % (b + 1) == 0)flag = 2;
else flag = 1;
if (flag == 1)printf("A\n");
else printf("B\n");
}
}
Nim–两人从n堆石子中任选一堆取石子，不得不取，可以把一堆直接去玩，拿到最后一颗石子得人获胜
int main() {
int n;
int stone, tag=0;
scanf("%d", &n);
while (n--) {
scanf("%d", &stone);
tag ^= stone;
}
// tag为0则为后⼿手赢，否则为先⼿手赢
if (tag == 0)printf("B\n");
else printf("A\n");
}
威佐夫博弈–有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜
int main() {
int n;
int stone, tag=0;
scanf("%d", &n);
while (n--) {
int a, b;
scanf("%d%d", &a,&b);
if (a < b)swap(a, b);
int flag = (a - b)*(sqrt(5) + 1) / 2; //黄金分割线
// 如果flag == b，则为后⼿手赢，否则先⼿手赢（奇异局）
if (flag == b)printf("B\n");
else printf("A\n");
}
}
SG打表
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];
void getSG(int n)
{
int i,j;
memset(sg,0,sizeof(sg));
for(i=1;i<=n;i++)
{
memset(hash,0,sizeof(hash));
for(j=1;f[j]<=i;j++)
hash[sg[i-f[j]]]=1;
for(j=0;j<=n;j++) //求mes{}中未出现的最小的非负整数
{
if(hash[j]==0)
{
sg[i]=j;
break;
}
}
}
}
SG-DFS
int s[110],sg[10010],n;
int SG_dfs(int x)
{
int i;
if(sg[x]!=-1)
return sg[x];
bool vis[110];
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
{
if(x>=s[i])
{
SG_dfs(x-s[i]);
vis[sg[x-s[i]]]=1;
}
}
int e;
for(i=0;;i++)
if(!vis[i])
{
e=i;
break;
}
return sg[x]=e;
}
一般DFS只在打表解决不了的情况下用，首选打表预处理。
2.3中国剩余定理
两两互质
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long aa[15],bb[15];
long long extgcd(long long a, long long b, long long &x, long long &y){
long long d = a;
if(b != 0){
d = extgcd(b, a%b, y, x);
y -= (a / b) * x;
}
else{
x = 1; y = 0;
}
return d;
}
// 注意使用方法， 除以mi 余数是ai, 传参数的时候容易传错， 倒过来再试试
// 求解模线性方程组x = ai (mod mi)
long long China(long long a[], long long m[], int k)
{
long long M = 1;
long long ans = 0;
for(int i = 0; i < k; i++)
M *= m[i];
for(int i=0; i<k; i++){
long long x, y;
long long Mi = M / m[i];
extgcd(Mi, m[i], x, y);
ans = (ans + Mi * x * a[i]) % M;
}
if(ans < 0)
ans += M;
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i = 0; i < n; i++)
scanf("%I64d %I64d",&aa[i],&bb[i]);
printf("%I64d\n",China(bb, aa, n));
}
return 0;
}
不两两互质
long long extgcd(long long a, long long b, long long &x, long long &y){
long long d = a;
if(b != 0){
d = extgcd(b, a%b, y, x);
y -= (a / b) * x;
}
else{
x = 1; y = 0;
}
return d;
}
//求模线性方程组x = bi (mod ni), ni可以不互质, num表示方程的数目
long long China(long long b[], long long n[], int num){
bool flag = false;
long long bb, d, t, k;
long long n1 = n[0], n2;
long long b1 = b[0], b2;
long long x, y;
for(int i = 1; i < num; i++){
n2 = n[i], b2 = b[i];
bb = b2 - b1;
d = extgcd(n1, n2, x, y);
if (bb % d){ //模线性解k1时发现无解
flag = true;
break;
}
k = bb / d * x; //相当于求上面所说的k1【模线性方程】
t = n2 / d;
if (t < 0) t = -t;
k = (k % t + t) % t; //相当于求上面的K`
b1 = b1 + n1*k;
n1 = n1 / d * n2;
}
if (flag)
return -1; //无解返回-1
return ((b1%n1)+n1)%n1; //这是返回的最小非负整数解
//形成的所有解：b1, b1+n1, b1+2n1,..., b1+xni...
/* 下面是求不大于N的解的个数 if (b1 > N) return 0; return (N-b1)/n1+1; */
}
2.4.快速乘&&快速幂
typedef long long ll;
ll q_mul(ll a, ll b, ll mod){
ll ans=0;
while(b){
if(b & 1) ans=(ans+a)%mod;
a=(a<<1)%mod;
b>>=1;
}
return ans;
}
///////////////////////////第二种/////////////////////////////////
inline ll ksc(ll x,ll y,ll mod)
{
return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}
2.5.Miller-Rabin素数测试算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[10]={2,3,5,7,11,13,17,19,23,29};
int Quick_Multiply(int a,int b,int c) //快速积（和快速幂差不多）
{
long long ans=0,res=a;
while(b)
{
if(b&1)
ans=(ans+res)%c;
res=(res+res)%c;
b>>=1;
}
return (int)ans;
}
int Quick_Power(int a,int b,int c) //快速幂，这里就不赘述了
{
int ans=1,res=a;
while(b)
{
if(b&1)
ans=Quick_Multiply(ans,res,c);
res=Quick_Multiply(res,res,c);
b>>=1;
}
return ans;
}
bool Miller_Rabin(int x) //判断素数
{
int i,j,k;
int s=0,t=x-1;
if(x==2) return true; //2是素数
if(x<2||!(x&1)) return false; //如果x是偶数或者是0,1，那它不是素数
while(!(t&1)) //将x分解成(2^s)*t的样子
{
s++;
t>>=1;
}
for(i=0;i<10&&prime[i]<x;++i) //随便选一个素数进行测试
{
int a=prime[i];
int b=Quick_Power(a,t,x); //先算出a^t
for(j=1;j<=s;++j) //然后进行s次平方
{
k=Quick_Multiply(b,b,x); //求b的平方
if(k==1&&b!=1&&b!=x-1) //用二次探测判断
return false;
b=k;
}
if(b!=1) return false; //用费马小定律判断
}
return true; //如果进行多次测试都是对的，那么x就很有可能是素数
}
int main()
{
int x;
scanf("%d",&x);
if(Miller_Rabin(x)) printf("Yes");
else printf("No");
return 0;
}
2.6. 扩展欧几里德
非递归
int exgcd(int m, int n, int &x, int &y) {
if (n == 0) {
x = 1; y = 0;
return m;
}
int a, a1, b, b1, c, d, q, r, t;
a1 = b = 1;
a = b1 = 0;
c = m; d = n;
q = c/d; r = c%d;
while (r) {
c = d;
d = r;
t = a1;
a1 = a;
a = t - q * a;
t = b1;
b1 = b;
b = t - q * b;
q = c/d;
r = c%d;
}
x = a; y = b;
return d;
}
递归
int exgcd(int a, int b, int &x, int &y)
{
if(b == 0)
{//推理1，终止条件
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a%b, x, y);
//先得到更底层的x2,y2,再根据计算好的x2,y2计算x1，y1。
//推理2，递推关系
int t = y;
y = x - (a/b) * y;
x = t;
return r;
}
三，树
树状数组
// hdu1166-区间求和
#include<bits/stdc++.h>
#define maxn 50005
#define lowbit(x) (x & (-x))
using namespace std;
int tree[50005];
int n, t;
void update(int x, int v) {
while(x <= n) {
tree[x] += v;
x += lowbit(x);
}
}
int getsum(int x) {
int ans = 0;
while(x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int getq(int l ,int r) {
int ans = getsum(r) - getsum(l - 1);
return ans;
}
int main() {
int a = 0;
char str[30];
scanf("%d",&t);
while(t--) {
memset(tree, 0, sizeof(tree));
a++;
int k;
scanf("%d",&n);
for(int i =1; i <= n; i++) {
scanf("%d",&k);
update(i, k);
}
printf("Case %d:\n", a);
while(~scanf("%s",str)) {
if(str[0] == 'E') {
break;
}
int i, j;
if(str[0] == 'A') {
scanf("%d%d",&i, &j);
update(i, j);
} else if(str[0] == 'Q') {
scanf("%d%d",&i, &j);
printf("%d\n",getq(i, j));
} else {
scanf("%d%d",&i, &j);
update(i, -j);
}
}
}
return 0;
}
线段树
// 区间最大值
#include<cstdio>
#include<algorithm>
#define maxn 100105
using namespace std;
int ls[maxn*20],rs[maxn*20];
int tot,sum[maxn*20],root[maxn];//tot是总的节点数，sum是记录每个数在某个节点出现的次数,root是每个线段树的根的值；
void build(int l,int r,int &st) //st表示地址
{
st=++tot;
sum[st]=0;
if(l==r)
return;
int temp=(l+r)/2;
build(l,temp,ls[st]);
build(temp+1,r,rs[st]);
}
void update(int last,int k,int l,int r,int &st)
{
st=++tot;
ls[st]=ls[last];
rs[st]=rs[last];
sum[st]=sum[last]+1;
if(l==r)
return;
int temp=(l+r)/2;
if(k<=temp)
update(ls[last],k,l,temp,ls[st]);
else
update(rs[last],k,temp+1,r,rs[st]);
}
int query(int ss,int tt,int k,int l,int r)
{
if(l==r)
return l;
int ans=sum[ls[tt]]-sum[ls[ss]];
int temp=(l+r)/2;
if(k<=ans)
return query(ls[ss],ls[tt],k,l,temp);
else
return query(rs[ss],rs[tt],k-ans,temp+1,r);
}
int a[maxn],b[maxn];
int main()
{
int T;
int n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
tot=0;
sort(b+1,b+n+1);
int t=unique(b+1,b+n+1)-b-1;
build(1,t,root[0]);
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+t+1,a[i])-b;
for(int i=1;i<=n;i++)
{
update(root[i-1],a[i],1,t,root[i]);
}
for(int i=1;i<=m;i++)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
int ans=query(root[l-1],root[r],k,1,t);
printf("%d\n",b[ans]);
}
}
return 0;
}
四，网络流
最大流
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1e9;
int n,m,x,y,z,maxflow,deep[500];//deep深度
struct Edge{
int next,to,dis;
}edge[500];
int num_edge=-1,head[500],cur[500];//cur用于复制head
queue <int> q;
void add_edge(int from,int to,int dis,bool flag)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
if (flag) edge[num_edge].dis=dis;//反图的边权为 0
head[from]=num_edge;
}
//bfs用来分层
bool bfs(int s,int t)
{
memset(deep,0x7f,sizeof(deep));
while (!q.empty()) q.pop();
for (int i=1; i<=n; i++) cur[i]=head[i];
deep[s]=0;
q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=head[now]; i!=-1; i=edge[i].next)
{
if (deep[edge[i].to]>inf && edge[i].dis)//dis在此处用来做标记 是正图还是返图
{
deep[edge[i].to]=deep[now]+1;
q.push(edge[i].to);
}
}
}
if (deep[t]<inf) return true;
else return false;
}
//dfs找增加的流的量
int dfs(int now,int t,int limit)//limit为源点到这个点的路径上的最小边权
{
if (!limit || now==t) return limit;
int flow=0,f;
for (int i=cur[now]; i!=-1; i=edge[i].next)
{
cur[now]=i;
if (deep[edge[i].to]==deep[now]+1 && (f=dfs(edge[i].to,t,min(limit,edge[i].dis))))
{
flow+=f;
limit-=f;
edge[i].dis-=f;
edge[i^1].dis+=f;
if (!limit) break;
}
}
return flow;
}
void Dinic(int s,int t)
{
while (bfs(s,t))
maxflow+=dfs(s,t,inf);
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&m,&n);
for (int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z,1); add_edge(y,x,z,0);
}
Dinic(1,n);
printf("%d",maxflow);
return 0;
}
最小费用流
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100010;
bool vis[maxn];
int n,m,s,t,x,y,z,f,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
struct Edge{
int to,next,flow,dis;//flow流量 dis花费
}edge[maxn];
int head[maxn],num_edge;
queue <int> q;
void add_edge(int from,int to,int flow,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
edge[num_edge].flow=flow;
edge[num_edge].dis=dis;
head[from]=num_edge;
}
bool spfa(int s,int t)
{
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
while (!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for (int i=head[now]; i!=-1; i=edge[i].next)
{
if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边
{
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);//
if (!vis[edge[i].to])
{
vis[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
}
return pre[t]!=-1;
}
void MCMF()
{
while (spfa(s,t))
{
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
while (now!=s)
{//从源点一直回溯到汇点
edge[last[now]].flow-=flow[t];//flow和dis容易搞混
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main()
{
memset(head,-1,sizeof(head)); num_edge=-1;//初始化
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1; i<=m; i++)
{
scanf("%d%d%d%d",&x,&y,&z,&f);
add_edge(x,y,z,f); add_edge(y,x,0,-f);
//反边的流量为0，花费是相反数
}
MCMF();
printf("%d %d",maxflow,mincost);
return 0;
}
五，字符串
KMP
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000005;
char s1[Maxn],s2[Maxn];
int l1,l2,fail[Maxn];
void Fail(){//构造fail数组
for(int i=2,j=0;i<=l2;++i){
while(j&&s2[j+1]!=s2[i])j=fail[j];
if(s2[j+1]==s2[i])++j;
fail[i]=j;
}
}
void Match(){
for(int i=1,j=0;i<=l1;++i){
while(j&&s2[j+1]!=s1[i])j=fail[j];
if(s2[j+1]==s1[i])++j;
if(j==l2){
//找到一个串，自行维护
j=fail[j];
}
}
}
int main(){
scanf("%s%s",s1+1,s2+1);
l1=strlen(s1+1);
l2=strlen(s2+1);
Fail();
Match();
return 0;
}
哈希
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const LL base1=131;
const LL base2=131;
const LL mod1=1e9+7;
const LL mod2=1e9+9;
char ss[10][10010];
struct node{
LL hash1,hash2;
}a[10011];
LL make_hash1(char s[])
{
LL ans=0;
for(int i=0;i<strlen(s);i++)
ans=(ans*base1+(LL)(s[i]))%mod1;
return ans;
}
LL make_hash2(char s[])
{
LL ans=0;
for(int i=0;i<strlen(s);i++)
ans=(ans*base2+(LL)(s[i]))%mod2;
return ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",ss[i]),a[i].hash1=make_hash1(ss[i]),a[i].hash2=make_hash2(ss[i]);
cout<<"***********"<<endl;
for(int i=1;i<=n;i++)
{
cout<<ss[i]<<" "<<a[i].hash1<<" "<<a[i].hash2<<endl;
}
return 0;
}//求子串哈希值hash=((hash[r]−hash[l−1]∗mod^(r−l+1))%mod+mod)%mod
六，外挂
整数
inline int read(){
2 int x=0,f=1;
3 char ch=getchar();
4 while(ch<'0'||ch>'9'){
5 if(ch=='-')
6 f=-1;
7 ch=getchar();
8 }
9 while(ch>='0'&&ch<='9'){
10 x=(x<<1)+(x<<3)+(ch^48);
11 ch=getchar();
12 }
13 return x*f;
14 }
浮点数
inline bool scan_lf( double &num )
{
char in;
double Dec = 0.1;
bool IsN = false;
bool IsD = false;
in = getchar();
if ( in==EOF )
return false;
while ( in!='-'&&in!='.'&&(in<'0'||in>'9') )
in = getchar();
if ( in=='-' )
IsN = true,num = 0;
else if ( in=='.' )
IsD = true,num = 0;
else
num = in-'0';
if ( !IsD )
{
while ( in=getchar(),in>='0'&&in<='9' )
num = num*10+in-'0';
}
if ( in!='.' )
{
if ( IsN )
num = -num;
return true;
}
else
{
while ( in=getchar(),in>='0'&&in<='9' )
num += Dec*(in-'0'),Dec *= 0.1;
}
if ( IsN )
num = -num;
return true;
}
京公网安备 11010502036488号