ACM-ICPC常用模板更新

1、数据结构

并查集

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

int size[maxn], ranks[maxn];
int fa[maxn];
int find(int x){
    if(fa[x] == x)return x;
    int t = find(fa[x]);
    ranks[x] += ranks[fa[x]]; //路径压缩时需要更新当前位置
    return fa[x] = t;
}
void merge(int x, int y){
    int a = find(x), b = find(y);
    fa[a] = b; //x整列接到y后面
    ranks[a] += size[b];//x的首元素位置加上y的长度
    size[b] += size[a];//b的长度加上a的长度
    size[a] = 0;
}

2、数学

卢卡斯组合数

LL fac[maxn], inv[maxn];
LL mpow(LL a, LL x) {
	if(x==0)return 1;
	LL t = mpow(a, x>>1);
	if(x%2==0)return t*t%mod;
	return t*t%mod*a%mod;
}
LL init(){
	fac[0]=inv[0]=1;
	for(int i = 1; i < maxn; i++){
		fac[i]=fac[i-1]*i%mod; inv[i]=mpow(fac[i],mod-2);
	}return 0;
}
LL C(int x, int y) {
	if(y<0 || y>x)return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}

3、STL

优先队列

priority_queue<int, vector<int>, greater<int> >q;  //小根堆
priority_queue<int, vector<int>, less<int> >q; //大根堆
struct node{int x, y;};//比较函数
struct cmp{
	bool operator()(node a, node b){
		return a.x > b.x;
	}
};
priority_queue<node, vector<node>, cmp>q;

二分

//lower_bound：返回第一个大于等于x的位置
int p1=lower_bound(a,a+n,x)-a;
//upper_bound：返回第一个大于x的位置
int p2=upper_bound(a,a+n,x)-a;
//lower_bound2：返回数组中第一个小于或等于x的值 
int p3=lower_bound(a,a+n,x,greater<int>())-a;
//upper_bound2：返回数组中第一个小于x的值 
int p4=upper_bound(a,a+n,x,greater<int>())-a;

struct cmp_lower{
    bool operator () (int a,int b){
        return index[a]<b;
    }
};
int lower_result=lower_bound(ar.begin(),ar.end(),x+1,cmp_lower())-ar.begin();

去重

int count = unique(a, a+n)-a;
for(int i = 0; i < count; i++)printf("%d ", a[i]);

可重map，set

multiset 
multimap 

bitset

bitset

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/114992343