|
STL算法 STL 算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序），头文件是：#include 1、 sort排序系列 sort：对给定区间所有元素进行排序（全排） 使用时根据需要选择合理的排序函数即可，所有的排序函数默认从小到大排序，可以定义自己的比较方式。
2、二分系列 二分检索，复杂度O(log(last-first)) 二分经常会与其他算法结合。 例：HDU 1496 #include #include #include using namespace std; int val[40010]; int main() { pair int a, b, c, d; while (cin >> a >> b >> c >> d) { if( (a > 0 && b > 0 && c > 0 && d > 0) || (a <><><><> cout <><> continue; } memset(val, 0, sizeof(val)); int k = 0; for (int i = -100; i <> if (i == 0) continue; for (int 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 <> if (j == 0) continue; for (int 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 <><> } return 0; }
3、排列系列 next_permutation是一个求一个排序的下一个排列的函数，可以遍历全排列，要包含头文件 int 类型的next_permutation int main() { int a[3]; a[0]=1;a[1]=2;a[2]=3; do { cout<><><><'><><> } 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=""><> }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<><> else cout<> } } int main() { string line; while(cin>>line&&line!='#') { sort(line.begin(),line.end()); cout<><> while(next_permutation(line.begin(),line.end())) cout<><> } }
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 #include 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 #include 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 <=> 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 <=> { 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;=""> {
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 #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, '/STACK:1024000000,1024000000') template 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<> if(c==' '||c=='\n'){ ret*=sgn; return 1; } while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit> ret*=sgn; return 1; } #define inf 1073741823 #define llinf 4611686018427387903LL #define PI acos(-1.0) #define lth (th<> #define rth (th<> #define rep(i,a,b) for(int i=int(a);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<> #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 #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<> 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<> 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 #include #include #include usingnamespace std; constint SIZE=505; intadd[SIZE<> doublex[SIZE<><> 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=""> return p.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<><> } voidupdate(int L,int R,int c,int l,int r,int rt){ int m; if(L<><> add[rt]+=c; pushup(rt,l,r); return; } m=(l+r)>>1; if(L<> update(L,R,c,l,m,rt<> if(R>m) update(L,R,c,m+1,r,rt<> 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<> 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<> if(x[i]!=x[i-1]) x[k++]=x[i]; memset(add,0,sizeof(add)); memset(sum,0,sizeof(sum)); for(i=0;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 #define N 2002 int fa[N],rank[N],resex[N]; void init(int len) { int i; for(i=1;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<> { flag=1; num++; scanf('%d%d',&n,&m); init(n); for(i=1;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; } 另：为感谢各位家长一直以来对融科信息学的信任与支持，在双十二来临之际，特推出双十二底价团购信息学课程，详情点击链接→融科教育双十二同学“惠”，信息学课程底价疯狂抢！（←点击链接，了解活动详情吧） 长沙信息学竞赛 |
|
|
