\({\mathtt{1}}\). gcd（最大公因数）
点击查看代码
ll gcd(ll a,ll b)
{
if(b==0) return a;
return gcd(b, a%b);
}
\({\mathtt{2}}\). 链式前向星
点击查看代码
int head[100005], edgenum;
struct edge{
int next;
int to;
int w;
};
edge edge[MAXN];
void add(int from,int to,int w)
{
edge[++edgenum].next=head[from];
edge[edgenum].to=to;
edge[edgenum].w=w;
head[from]=edgenum;
}
......
for(int i=head[u];i;i=edge[i].next)
{
......
}
\({\mathtt{3}}\). 快速幂
点击查看代码
ll fpow(ll a, ll b)//a的b次方
{
ll ans=1;
while(b)
{
if(b&1)
{
ans*=a;
}
b>>=1;
a*=a;
}
return ans;
}
\({\mathtt{4}}\). LCA
原题：距离咨询
点击查看代码
//两点距离之和为树根到两点各自的距离之和减去它们的2倍的LCA
#include<bits/stdc++.h>
using namespace std;
int n, m, f1, f2, l, k, x, y, ans;
char d;
int edgenum, head[400005], vis[400005], dep[400005], f[400005][20], dis[400005];
struct edge{
int next;
int w;
int to;
}edge[400005];
void add(int from, int to, int w)
{
edge[++edgenum].next=head[from];
edge[edgenum].to=to;
edge[edgenum].w=w;
head[from]=edgenum;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;//更新深度
f[u][0]=fa;//2^0的祖先就是自己的父亲
for(int i=1;i<=18;i++)//最多大概到2^18次方吧
{
f[u][i]=f[f[u][i-1]][i-1];//倍增递推 2^i=2^(i-1)+2^(i-1)
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa)
{
continue;
}
dis[v]=dis[u]+edge[i].w;//dis表示树根到这个点的距离
dfs(v, u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
{
swap(x, y);//统一x更深
}
for(int i=18;i>=0;i--)//调至同一深度
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
}
if(x==y)
{
return x;//如果相等，直接输出
}
for(int i=18;i>=0;i--)//从大往小跳，更能直接跳到离LCA较近的距离
{
if(f[x][i]!=f[y][i])
{
x=f[x][i], y=f[y][i];
}
}
return f[x][0];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>f1>>f2>>l>>d;
add(f1, f2, l);
add(f2, f1, l);
}
dfs(1, 0);
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>x>>y;
ans=dis[x]+dis[y]-2*dis[lca(x, y)];
cout<<ans<<endl;
}
return 0;
}
一道lca练手好题
\({\mathtt{5}}\). cin cout关闭同步流
点击查看代码
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
\({\mathtt{6}}\). \(kmp\)
点击查看代码
void getnxt()
{
int j=0;
for(int i=2,j=0;i<=n;i++)
{
while(j&&s[i]!=s[j+1])
{
j=nxt[j];
}
if(s[i]==s[j+1])
{
j++;
}
nxt[i]=j;
}
}
\({\mathtt{7}}\). 拓扑排序
将一个有向无环图（\(DAG\)）中的所有顶点排成一个线性序列，满足图中任意一对顶点若存在边连接，那么在序列中该顶点总是出现在其前驱之前。
点击查看代码
void topsort()
{
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
in[v]--;
if(!in[v])
{
q.push(v);
}
}
}
}
\({\mathtt{8}}\). 高斯消元
1.高斯消元
点击查看代码
int gauss()
{
int c=1;
for (int i=1;i<=n;i++)
{
int r=c;
for(int k=c;k<=n;k++)
{
if(fabs(a[k][i])>fabs(a[r][i]))
{
r=k;
}
}
if(fabs(a[r][i])<=eps)
{
continue;
}
swap(a[r], a[c]);
for(int k=n+1;k>=i;k--)
{
a[c][k]/=a[c][i];
}
for(int k=c+1;k<=n;k++)
{
if(fabs(a[k][i])>eps)
{
for (int j=n+1;j>=i;j--)
{
a[k][j]-=a[c][j]*a[k][i];
}
}
}
c++;
}
if(c<=n)
{
int cnt=0;
for(int i=c;i<=n;i++)
{
if(fabs(a[i][n+1])>eps)
{
return -1;
}
cnt++;
}
return cnt;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][n+1]-=a[j][n+]*a[i][j];
}
}
return 0;
}
2.约旦消元
点击查看代码
void gauss(int n)
{
for(int i=1;i<=n;i++)
{
int r=i;
for (int k=i;k<=n;k++)
{
if(fabs(a[k][i])>eps)
{
r=k;
break;
}
}
if(r!=i)
{
swap(a[r], a[i]);
}
if (fabs(a[i][i])<eps)
{
return;
}
for(int j=n+1;j>=i;j--)
{
a[i][j]/=a[i][i];
}
for(int k=i+1;k<=n;k++)
{
for(int j=n+1;j>=i;j--)
{
a[k][j]-=a[k][i]*a[i][j];
}
}
}
for(int i=n-1;i>=1;i--)
{
for (int j=i+1;j<=n;j++) {
a[i][n+1]-=a[i][j]*a[j][n+1];
}
}
return;
}
\({\mathtt{9}}\). tarjan方面
\({\mathtt{10}}\). 线性筛
点击查看代码
st[1]=1;
for(int i=2;i<=100000;i++)
{
if(!st[i])
{
p[++k]=i;
}
for(int j=1;j<=k&&p[j]*i<=100000;j++)
{
st[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
\({\mathtt{11}}\). 离散化
点击查看代码
for(int i=1;i<=n;i++)
{
a[i]=p[i];
}
sort(a+1, a+n+1);
m=unique(a+1, a+n+1)-a-1;
for(int i=1;i<=n;i++)
{
p[i]=lower_bound(a+1, a+n+1, p[i])-a;
}
\({\mathtt{12}}\). 并查集
点击查看代码
int find(int x)
{
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
\({\mathtt{13}}\). 线段树&树剖
\({\mathtt{14}}\). 树状数组
一维：
点击查看代码
#define lowbit(x) (x&(-x))
int sum[maxn];
void add(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos)l
}
}
int query(int pos)
{
int res=0;
while(pos>0)
{
res+=sum[pos];
pos-=lowbit(pos);
}
return res;
}
点击查看代码
long long lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=m;j+=lowbit(j))
{
s[i][j]+=k;
}
}
}
long long getsum(int x,int y)
{
long long ans=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ans+=s[i][j];
}
}
return ans;
}
void add(int x,int y,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=m;j+=lowbit(j))
{
c1[i][j]+=k;
c2[i][j]+=x*k;
c3[i][j]+=y*k;
c4[i][j]+=x*y*k;
}
}
}
int getsum(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ans+=(x+1)*(y+1)*c1[i][j]-(y+1)*c2[i][j]-(x+1)*c3[i][j]+c4[i][j];
}
}
return ans;
}
\({\mathtt{15}}\). 数论part
\({\mathtt{16}}\). 快读
自从那次考试TLE挂了5pts，快读就成为了解决TLE的好帮手。。。
点击查看代码
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;
}
\({\mathtt{16}}\). 异或的一些基本运算规则：
点击查看代码
\(a ⊕ a = 0,\)
\(0 ⊕ a = a,\)
\(a ⊕ b = b ⊕ a,\)
\(a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c\)
\({\mathtt{17}}\). dfs序
点击查看代码
int st[maxn], ed[maxn], id[maxn], idx;
void dfs(int u)
{
st[u]=++idx;
id[idx]=u;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(!st[v]) dfs(v);
}
ed[u]=idx;
}
\({\mathtt{18}}\). RMQ
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n, m, a[maxn], dp[maxn][100], Log2[maxn];
void init()
{
for(int i=1;i<=n;i++) dp[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp[i][j]=max(dp[i][j-1], dp[i+(1<<j-1)][j-1]);
}
}
}
int RMQ(int l,int r)
{
int k=Log2[r-l+1];
return max(dp[l][k], dp[r-(1<<k)+1][k]);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)Log2[i]=(1<<Log2[i-1]+1)>i?Log2[i-1]:Log2[i-1]+1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
init();
while(m--)
{
int l, r;
cin>>l>>r;
cout<<RMQ(l, r)<<endl;
}
return 0;
}
\({\mathtt{19}}\). 对拍
点击查看代码
#include <iostream>
#include <cstdio>
#include <windows.h>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
int ok = 0;
int n = 50;
for (int i = 1; i <= n; ++i)
{
system("make.exe > make.txt");
system("std.exe < make.txt > std.txt");
double begin = clock();
system("baoli.exe < make.txt > baoli.txt");
double end = clock();
double t = (end - begin);
if (system("fc std.txt baoli.txt"))
{
printf("测试点#%d Wrong Answer\n", i);
}
else if (t > 1000) //1秒
{
printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
}
else
{
printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
ok++; //AC数量+1
}
}
printf("\n");
double res = 100.0 * ok / n;
printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
Sleep(1000); //休眠1秒，为了节约对拍次数。
}
- 函数前加上
inline。 - cin cout关闭同步流。
- 。。。