STL算法
STL 算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序），头文件是：#include <algorithm>。常用STL 算法库包括：sort快速排序算法、二分查找算法、枚举排列算法等。
1、 sort排序系列
sort：对给定区间所有元素进行排序（全排）
stable_sort：对给定区间所有元素进行稳定排序，就是相等的元素位置不变，原来在前面的还在前面。
partial_sort：对给定区间所有元素部分排序，就是找出你指定的数目最小或最大的值放在最前面或最后面，比如说我只要找到1000000个数中最大的五个数，那你用这个函数是最好的，排序后最大的五个数就在最前面的五个位置，其他的元素位置分布不确定。
partial_sort_copy：对给定区间复制并排序，和上面的一样，只是这是指定区间进行复制然后排序的。
nth_element：找出给定区间的某个位置对应的元素，根据比较函数找到第n个最大（小）元素，适用于寻找“第n个元素”。
is_sorted：判断一个区间是否已经排好序（返回bool值判断是否已排序）
partition：使得符合某个条件的元素放在前面，划分区间函数，将 [first, last]中所有满足的元素置于不满足的元素前面，这个函数会返回迭代器，设返回的迭代器为 i，则对 [first, i]中的任意迭代器 j，*j满足给定的判断，对 [i, last] 中的任意迭代器 k，*k不满足。
stable_partition：相对稳定的使得符合某个条件的元素放在前面（和上面的一样，只是位置不变）
使用时根据需要选择合理的排序函数即可，所有的排序函数默认从小到大排序，可以定义自己的比较方式。
2、二分系列
二分检索，复杂度O(log(last-first))
itr =upper_bound(first, last, value, cmp);
//itr 指向大于value 的第一个值(或容器末尾)
itr = lower_bound(first, last, value, cmp);
//itr 指向不小于valude 的第一个值(或容器末尾)
pairequal_range(first, last, value, cmp);
//找出等于value的值的范围O(2*log(last–first))
Binary_search(first,last, value)返回bool值，找到则true，否则false。
二分经常会与其他算法结合。
例：HDU 1496
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int val[40010];
int main() {
pair <int*, int*> p;
int a, b, c, d;
while (cin >> a >> b >> c >> d) {
if( (a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0)){
cout << 0 << endl;
continue;
}
memset(val, 0, sizeof(val));
int k = 0;
for (int i = -100; i <= 100; i++){
if (i == 0) continue;
for (int j = -100; j <= 100; j++) {
if (j == 0) continue;
val[k++] = a*i*i + b*j*j;
}
}
sort(val, val+k);
int cnt = 0;
for (int j = -100; j <= 100; j++) {
if (j == 0) continue;
for (int i = -100; i <= 100; i++) {
if (i == 0) continue;
int sum = c*j*j + d*i*i;
p = equal_range(val, val+k, -sum);
cnt += p.second - p.first;
}
}
cout << cnt << endl;
}
return 0;
}
3、排列系列
next_permutation是一个求一个排序的下一个排列的函数，可以遍历全排列，要包含头文件<algorithm>，与之完全相反的函数还有prev_permutation。
int 类型的next_permutation
int main()
{
int a[3];
a[0]=1;a[1]=2;a[2]=3;
do
{
cout<<a[0]<<""<<a[1]<<" "<<a[2]<<endl;
} while (next_permutation(a,a+3));
}
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
char 类型的next_permutation
int main()
{
char ch[205];
cin >> ch;
sort(ch, ch + strlen(ch) );
char *first = ch;
char *last = ch + strlen(ch);
do {
cout<< ch << endl;
}while(next_permutation(first, last));
return 0;
}
string 类型的next_permutation
int main()
{
string line;
while(cin>>line&&line!="#")
{
if(next_permutation(line.begin(),line.end()))
cout<<line<<endl;
else cout<<"Nosuccesor\n";
}
}
int main()
{
string line;
while(cin>>line&&line!="#")
{
sort(line.begin(),line.end());
cout<<line<<endl;
while(next_permutation(line.begin(),line.end()))
cout<<line<<endl;
}
}
4、常用函数
copy、copy_if：copy直接拷贝，比for循环高效，最坏为线性复杂度，而且这个可以说是一个copy族函数，还有类似的满足一定条件的copy_if等。
find、find_i：查找第一个匹配的值或第一个满足函数使其为true的值位置，没有返回指定区间的末尾，线性复杂度，还有一些不怎么常用的find族函数就不多介绍了。
count、count_if：返回匹配或使函数为true的值的个数，线性复杂度。
search：这是寻找序列是否存在于另一个序列中的函数，挺好用的，某些简单的寻找公共子串的题就可以这样写，时间复杂度二次。
reverse：翻转一个区间的值，我经常遇到需要这种题，直接reverse了，不需要for循环了，主要是方便。
for_each：直接对一个区间内的每个元素执行后面的函数操作，写起来简单。
max、min、max_element、min_element：寻找两个数或者一个区间的最大最小值，都可以添加比较函数参数。
集合操作函数：includes、set_union、set_difference、set_intersection、set_symmetric_difference、前面这些函数的最差复杂度为线性，另外附加一个序列的操作函数merge，相当于归并排序中的合并函数，时间复杂度为线性，注意这些函数的操作对象都必须是升序的。
例：
#include<cstdio>
#include<algorithm>
using namespace std;
void out(int a) { if (a != -1) printf("%d ",a); }
int main() {
int a[5] = {1, 8, 10, 52, 100};
int b[5] = {6, 8, 9, 10, 1000};
int c[20];
printf("a集合为：");
for_each(a, a+5, out);
puts("");
printf("b集合为：");
for_each(b, b+5, out);
puts("");
//判断b是否是a的子集。
if(includes(a, a+5, b, b+5)) printf("bis a sub set of a\n");
//合并两个有序序列，必须为合并后的序列分配空间，否则程序会崩溃。
printf("两个集合的合并序列为：");
merge(a, a+5, b, b+5, c);
for_each(c, c+10, out);
puts("");
//求两个集合的并集。
fill(c, c+20, -1);
set_union(a, a+5, b, b+5, c);
printf("两个集合的并集为：");
for_each(c, c+10, out);
puts("");
//求两个集合的交集。
fill(c, c+20, -1);
set_intersection(a, a+5, b, b+5, c);
printf("两个集合的交集为：");
for_each(c, c+10, out);
puts("");
//求两个集合的差集，这里为a-b。
fill(c, c+20, -1);
set_difference(a, a+5, b, b+5, c);
printf("a-b的差集为：");
for_each(c, c+10, out);
puts("");
//求两个集合的差集，这里为b-a。
fill(c, c+20, -1);
set_difference(b, b+5, a, a+5, c);
printf("b-a的差集为：");
for_each(c, c+10, out);
puts("");
//求两个集合的对称差
set_symmetric_difference(a, a+5, b, b+5,c);
printf("两个集合的对称差为：");
for_each(c, c+10, out);
puts("");
return 0;
}
树结构模板
1、树状数组
例：HDU 1166
#include<stdio.h>
#include<math.h>
const intMAX = 50010 * 4;
intsegment[MAX];
voidpushUp(int root)
{
segment[root] = segment[root * 2] + segment[root* 2 + 1];
}
voidbuildTree(int root, int left, int right)
{
if(left == right)
{
scanf("%d",&segment[root]);
return;
}
int mid = (left + right) / 2;
buildTree(root * 2, left, mid);
buildTree(root * 2 + 1, mid + 1, right);
pushUp(root);
}
voidupdate(int root, int pos, int add_num, int left, int right)
{
if (left == right)
{
segment[root] += add_num;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update(root * 2, pos, add_num, left,mid);
else
update(root * 2 + 1, pos, add_num, mid+ 1, right);
pushUp(root);
}
intgetSum(int root, int left, int right, int L, int R)
{
if(left == L && right == R)
{
return segment[root];
}
int mid = (L + R) / 2;
int res = 0;
if(left > mid)
{
res += getSum(root * 2 + 1, left,right, mid + 1, R);
}
else if(right <= mid)
{
res += getSum(root * 2, left, right, L,mid);
}
else
{
res += getSum(root * 2, left, mid, L,mid);
res += getSum(root * 2 + 1, mid + 1,right, mid + 1, R);
}
return res;
}
int main()
{
int T;
scanf("%d", &T);
for(int kase = 1; kase <= T; kase++)
{
int n;
scanf("%d", &n);
buildTree(1, 1, n);
char op[10];
int t1, t2;
printf("Case %d:\n", kase);
while(scanf("%s", op))
{
if(op[0] == 'E')
break;
scanf("%d %d", &t1,&t2);
if(op[0] == 'A')
{
update(1, t1, t2, 1, n);
}
else if(op[0] == 'S')
{
update(1, t1, -t2, 1, n);
}
else
{
printf("%d\n",getSum(1, t1, t2, 1, n));
}
}
}
return 0;
}
2、后缀树
例：CodeForces 128B
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdlib.h>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#pragma comment(linker, "/STACK:1024000000,1024000000")
template <class T>
bool scanff(T &ret){ //Faster Input
char c; int sgn; T bit=0.1;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
if(c==' '||c=='\n'){ ret*=sgn; return 1; }
while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
ret*=sgn;
return 1;
}
#define inf 1073741823
#define llinf 4611686018427387903LL
#define PI acos(-1.0)
#define lth (th<<1)
#define rth (th<<1|1)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define drep(i,a,b) for(int i=int(a);i>=int(b);i--)
#define gson(i,root) for(int i=ptx[root];~i;i=ed[i].next)
#define tdata int testnum;scanff(testnum);for(int cas=1;cas<=testnum;cas++)
#define mem(x,val) memset(x,val,sizeof(x))
#define mkp(a,b) make_pair(a,b)
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SIZE 27
struct suffixtree{
struct node{
int l,r,point,a[SIZE];
void init(){
mem(a,0);
point=l=0;
r=-1;
}
}T[400011];
char s[400011];
int actnode,actride,actline;
int rest,total,temp,linker,len;
void builtleaf(int root,int line){
total++;
T[total].init();
T[total].l=len;
T[total].r=100000001;
T[root].a[line]=total;
rest--;
}
bool pd_ride(int next){
temp=T[next].r-T[next].l+1;
if(actride>=temp){
actride-=temp;
actnode=next;
actline+=temp;
return true;
}
return false;
}
void link(int x){
if(linker>0)T[linker].point=x;
linker=x;
}
void insert(int wait){
s[++len]=wait;
rest++;
linker=0;
while(rest>0){
if(actride==0)actline=len;
if(T[actnode].a[s[actline]]==0){
builtleaf(actnode,s[actline]);
link(actnode);
}
else{
int next=T[actnode].a[s[actline]];
if(pd_ride(next))continue;
if(s[T[next].l+actride]==wait){
actride++;
link(actnode);
break;
}
total++;
T[total].init();
T[actnode].a[s[actline]]=total;
T[total].l=T[next].l;
T[total].r=T[next].l+actride-1;
T[next].l+=actride;
T[total].a[s[T[next].l]]=next;
link(total);
builtleaf(total,wait);
}
if(actnode==0&&actride>0){
actride--;
actline=len-rest+1;
}
else actnode=T[actnode].point;
}
}
void clear(){
total=0;
len=0;
T[0].init();
actnode=actride=actline=0;
}
void debug(){
rep(i,0,total){
printf("T[%d] (%d %d)\n",i,T[i].l,T[i].r);
}
}
}st;
#define NN 400400
char s[NN];
ll cot[NN];
ll sum;
ll k;
int len;
ll getcot(int x){
ll temp=0;
ll bj=1;
rep(i,0,26){
if(st.T[x].a[i]){
bj=0;
temp+=getcot(st.T[x].a[i]);
}
}
cot[x]=temp+bj;
return cot[x];
}
ll edr,edx;
int alen=0;
char ans[NN];
void dfs(int x){
sum+=(ll)(min(st.T[x].r,len)-st.T[x].l+1)*cot[x];
if(sum>=k){
edx=x;
edr=min(ll(st.T[x].r),ll(len));
while(sum-cot[x]>=k){
sum-=cot[x];
edr--;
}
//printf("%lld %lld\n",edx,edr);
//return;
}
rep(i,0,26){
if(st.T[x].a[i]&&sum<k){
dfs(st.T[x].a[i]);
}
}
if(sum>=k){
drep(i,min(edr,ll(st.T[x].r)),st.T[x].l){
ans[alen++]=s[i];
}
}
}
main(){
st.clear();
scanf("%s",s+1);
len=strlen(s+1);
rep(i,1,len)st.insert(s[i]-'a');
st.insert(26);
scanf("%lld",&k);
if(ll(len)*ll(len+1)/2LL<k){
printf("No such line.\n");
return 0;
}
getcot(0);
dfs(0);
ans[alen]=0;
reverse(ans,ans+alen);
printf("%s\n",ans);
}
3、线段树
例：HDU 1542
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
usingnamespace std;
constint SIZE=505;
intadd[SIZE<<2];
doublex[SIZE<<2],sum[SIZE<<2];
structnode{
int ss;
double l,r,h;
node(){}
node(double a,double b,double c,intd):l(a),r(b),h(c),ss(d){}
friend bool operator<(node p,node q){
return p.h<q.h;
}
}s[SIZE];
voidpushup(int rt,int l,int r){
if(add[rt])
sum[rt]=x[r+1]-x[l];
else if(l==r)
sum[rt]=0;
else
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
voidupdate(int L,int R,int c,int l,int r,int rt){
int m;
if(L<=l&&r<=R){
add[rt]+=c;
pushup(rt,l,r);
return;
}
m=(l+r)>>1;
if(L<=m)
update(L,R,c,l,m,rt<<1);
if(R>m)
update(L,R,c,m+1,r,rt<<1|1);
pushup(rt,l,r);
}
intmain(){
int n,i,k,l,m,r,cas;
double a,b,c,d,ans;
cas=1;
while(scanf("%d",&n)!=EOF&&n){
k=1,ans=m=0;
for(i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x[m]=a;
s[m++]=node(a,c,b,1);
x[m]=c;
s[m++]=node(a,c,d,-1);
}
sort(x,x+m);
sort(s,s+m);
for(i=1;i<m;i++)
if(x[i]!=x[i-1])
x[k++]=x[i];
memset(add,0,sizeof(add));
memset(sum,0,sizeof(sum));
for(i=0;i<m-1;i++){
l=lower_bound(x,x+k,s[i].l)-x;
r=lower_bound(x,x+k,s[i].r)-x-1;
update(l,r,s[i].ss,0,k-1,1);
ans+=(sum[1]*(s[i+1].h-s[i].h));
}
printf("Test case #%d\nTotalexplored area: %.2lf\n\n",cas++,ans);
}
return 0;
}
4、并查集
例：POJ 2492
#include<stdio.h>
#define N 2002
int fa[N],rank[N],resex[N];
void init(int len)
{
int i;
for(i=1;i<=len;i++)
{
fa[i]=i;
rank[i]=0;
resex[i]=0;
}
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);//路径压缩
}
return fa[x];
}
void Union(int a,int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])//按秩合并
fa[y]=x;
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int T,n,m,i,a,b,num=0,flag;
scanf("%d",&T);
while(num<T)
{
flag=1;
num++;
scanf("%d%d",&n,&m);
init(n);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(!flag)continue;
int x=find(a);
int y=find(b);
if(x==y)flag=0;
if(resex[a]!=0)Union(resex[a],b);
else resex[a]=b;
if(resex[b]!=0)Union(resex[b],a);
else resex[b]=a;
}
printf("Scenario#%d:\n",num);
if(!flag)
printf("Suspiciousbugs found!\n\n");
else
printf("Nosuspicious bugs found!\n\n");
}
return 0;
}
支付宝扫一扫
