高精度加法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1000], b[1000], c[1000];
char s[1000];
int main() {
int i, j, k, m, n;
int alen, blen, clen;
gets(s);
alen = strlen(s);
for (i = alen - 1; i >= 0; i--)
a[alen - i] = s[i] - '0';
gets(s);
blen = strlen(s);
for (i = blen - 1; i >= 0; i--)
b[blen - i] = s[i] - '0';
clen = alen > blen ? alen : blen;
for (i = 1; i <= clen; i++)
c[i] = a[i] + b[i];
for (i = 1; i < clen; i++)
if (c[i] >= 10) {
c[i + 1]++;
c[i] -= 10;
}
for (i = clen; i >= 1; i--)
printf("%d", c[i]);
puts("");
system("pause");
return 0;
}
高精度减法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1000], b[1000], c[1000];
char s[1000];
int main() {
int i, j, k, m, n;
int alen, blen, clen;
gets(s);
alen = strlen(s);
for (i = alen - 1; i >= 0; i--)
a[alen - i] = s[i] - '0';
gets(s);
blen = strlen(s);
for (i = blen - 1; i >= 0; i--)
b[blen - i] = s[i] - '0';
for (i = 1; i <= alen; i++)
c[i] = a[i] - b[i];
for (i = 1; i < alen; i++)
if (c[i] < 0) {
c[i + 1]--;
c[i] += 10;
}
while (c[alen] == 0 && alen != 1)
alen--;
for (i = alen; i >= 1; i--)
printf("%d", c[i]);
puts("");
system("pause");
return 0;
}
高精度乘法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1000], b[1000], c[2000];
char s[1000];
int main() {
int i, j, k, m, n;
int alen, blen, clen;
gets(s);
alen = strlen(s);
for (i = alen - 1; i >= 0; i--)
a[alen - i] = s[i] - '0';
gets(s);
blen = strlen(s);
for (i = blen - 1; i >= 0; i--)
b[blen - i] = s[i] - '0';
for (i = 1; i <= alen; i++)
for (j = 1; j <= blen; j++)
c[i + j - 1] += a[i] * b[j];
for (i = 1; i < alen + blen - 1; i++)
if (c[i] >= 10) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
for (i = alen + blen - 1; i >= 1; i--)
printf("%d", c[i]);
puts("");
system("pause");
return 0;
}
高精度除法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1000], c[2000];
char s[1000], tmp;
int main() {
int i, j, k, m, n;
int alen, clen;
gets(s);
alen = strlen(s);
for (i = 0; i < alen; i++) a[i + 1] = s[i] - '0';
/*tmp=getchar();*/
scanf("%d", &m);
k = a[1]; i = 1;
while (k < m)
{
i++;
k = k * 10 + a[i];
}
clen = 0;
c[++clen] = k / m;
k %= m;
i++;
for (; i <= alen; i++)
{
k = k * 10 + a[i];
c[++clen] = k / m;
k %= m;
}
puts("结果是：");
for (i = 1; i <= clen; i++) printf("%d", c[i]);
if (k > 0) printf("
余数是：%d
", k);
puts("");
system("pause");
return 0;
}
归并排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int a[1000005], r[100005];
inline int read() {
int x = 0, w = 1; char ch = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * w;
}
void msort(int s, int t) {
if (s == t) return;
int m = (s + t) >> 1;
msort(s, m);
msort(m + 1, t);
int i = s, j = m + 1, k = s;
while (i <= m && j <= t)
if (a[i] < a[j]) r[k++] = a[i++];
else r[k++] = a[j++];
while (i <= m) r[k++] = a[i++];
while (j <= t) r[k++] = a[j++];
for (int i = s; i <= t; i++) a[i] = r[i];
}
int main() {
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
msort(1, n);
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
}
快速排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;
int n,a[100005];
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
void qsort(int l,int r){
int i=l,j=r;
int t=(rand()%(r-l+1))+l;
int m=a[t];
do{
while(a[i]<m) i++;
while(a[j]>m) j--;
if(i<=j){
swap(a[i],a[j]);
i++,j--;
}
}while(i<=j);
if(i<r) qsort(i,r);
if(j>l) qsort(l,j);
}
int main(){
srand(time(0));
n=read();
for(int i=1;i<=n;i++) a[i]=read();
qsort(1,n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
堆排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[1000005],tot;
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
inline void up(int num,int max){
int j=num>>1;
while(j){
if(a[j]>a[num]){
swap(a[j],a[num]);
num=j;j=num>>1;
}
else return;
}
}
inline void down(int num,int max){
int j=num<<1;
while(j<=max){
if(a[j]>a[j+1]&&j<max) j++;
if(a[j]<a[num]){
swap(a[j],a[num]);
num=j;j=num<<1;
}
else j=max+1;
}
}
int main(){
int n=read();
for(int i=1;i<=n;i++) {
int x=read();
a[++tot]=x;up(tot,tot);
}
for(int i=tot;i>=2;i--){
swap(a[i],a[1]);
down(1,i-1);
}
for(int i=n;i>=1;i--) printf("%d ",a[i]);
}
最小生成树
prime
using namespace std;
int map[5050][5050];
int n,m,sum;
int dis[5005],vis[5005];
inline int read() {
int w=1,x=0; char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
return x*w;
}
void Prim() {
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++) dis[i]=map[1][i];
vis[1]=1;
int pos;
for(register int i=1; i<=n-1; ++i) {
int minn=0x3f3f3f3f;
for(register int j=1; j<=n; ++j) {
if(!vis[j]&&dis[j]<minn) minn=dis[j],pos=j;
}
vis[pos]=1;sum+=dis[pos];
for(register int j=1; j<=n; ++j) {
if(!vis[j]&&dis[j]>map[pos][j])
dis[j]=min(dis[j],map[pos][j]);
}
}
}
int main() {
n=read();m=read();
for(register int i=1; i<=n; i++)
for(register int j=1; j<=n; j++)
if(i==j) map[i][j]=0;
else map[i][j]=0x3f3f3f3f;
for(register int i=1; i<=m; i++) {
int t1=read(),t2=read(),t3=read();
map[t1][t2]=map[t2][t1]=min(map[t1][t2],t3);
}
Prim();
printf("%d
",sum);
return 0;
}
kruskal
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct arr{
int u,v,c;
}w[200010];
int n,m,ans;
int f[5010];
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
inline int cmp(arr a,arr b){ return a.c<b.c; }
int gf(int x){ return f[x]==x?x:f[x]=gf(f[x]); }
void union1(int u,int v,int c){
int f1=gf(u),f2=gf(v);
if(f1!=f2){
f[f1]=f2;
ans+=c;
}
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) w[i].u=read(),w[i].v=read(),w[i].c=read();
sort(1+w,1+w+m,cmp);
for(int i=1;i<=m;i++)
union1(w[i].u,w[i].v,w[i].c);
printf("%d",ans);
return 0;
}
次小生成树
线段树
（常数稍大版）区间修改，区间查询一段和，区间查询最大值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct arr{
int l,r,tag;ll sum;
}tree[500000];
int n,m,i,u;
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x*w;
}
void build(ll p,ll l,ll r){
tree[p].l=l;tree[p].r=r;
if(l!=r) {
int m=(l+r)>>1;
build(p<<1,l,m);
build((p<<1)+1,m+1,r);
}
}
inline void push_down(ll p){
if(tree[p].tag==0) return ;
tree[p<<1].sum+=tree[p].tag*(tree[p<<1].r-tree[p<<1].l+1);
tree[(p<<1)+1].sum+=tree[p].tag*(tree[(p<<1)+1].r-tree[(p<<1)+1].l+1);
tree[p<<1].tag+=tree[p].tag;
tree[(p<<1)+1].tag+=tree[p].tag;
tree[p].tag=0;
}
void change(ll p,ll l,ll r,ll data){
if(tree[p].l==l&&tree[p].r==r) {
tree[p].sum+=(r-l+1)*data;tree[p].tag+=data; return;
}
push_down(p);
int m=(tree[p].l+tree[p].r)>>1;
if(r<=m) change(p<<1,l,r,data);
else if(l>m) change((p<<1)+1,l,r,data);
else change(p<<1,l,m,data),change((p<<1)+1,m+1,r,data);
tree[p].sum=tree[p<<1].sum+tree[(p<<1)+1].sum;
}
ll getsum(ll p,ll l,ll r){
if(tree[p].l==l&&tree[p].r==r) return tree[p].sum;
push_down(p);
int m=(tree[p].l+tree[p].r)>>1;
if(r<=m) return getsum(p<<1,l,r);
else if(l>m) return getsum((p<<1)+1,l,r);
else return getsum(p<<1,l,m)+getsum((p<<1)+1,m+1,r);
}
int main(){
n=read();m=read();
build(1,1,n);
for(register int i=1;i<=n;i++) { int x=read();change(1,i,i,x); }
for(register int i=1;i<=m;i++){
int u=read();
if(u==1) { int x=read(),y=read(),k=read();change(1,x,y,k); }
if(u==2) { int x=read(),y=read();printf("%lld
",getsum(1,x,y)); }
}
}
树状数组（差分优化）
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int c[500005],BIT[500005];
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x*w;
}
int lowbit(int x){ return x&-x; }
void add(int pos,int k)
{ while(pos<=n){ BIT[pos]+=k; pos+=lowbit(pos); } }
int sum(int pos)
{ int ans=0; while(pos){ ans+=BIT[pos]; pos-=lowbit(pos); } return ans; }
int main(){
n=read();m=read();
for (int i=1;i<=n;i++){ c[i]=read(); add(i,c[i]-c[i-1]); }
for (int i=1;i<=m;i++){
int num,x,y,k;
num=read();x=read();
if(num==1){y=read();k=read();add(x,k);add(y+1,-k);}
if(num==2) printf("%d
",sum(x));
}
}
Splay
Splay（区间翻转版）
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=101000;
int ch[N][2];
int size[N],rev[N],fa[N];
int n,m,rt=0;
int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
void pushup(int x){
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void pushdown(int x){
if (rev[x]){
int &lc=ch[x][0],&rc=ch[x][1];
swap(lc,rc);
rev[lc]^=1;rev[rc]^=1;rev[x]=0;
}
}
void build(int l,int r,int &rt){
if (l>r) return;
int mid=(l+r)>>1;
if (mid<rt)ch[rt][0]=mid;else ch[rt][1]=mid;
fa[mid]=rt;size[mid]=1;
if (l==r)return;
build(l,mid-1,mid);build(mid+1,r,mid);
pushup(mid);
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],d=ch[y][1]==x;
if (y==k)k=x;
else ch[z][ch[z][1]==y]=x;
fa[ch[x][d^1]]=y;fa[y]=x;fa[x]=z;
ch[y][d]=ch[x][d^1];ch[x][d^1]=y;
pushup(x);pushup(y);
}
void splay(int x,int &k){
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if ((ch[z][0]==y)^(ch[y][0]==x))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int select(int &rt,int k){
pushdown(rt);
int sum=size[ch[rt][0]]+1;
if (sum==k)return rt;
if (sum>k)return select(ch[rt][0],k);
else return select(ch[rt][1],k-sum);
}
void rever(int L,int R){
splay(L,rt);splay(R,ch[L][1]);
rev[ch[R][0]]^=1;
}
void print(int rt){
pushdown(rt);
if (ch[rt][0])print(ch[rt][0]);
if (2<=rt && rt<=n+1)printf("%d ",rt-1);
if (ch[rt][1])print(ch[rt][1]);
}
int main(){
n=read(),m=read();
rt=(3+n)>>1;build(1,n+2,rt);
/*将询问区间[l,r]转换成[l+1,r+1],那么我们翻转l-1,r+1时就不需要特判了。*/
for (int i=1;i<=m;i++){
int L=read(),R=read();
L=select(rt,L);R=select(rt,R+2);
rever(L,R);
}
print(rt);
return 0;
}
Splay（常用版）
Struct Tree {
int key, size, fa, son[2];
}
void PushUp(int x);
void Rotate(int x, int p); /*0左旋 1右旋*/
void Splay(int x, int To) /*将x节点插入到To的子节点中*/
int find(int key) /*返回值为key的节点 若无返回0 若有将其转移到根处*/
int prev() /*返回比根值小的最大值 若无返回0 若有将其转移到根处*/
int succ() /*返回比根值大的最小值 若无返回0 若有将其转移到根处*/
void Insert(int key) /*插入key 并且将该节点转移到根处*/
void Delete(int key) /*删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处*/
int GetPth(int p) /*获得第p小的节点 并将其转移到根处*/
int GetRank(int key) /*获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<*/
int cnt=1, rt=0;
struct Tree {
int key, size, fa, son[2];
void set(int _key, int _size, int _fa) {
key=_key;
size=_size;
fa=_fa;
son[0]=son[1]=0;
}
} T[MAXN];
inline void PushUp(int x) {
T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1;
}
inline void Rotate(int x, int p) { /*0左旋 1右旋*/
int y=T[x].fa;
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[1] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
}
void Splay(int x, int To) { /*将x节点插入到To的子节点中*/
while(T[x].fa != To) {
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[0] == x);
else {
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[0] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); /*之字旋*/
else
Rotate(y, p), Rotate(x, p); /*一字旋*/
}
}
if(To == 0) rt=x;
}
int find(int key) { /*返回值为key的节点 若无返回0 若有将其转移到根处*/
int x=rt;
while(x && T[x].key != key)
x=T[x].son[key > T[x].key];
if(x) Splay(x, 0);
return x;
}
int prev() { /*返回比根值小的最大值 若无返回0 若有将其转移到根处*/
int x=T[rt].son[0];
if(!x) return 0;
while(T[x].son[1])
x=T[x].son[1];
Splay(x, 0);
return x;
}
int succ() { /*返回比根值大的最小值 若无返回0 若有将其转移到根处*/
int x=T[rt].son[1];
if(!x) return 0;
while(T[x].son[0])
x=T[x].son[0];
Splay(x, 0);
return x;
}
void Insert(int key) { /*插入key 并且将该节点转移到根处*/
if(!rt)
T[rt = cnt++].set(key, 1, 0);
else {
int x=rt, y=0;
while(x) {
y=x;
x=T[x].son[key > T[x].key];
}
T[x = cnt++].set(key, 1, y);
T[y].son[key > T[y].key]=x;
Splay(x, 0);
}
}
void Delete(int key) { /*删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处*/
int x=find(key);
if(!x) return;
int y=T[x].son[0];
while(T[y].son[1])
y=T[y].son[1];
int z=T[x].son[1];
while(T[z].son[0])
z=T[z].son[0];
if(!y && !z) {
rt=0;
return;
}
if(!y) {
Splay(z, 0);
T[z].son[0]=0;
PushUp(z);
return;
}
if(!z) {
Splay(y, 0);
T[y].son[1]=0;
PushUp(y);
return;
}
Splay(y, 0);
Splay(z, y);
T[z].son[0]=0;
PushUp(z);
PushUp(y);
}
int GetPth(int p) { /*获得第p小的节点 并将其转移到根处*/
if(!rt) return 0;
int x=rt, ret=0;
while(x) {
if(p == T[T[x].son[0]].size+1)
break;
if(p>T[T[x].son[0]].size+1) {
p-=T[T[x].son[0]].size+1;
x=T[x].son[1];
} else
x=T[x].son[0];
}
Splay(x, 0);
return x;
}
int GetRank(int key) { /*获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<*/
if(!rt) return 0;
int x=rt, ret=0, y;
while(x) {
y=x;
if(T[x].key <= key) {
ret+=T[T[x].son[0]].size+1;
x=T[x].son[1];
} else
x=T[x].son[0];
}
Splay(y, 0);
return ret;
}
Splay（完全版）
Struct Tree {
int key, num, size, fa, son[2];
}
void PushUp(int x);
void PushDown(int x);
int Newnode(int key, int fa); /*新建一个节点并返回*/
void Rotate(int x, int p); /*0左旋 1右旋*/
void Splay(int x, int To); /*将x节点移动到To的子节点中*/
int GetPth(int p, int To); /*返回第p小的节点 并移动到To的子节点中*/
int Find(int key); /*返回值为key的节点 若无返回0 若有将其转移到根处*/
int Prev(); /*返回根节点的前驱*/
int Succ(); /*返回根结点的后继*/
void Insert(int key); /*插入key值*/
void Delete(int key); /*删除值为key的节点*/
int GetRank(int key); /*获得值<=key的节点个数*/
void Delete(int l, int r); /*删除值在[l, r]中的节点*/
int cnt, rt;
int Add[MAXN];
struct Tree {
int key, num, size, fa, son[2];
} T[MAXN];
inline void PushUp(int x) {
T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+T[x].num;
}
inline void PushDown(int x) {
if(Add[x]) {
if(T[x].son[0]) {
T[T[x].son[0]].key+=Add[x];
Add[T[x].son[0]]+=Add[x];
}
if(T[x].son[1]) {
T[T[x].son[1]].key+=Add[x];
Add[T[x].son[1]]+=Add[x];
}
Add[x]=0;
}
}
inline int Newnode(int key, int fa) { /*新建一个节点并返回*/
++cnt;
T[cnt].key=key;
T[cnt].num=T[cnt].size=1;
T[cnt].fa=fa;
T[cnt].son[0]=T[cnt].son[1]=0;
return cnt;
}
inline void Rotate(int x, int p) { /*左旋 1右旋*/
int y=T[x].fa;
PushDown(y);
PushDown(x);
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[1] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
}
void Splay(int x, int To) { /*将x节点移动到To的子节点中*/
while(T[x].fa != To) {
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[0] == x);
else {
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[0] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); /*之字旋*/
else
Rotate(y, p), Rotate(x, p); /*一字旋*/
}
}
if(To == 0) rt=x;
}
int GetPth(int p, int To) { /*返回第p小的节点 并移动到To的子节点中*/
if(!rt || p > T[rt].size) return 0;
int x=rt;
while(x) {
PushDown(x);
if(p >= T[T[x].son[0]].size+1 && p <= T[T[x].son[0]].size+T[x].num)
break;
if(p > T[T[x].son[0]].size+T[x].num) {
p-=T[T[x].son[0]].size+T[x].num;
x=T[x].son[1];
} else
x=T[x].son[0];
}
Splay(x, 0);
return x;
}
int Find(int key) { /*返回值为key的节点 若无返回0 若有将其转移到根处*/
if(!rt) return 0;
int x=rt;
while(x) {
PushDown(x);
if(T[x].key == key) break;
x=T[x].son[key > T[x].key];
}
if(x) Splay(x, 0);
return x;
}
int Prev() { /*返回根节点的前驱 非重点*/
if(!rt || !T[rt].son[0]) return 0;
int x=T[rt].son[0];
while(T[x].son[1]) {
PushDown(x);
x=T[x].son[1];
}
Splay(x, 0);
return x;
}
int Succ() { /*返回根结点的后继 非重点*/
if(!rt || !T[rt].son[1]) return 0;
int x=T[rt].son[1];
while(T[x].son[0]) {
PushDown(x);
x=T[x].son[0];
}
Splay(x, 0);
return x;
}
void Insert(int key) { /*插入key值*/
if(!rt)
rt=Newnode(key, 0);
else {
int x=rt, y=0;
while(x) {
PushDown(x);
y=x;
if(T[x].key == key) {
T[x].num++;
T[x].size++;
break;
}
T[x].size++;
x=T[x].son[key > T[x].key];
}
if(!x)
x=T[y].son[key > T[y].key]=Newnode(key, y);
Splay(x, 0);
}
}
void Delete(int key) { /*删除值为key的节点1个*/
int x=Find(key);
if(!x) return;
if(T[x].num>1) {
T[x].num--;
PushUp(x);
return;
}
int y=T[x].son[0];
while(T[y].son[1])
y=T[y].son[1];
int z=T[x].son[1];
while(T[z].son[0])
z=T[z].son[0];
if(!y && !z) {
rt=0;
return;
}
if(!y) {
Splay(z, 0);
T[z].son[0]=0;
PushUp(z);
return;
}
if(!z) {
Splay(y, 0);
T[y].son[1]=0;
PushUp(y);
return;
}
Splay(y, 0);
Splay(z, y);
T[z].son[0]=0;
PushUp(z);
PushUp(y);
}
int GetRank(int key) { /*获得值<=key的节点个数*/
if(!Find(key)) {
Insert(key);
int tmp=T[T[rt].son[0]].size;
Delete(key);
return tmp;
} else
return T[T[rt].son[0]].size+T[rt].num;
}
void Delete(int l, int r) { /*删除值在[l, r]中的所有节点 l!=r*/
if(!Find(l)) Insert(l);
int p=Prev();
if(!Find(r)) Insert(r);
int q=Succ();
if(!p && !q) {
rt=0;
return;
}
if(!p) {
T[rt].son[0]=0;
PushUp(rt);
return;
}
if(!q) {
Splay(p, 0);
T[rt].son[1]=0;
PushUp(rt);
return;
}
Splay(p, q);
T[p].son[1]=0;
PushUp(p);
PushUp(q);
}
树链剖分
树链剖分POJ 模板题
第一个操作：将第i条边的权值变为v。
第二个操作：将点a到点b路径上的边权变为其相反数。
第三个操作：查询点a到点b路径上的边权最大值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ls p<<1
#define rs (p<<1)+1
#define mid (tree[p].l+(tree[p].r-tree[p].l)/2)
using namespace std;
struct Node{
int l,r,p,sum;
}tree[500005];
struct arr{
int nd,nx,co,id;
}edge[100005];/*这个地方既可以用邻接链表储存，也可以用动态数组来存 */
int head[100005],deep[100005],pos[100005],son_cost[100005];
int top[100005],fa[100005],sz[100005],son[100005],road[100005],a[100005];
int t,n,cnt,tot,ans;
int mx[500005],mi[500005],fg[500005];
inline void add(int u,int v,int w,int id){ edge[++cnt].nd=v; edge[cnt].co=w; edge[cnt].id=id;edge[cnt].nx=head[u]; head[u]=cnt; }
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
void dfs1(int u,int father,int depth){/*建立起一棵树，并且查找出重儿子 */
deep[u]=depth;fa[u]=father;sz[u]=1;
for(int i=head[u];i;i=edge[i].nx){
int v=edge[i].nd;
if(v!=father){
road[edge[i].id]=v;
dfs1(v,u,depth+1);
sz[u]+=sz[v];
if(son[u]==-1||sz[son[u]]<sz[v]) {
son[u]=v;
/* son_cost[u]=edge[i].co;*/
}
}/*这一步很重要！！！第二个if是为了记录重儿子是哪一个 */
}
}
void dfs2(int u,int tp,int cost){/*这个操作是将重轻链的最顶端的点求出来 */
top[u]=tp;pos[u]=++tot;a[tot]=cost;
if(son[u]==-1) return;
dfs2(son[u],tp,son_cost[u]);
for(int i=head[u];i;i=edge[i].nx){
int v=edge[i].nd;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v,edge[i].co);
}
}
inline void pushup(int p){ mx[p]=max(mx[ls],mx[rs]); mi[p]=min(mi[ls],mi[rs]); }
inline void push_down(int p){
if(fg[p]){
fg[ls]^=1; fg[rs]^=1;
int tmp=mx[ls]; mx[ls]=-mi[ls]; mi[ls]=-tmp;
tmp=mx[rs]; mx[rs]= -mi[rs]; mi[rs]= -tmp;
fg[p]=0;
}
}
void build(int l,int r,int p){
tree[p].l=l; tree[p].r=r;
if(l==r) {
mx[p]=a[l];
mi[p]=a[l];
return;
}
int midd=(l+r)>>1;
build(l,midd,ls);
build(midd+1,r,rs);
pushup(p);
}
void change(int p,int l,int data){
if (tree[p].l==tree[p].r){
mi[p]=mx[p]=data;
} else {
push_down(p);
if (l<=mid) change(ls,l,data);
else change(rs,l,data);
pushup(p);
}
}
void nega(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r){
fg[p]^=1;
int tmp=mx[p];
mx[p]=-mi[p];
mi[p]=-tmp;
return;
}
push_down(p);
if(l<=mid) nega(ls,l,r);
if(r>mid) nega(rs,l,r);
pushup(p);
}
void NEGATE(int x,int y,int n){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
nega(1,pos[top[x]],pos[x]);
x=fa[top[x]];
}
if(x==y) return;
if(deep[x]>deep[y]) swap(x,y);
nega(1,pos[son[x]],pos[y]);
}
int query(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r) return mx[p];
push_down(p);
int ans = -(1<<30);
if(l<=mid) ans=max(ans,query(ls,l,r));
if(r>mid) ans=max(ans,query(rs,l,r));
pushup(p);
return ans;
}
int QUERY(int x,int y,int n){
if(x==y) return 0;
int ans=-(1<<30);
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,query(1,pos[top[x]],pos[x]));
x=fa[top[x]];
}
if(x==y) return ans;
if(deep[x]>deep[y]) swap(x,y);
ans=max(ans,query(1,pos[son[x]],pos[y]));
return ans;
}
void init(){
tot=cnt=0;
memset(head,0,sizeof(head));
memset(son,-1,sizeof(head));
memset(fg,0,sizeof(fg));
}
int main(){
t=read();
for(int k=1;k<=t;k++){
n=read();init();
for(int i=1;i<=n-1;i++){
int u=read(),v=read(),w=read();
add(u,v,w,i);add(v,u,w,i);
}
dfs1(1,0,0);
dfs2(1,1,0);
build(2,n,1);
char ch[10];
while(~scanf("%s",ch)){
if(*ch=='D') break;
int u=read(),v=read();
if(*ch=='Q')printf("%d
",QUERY(u,v,n));
else if(*ch=='C') change(1,pos[road[u]],v);
else NEGATE(u,v,n);
}
}
}
树链剖分 洛谷模板题 维护点权
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (tree[rt].l+(tree[rt].r-tree[rt].l)/2)
using namespace std;
struct arr{
int l,r,sum,tag;
}tree[3000000];
int w[200000],id[200000],deep[200000],fa[200000],sz[200000];
int top[200000],son[200000],pos[200000];
int n,m,rr,MD,cnt;
vector<int>g[2000000];
template<typename tp>void read(tp & dig){/*读入优化*/
char c=getchar();dig=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
inline int read(){
int x=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x*w;
}
inline void pushup(int rt){tree[rt].sum=tree[ls].sum+tree[rs].sum;}
inline void build(int l,int r,int rt){/*建立一棵线段树 */
tree[rt].l=l,tree[rt].r=r;
if(l==r){tree[rt].sum=w[id[l]];return ;}
int midd=l+(r-l)/2;
build(l,midd,ls),build(midd+1,r,rs);
pushup(rt);
}
inline void pushdown(int rt){/*下传标记 */
if(tree[rt].tag){
tree[ls].tag=(tree[ls].tag+tree[rt].tag)%MD;
tree[rs].tag=(tree[rs].tag+tree[rt].tag)%MD;
tree[ls].sum=(tree[ls].sum+(tree[ls].r-tree[ls].l+1)*tree[rt].tag)%MD;
tree[rs].sum=(tree[rs].sum+(tree[rs].r-tree[rs].l+1)*tree[rt].tag)%MD;
tree[rt].tag=0;
}
}
inline void update(int l,int r,int c,int rt){/*区间、单点修改 */
if(l<=tree[rt].l&&tree[rt].r<=r){ /*线段树的另一种写法，快一些 */
tree[rt].sum=(tree[rt].sum+(c*(tree[rt].r-tree[rt].l+1)%MD))%MD;
tree[rt].tag+=c%MD;
return ;
}
pushdown(rt);
if(l<=mid) update(l,r,c,ls);/*为啥是这样写？ */
if(r>mid) update(l,r,c,rs);
pushup(rt);
}
inline long long query(int l,int r,int rt){/*区间查询 */
if(l<=tree[rt].l&&tree[rt].r<=r) return tree[rt].sum;
pushdown(rt);
int ans=0;
if(l<=mid) ans+=query(l,r,ls),ans%=MD;
if(r>mid) ans+=query(l,r,rs),ans%=MD;
return ans%MD;
}
void dfs1(int x,int fat,int dep){
deep[x]=dep,fa[x]=fat,sz[x]=1;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v!=fat){
dfs1(v,x,dep+1);
sz[x]+=sz[v];
if(son[x]==-1||sz[son[x]]<sz[v]) son[x]=v;
}
}
}
void dfs2(int x,int tp){
top[x]=tp;pos[x]=++cnt;id[pos[x]]=x;
if(son[x]==-1) return;
dfs2(son[x],tp);
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v!=fa[x]&&v!=son[x]) dfs2(v,v);
}
}
long long add(int t1,int t2,int data,int ok){
long long u=t1,v=t2,ans=0;
while(top[u]!=top[v]){
if(deep[top[u]]>deep[top[v]]) swap(u,v);
if(!ok)update(pos[top[v]],pos[v],data,1);
else ans+=query(pos[top[v]],pos[v],1),ans%=MD;
v=fa[top[v]];
}
if(deep[u]>deep[v]) swap(u,v);
if(!ok) update(pos[u],pos[v],data,1);
else ans+=query(pos[u],pos[v],1);
return ans%=MD;
}
int main(){
memset(son,-1,sizeof(son));
n=read();m=read();rr=read();MD=read();
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<=n-1;i++){
int u=read(),v=read(); g[u].push_back(v);g[v].push_back(u);
}
dfs1(rr,-1,1);
dfs2(rr,rr);
build(1,n,1);/*建树*/
for(int i=1;i<=m;i++){
int xx,t1,t2,t3;
cin>>xx;
if(xx==1) t1=read(),t2=read(),t3=read(),add(t1,t2,t3,0);
if(xx==3) t1=read(),t2=read(),update(pos[t1],pos[t1]+sz[t1]-1,t2,1);
if(xx==2) t1=read(),t2=read(),printf("%lld
",add(t1,t2,0,1)%MD);
if(xx==4) t2=read(),printf("%lld
",query(pos[t2],pos[t2]+sz[t2]-1,1)%MD);
}
return 0;
}
树的重心
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int N = 50005;
const int INF = 1<<30;
int head[N],int son[N], cnt,n,ans[N],num,size;
bool vis[N];
struct Edge {
int to;
int next;
};
Edge edge[2*N];
void Init() {
cnt = 0; num = 0;
size = INF;
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
}
void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; }
void dfs(int cur) {
vis[cur] = 1;
son[cur] = 0;
int tmp = 0;
for(int i=head[cur]; ~i; i=edge[i].next) {
int u = edge[i].to;
if(!vis[u]) {
dfs(u);
son[cur] += son[u] + 1;
tmp = max(tmp,son[u] + 1);
}
}
tmp = max(tmp,n-son[cur]-1);
if(tmp < size) {
num = 1;
ans[0] = cur;
size = tmp;
} else if(tmp == size) { ans[num++] = cur; }
}
int main() {
while(~scanf("%d",&n)) {
Init();
for(int i=1; i<=n-1; i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1);
sort(ans,ans+num);
for(int i=0; i<num; i++) printf("%d ",ans[i]);
puts("");
}
return 0;
}
树的直径
1 #include<cstdio> 2 #include<cstring> 3 #define N 4200 4 struct hehe{ 5 int next; 6 int to; 7 }edge[N]; 8 int num_edge,head[N],dis[N],n,a,b,pos; 9 int add_edge(int from,int to){ 10 edge[++num_edge].next=head[from]; 11 edge[num_edge].to=to; 12 head[from]=num_edge; 13 } 14 int dfs(int x){ 15 for(int i=head[x];i;i=edge[i].next) 16 if(!dis[edge[i].to]){ 17 dis[edge[i].to]=dis[x]+1; 18 dfs(edge[i].to); 19 } 20 } 21 int main(){ 22 scanf("%d",&n); 23 for(int i=1;i<n;++i){ 24 scanf("%d%d",&a,&b); 25 add_edge(a,b); 26 add_edge(b,a); 27 } 28 dfs(1); 29 for(int i=pos=1;i<=n;i++) if(dis[i]>dis[pos]) pos=i; 30 memset(dis,0,sizeof(dis)); 31 dfs(pos); 32 for(int i=pos=1;i<=n;i++) if(dis[i]>dis[pos]) pos=i; 33 printf("%d ",dis[pos]); 34 return 0; 35 }
并查集
找爸爸1——递归：
int gf(int x) {
if(x==f[x]) return x;
else return f[x]=gf(f[x]);
}
或者也可以这样
int gf(int x) { return x==f[x]?x:f[x]=gf(f[x]); }
找爸爸2——非递归：
int gf(int x) {
int u=x;
int v;
while(x!=f[x]) x=f[x];
while(f[u]!=x) {
v=f[u];
f[u]=x;
u=v;
}
return x;
}
找爸爸3-—朴素：
int gfa(int x) { return fa[x]==x? x:gf(fa[x]); }
合并1——朴素（配合找爸爸1和2使用）：
void union1(int u,int v) {
int fa=gf(u) , fb=gf(v) ;
if(fa!=fb) f[fa]=fb;
}
合并2——按秩合并（配合找爸爸3使用）：
void union1 (int u,int v) {
int fa=gf(u),fb=gf(v);
if (fa!=fb) {
if(dep[fa]>dep[fb]) swap(fa,fb);
f[fa]=fb;
if (dep[fa]==dep[fb]) dep[fa]++;
}
}
最近公共祖先(LCA)
Tarjan版本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1000010
using namespace std;
int n,m,s,cnt,tot;
struct arr {
int nd,nx,num;
} bot[maxn],bot_ask[maxn]; /*用邻接链表存边*/
int head[maxn],head_ask[maxn];
int fa[maxn],ans[maxn],vis[maxn];
void add_edge(int x,int y) { /*这里是把题目中给的关系放在一个邻接链表中*/
bot[++cnt].nd=y;
bot[cnt].nx=head[x];
head[x]=cnt;
}
void add_ask(int x,int y,int num) { /*这里是把题目所给的询问存在另一个邻接链表中*/
bot_ask[++tot].nd=y;
bot_ask[tot].nx=head_ask[x];
bot_ask[tot].num=num;
head_ask[x]=tot;
}
int gf(int x) {
return fa[x]==x?x:fa[x]=gf(fa[x]); /*找爸爸*/
}
void dfs(int u) {
vis[u]=1;/*记录是否被搜索过*/
for(int i=head_ask[u]; i; i=bot_ask[i].nx)
if(vis[bot_ask[i].nd])ans[bot_ask[i].num]=gf(bot_ask[i].nd);
/*如果该点的询问对象被访问过，那吗他们的最近公共最先就是询问对象的祖先*/
for(int i=head[u]; i; i=bot[i].nx)
if(!vis[bot[i].nd]) dfs(bot[i].nd),fa[bot[i].nd]=u;
/*如果该节点没有被搜索过，继续递归下去。回溯的时候将爸爸修改一下*/
}
inline int read(){
int x=0,w=1; char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
int main() {
int x,y;
n=read();
m=read();
s=read();/*利用读入优化来读取数据会更快点*/
for(int i=1; i<=n; i++) fa[i]=i; /*初始父亲为自己*/
for(int i=1; i<=n-1; i++) {
x=read(),y=read(),add_edge(x,y),add_edge(y,x);
}
for(int i=1; i<=m; i++) {
x=read(),y=read(),add_ask(x,y,i),add_ask(y,x,i);
}
dfs(s);
for(int i=1; i<=m; i++) printf("%d
",ans[i]);
return 0;
}
倍增版本
using namespace std;
struct arr{
int u,nd,nx;
}bot[1000001];
int head[1000001],deep[1000001],fa[1000001][20];
int n,m,s,mm,stepp,cnt;
void add(int x,int y)
{ bot[++cnt].u=x; bot[cnt].nd=y; bot[cnt].nx=head[x]; head[x]=cnt; }//用邻接链表存边
void build_tree(int u){
for(int i=head[u];i;i=bot[i].nx){
int v=bot[i].nd;
if(deep[v]==0){
deep[v]=deep[u]+1; mm=max(mm,deep[v]+1);
fa[v][0]=u;
build_tree(v);
}
}
}
inline void init(){
for(int j=1;j<=stepp;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
for(int k=stepp;k>=0;k--){
if(deep[fa[x][k]]>=deep[y])
x=fa[x][k];
}
if(x==y) return y;
for(int i=stepp;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline int read(){
int x=0,w=1; char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*w;
}
int main(){
n=read();m=read();s=read();
for(int i=1;i<=n-1;i++){
int u=read(),v=read();
add(u,v),add(v,u);
}
deep[s]=1;
build_tree(s);
stepp=log2(mm);
init();
for(int i=1;i<=m;i++){
int u=read(),v=read();
printf("%d
",LCA(u,v));
}
return 0;
}
最短路
省略了最基本的几种算法
SPFA（路径条数）
/*简单的加分原理是不好搞定的，因为可能会重复累加。
于是乎，考虑定义两个数组F[x],Sf[x]分别表示到X点能传递的最短路方案数，到x点的最短路方案数。
那么很显然：
bf[a] 为true表示在队列中*/
if dis[a]=dis[b]+w<a,b> then
begin
if bf[a] then
F[a]:=F[a]+F[b]/*在队列中的话，那么其能传递的方案数并没有累加给其他点，所以要留着*/
else F[a]:=F[b];/*不在队列中的话，那么他之前能传递方案数已经累加给其他点了，那么就直接覆盖，将能传递的方案数直接赋值。*/
Sf[a]:=Sf[a]+F[b];/*对于a这个点的答案，要累加上b能传递的方案数。*/
end
if dis[a]>dis[b]+w<a,b> then
begin
dis[a]:=dis[b]+w<a,b>
F[a]:=F[b];
Sf[a]:=Sf[b];
end;
Floyd判最小环
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=1e8;
int w[102][102],g[102][102];
int n,e;
void init() {
int x,y,v;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
w[i][j]=g[i][j]=INF;
for(int i=1; i<=e; i++) {
scanf("%d%d%d",&x,&y,&v);
w[x][y]=w[y][x]=g[x][y]=g[y][x]=v;
}
}
void work() {
int ans=INF;
for(int k=1; k<=n; k++) {
for(int i=1; i<k; i++) /*最小环*/
for(int j=i+1; j<k; j++) /*为了避免一条边计算两次并且i == j时因为权重会出错*/
ans=min(ans,g[i][j]+w[i][k]+w[k][j]);
for(int i=1; i<=n; i++) /*Floyd*/
for(int j=1; j<=n; j++)
if(i!=j)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
if(ans==INF) cout<<"No solution."<<endl;
else cout<<ans<<endl;
}
int main() {
while(scanf("%d%d",&n,&e)!=EOF) {
init();
work();
}
}
强连通分量
tarjan
/*Tarjan*/
const int N =1010, M=100010;
struct node {
int to, next;
} edge[M];
int head[N], low[N], dfn[N], sta[N], belg[N], num[N];
bool vis[N];
int scc,index,top, tot;
void tarbfs(int u) {
int i,j,k,v;
low[u]=dfn[u]=++index;
sta[top++]=u;
vis[u]=1;
for(i=head[u]; i!=-1; i=edge[i].next) {
v=edge[i].to;
if(!dfn[v]) {
tarbfs(v);
if(low[u]>low[v]) low[u]=low[v];
} else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];
}
if(dfn[u]==low[u]) {
scc++;
do {
v=sta[--top];
vis[v]=0;
belg[v]=scc;
num[scc]++;
} while(v!=u) ;
}
}
void Tarjan(int n) {
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(num,0,sizeof(num));
memset(low,0,sizeof(low));
index=scc=top=0;
for(int i=1; i<=n; i++)
if(!dfn[i]) tarbfs(i);
}
void init() {
tot=0;
memset(head,-1,sizeof(head));
}
void addedge(int i,int j) {
edge[tot].to=j;
edge[tot].next=head[i];
head[i]=tot++;
}
拓扑排序(以洛谷旅行计划为例题)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
struct arr{
int nd,nx;
}bot[300000];
queue<int>q;
int n,m,tot,cnt,head[200000],top[200000],f[200000],rd[200000];
inline int read(){
int w=1,x=0;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
return x*w;
}
inline void add(int a,int b){ bot[++tot].nd=b; bot[tot].nx=head[a]; head[a]=tot; }
int main(){
n=read();m=read();
for(register int i=1;i<=m;++i){
int u=read(),v=read();
add(u,v);rd[v]++;
}
for(register int i=1;i<=n;++i)
if(!rd[i]) q.push(i);
while(!q.empty()){
top[++cnt]=q.front();q.pop();
for(register int i=head[top[cnt]];i;i=bot[i].nx){
rd[bot[i].nd]--;
if(!rd[bot[i].nd]) q.push(bot[i].nd);
}
}
for(register int k=1;k<=cnt;++k){
if(!f[top[k]])
f[top[k]]=1;
for(register int i=head[top[k]];i;i=bot[i].nx)
if(f[top[k]]+1>f[bot[i].nd])
f[bot[i].nd]=f[top[k]]+1;
}
for(register int i=1;i<=n;++i)
printf("%d
",f[i]);
}
欧拉线性筛
int main(){
int n,m,tot=0;
scanf("%d%d",&n,&m);
memset(point,0,sizeof point);
point[0]=point[1]=1;
for (int i=2;i<=n;i++){
if (point[i]==0)
prime[tot++]=i;
for (int j=0;j<tot;j++){
if (i*prime[j]>n) break;
point[i*prime[j]]=1;
if (i % prime[j]==0) break;
}
}
for (int i=1;i<=m;i++){
int a;
scanf("%d",&a);
if (point[a]==0) printf("Yes
");
else printf("No
");
}
}
快速幂+多项式系数
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,k,a,b;
int C[1005][1005];
inline int mi(int a,int b){
long long w=a,s=1;
for(;b;b>>=1){
if(b&1) s=(s*w)%10007;
w=(w*w)%10007;
}
return s;
}
int main(){
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
C[0][0]=1;
for(int i=1;i<=k;i++) C[i][0]=1,C[i][i]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%10007;
printf("%d",((C[k][m]*mi(a,n)%10007)*mi(b,m))%10007);
return 0;
}
RMQ
using namespace std;
int a[50001],dp[50001][20]; /*a是原数组,dp是动归数组*/
int n;
inline int maxn(int a,int b) {return a>b?a:b;}
/*两种方法处理DP数组*/
/*方法一:dp数组存最大值*/
void ST1() {
for(int i=1; i<=n; i++) dp[i][0]=a[i];/*初始化*/
for(int j=1; (1<<j)<=n; j++) {/*dp[i][j]表示从第i位开始，往后第(2^j)-1位*/
for(int i=1; i+(1<<j)-1<=n; i++) {/*范围不能超过长度n
dp[i][j]=maxn(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);*/
/*因为是二分，所以尽可能地把当前这一段给覆盖掉*/
/*一个是从第i位往后2^j-1位，这里为一半，另一半是从第i+j^2开始，往后2^j-1,可以刚好覆盖掉 */
}
}
}
int rmq1(int l,int r) {
int j=0;
while((1<<(j+1))<=r-l+1) j++;/*查询的时候，尽可能地使j变大能够刚好使j^2的长度能够覆盖这段区间 */
return maxn(dp[l][j],dp[r-(1<<j)+1][j]);/*左边一半，右边一半qu最值 */
}
/*方法二:dp数组存最大值的编号*/
void ST2(int n) {
for(int i=1; i<=n; i++)/*存最大编号的稍微改一下 */
dp[i][0] = i;
for(int j=1; (1<<j)<=n; j++) {
for(int i=1; i+(1<<j)-1<=n; i++) {
int x = dp[i][j-1] , y = dp[i+(1<<(j-1))][j-1];
dp[i][j] = a[x]<a[y]?x:y;
}
}
}
int rmq2(int l,int r) {
int j=0;
while((1<<(j+1))<=r-l+1) j++;
int x=dp[l][j] , y=dp[r-(1<<j)+1][j];
return maxn(a[x],a[y]);
}
KMP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include <iostream>
#include <string>
using namespace std;
int f[15000];
void getfill(string s) {
memset(f,0,sizeof(f)); /*根据其前一个字母得到*/
for(int i=1; i<s.size(); i++) {
int j=f[i];
while(j && s[i]!=s[j]) j=f[j];
f[i+1]=(s[i]==s[j])?j+1:0;
}
}
int find(string a,string s) {
int ans=0;
getfill(s);
int j=0;
for(int i=0; i<a.size(); i++) {
while(j && a[i]!=s[j]) j=f[j];
if(a[i]==s[j]) j++;
if(j==s.size()) { ans++; }
}
return ans;
}
int main() {
string s,a;
int T;
scanf("%d",&T);
while(T--) {
getchar();
cin>>s>>a;
int ans=find(a,s);
printf("%d
",ans);
}
return 0;
}
/*
void getFail(char* P,int* f){
int m=strlen(P);
f[0]=f[1]=0;
for(int i=1;i<m;i++){
int j=f[i];
while(j&&P[i]!=P[j]) j=f[j];
f[i+1]=P[i]==P[j]?j+1:0;
}
}
void Find(char* T,char* P,int* f){
int n=strlen(T),m=strlen(P);
getFail(P,f);
int j=0;
for(int i=0;i<n;i++){
while(j&&P[j]!=T[i]) j=f[j];
if(P[j]==T[i]) j++;
if(j==m) printf("%d
",i-m+1);
}
}
*/
Trie树
指针
int n, m;
struct NODE {
int cnt; NODE *next[26];
NODE() {
cnt = 0;
memset(next, NULL, sizeof(next));
}
};
char s[15];
void Insert(NODE *root, char *s) {
int len = strlen(s);
NODE *p = root;
for(int i = 0; i < len; i++) {
int idx = s[i] - 'a';
if(p -> next[idx] == NULL) p -> next[idx] = new NODE();
p = p -> next[idx]; p -> cnt ++;
}
}
int Search(NODE *root, char *s) {
int len = strlen(s);
NODE *p = root;
for(int i = 0; i < len; i++) {
int idx = s[i] - 'a';
if(i != len && p -> next[idx] == NULL) return 0;
p = p -> next[idx];
}
return p -> cnt;
}
int main() {
scanf("%d", &n);{
NODE *root = new NODE();
for(int i = 0; i < n; i++) {
scanf("%s", s);
Insert(root, s);
}
scanf("%d", &m);
while(m --) {
scanf("%s", s);
printf("%d
", Search(root, s));
}
}
}
Trie（数组）
int const MAX = 2600005;
int n, m;
char s[15];
struct Trie {
int next[MAX][26], cnt[MAX], tot, root;
inline int Newnode() {
memset(next[tot], -1, sizeof(next[tot]));
return tot ++;
}
inline void Init() {
memset(cnt, 0, sizeof(cnt));
tot = 0; root = Newnode();
}
inline void Insert(char *s) {
int len = strlen(s);
int p = root;
for(int i = 0; i < len; i++) {
int idx = s[i] - 'a';
if(next[p][idx] == -1) next[p][idx] = Newnode();
p = next[p][idx]; cnt[p] ++;
}
}
inline int Search(char *s) {
int len = strlen(s); int p = root;
for(int i = 0; i < len; i++) {
int idx = s[i] - 'a';
if(i != len && next[p][idx] == -1) return 0;
p = next[p][idx];
}
return cnt[p];
}
} t;
int main() {
while(scanf("%d", &n) != EOF) {
t.Init();
for(int i = 0; i < n; i++) { scanf("%s", s); t.Insert(s); }
scanf("%d", &m);
while(m --) {
scanf("%s", s); printf("%d
", t.Search(s));
}
}
}