一.STL

原則上手寫要比用STL快，不過有些確實難打···

map和set直接用就好，都是基于紅黑樹實現(xiàn)（根本不會打），效率已經(jīng)足夠高（當然不懼碼量的巨佬也可以手打）

#include<cstdio> #include<cstdlib> using namespace std; #define L tree[x].l #define R tree[x].r int const N=2e5+5; int root,n,opt,st,t; struct Treap{int l,r,id,weight,size; }tree[N]; inline int apply(int x){int k=++t;tree[k].id=x,tree[k].weight=rand();tree[k].size=1;return k; } inline void get(int x){tree[x].size=tree[L].size+tree[R].size+1;return ; } void split(int x,int val,int &a,int &b){if(!x){a=b=0;return ;}if(tree[x].id<=val){a=x;split(R,val,R,b);}else{b=x;split(L,val,a,L);}get(x);return ; } int merge(int x,int y){if(!x || !y)return x+y;if(tree[x].weight<tree[y].weight){R=merge(R,y);get(x);return x;}tree[y].l=merge(x,tree[y].l);get(y);return y; } void insert(int x){int a,b;split(root,x,a,b);root=merge(merge(a,apply(x)),b);return ; } void del(int y){int a,b,x;split(root,y,a,b);split(a,y-1,a,x);root=merge(merge(a,merge(L,R)),b);return ; } int rk(int x){int a,b,ans;split(root,x-1,a,b);ans=tree[a].size+1;root=merge(a,b);return ans; } int find(int x,int y){while(tree[L].size+1!=y)if(y<=tree[L].size)x=L;else y-=tree[L].size+1,x=R;return tree[x].id; } int pre(int x){int a,b,ans;split(root,x-1,a,b);ans=find(a,tree[a].size),root=merge(a,b);return ans; } int nxt(int x){int a,b,ans;split(root,x,a,b);ans=find(b,1),root=merge(a,b);return ans; } int main(){scanf("%d",&n);while(n--){scanf("%d%d",&opt,&st);switch(opt){case 1:insert(st);break;case 2:del(st);break;case 3:printf("%d\n",rk(st));break;case 4:printf("%d\n",find(root,st));break;case 5:printf("%d\n",pre(st));break;case 6:printf("%d\n",nxt(st));break;}}return 0; } 為證明自己是不懼碼量的巨佬強行肝的一棵不是紅黑樹的普通平衡樹

map確實很方便，不過有一種神奇的東西叫做hash表，可以以近似$\Theta(1)$的效率進行查詢^_^（就是有點不穩(wěn)定……）

#include<cstdio> using namespace std; int const mod=7e5+1,N=1e5+5; int head[mod+2],Next[N],to[N],t; inline int up(int x){return x<0?x+mod:x; } inline int ins(int x){int z=up(x%mod);for(register int i=head[z];i;i=Next[i])if(to[i]==x)return i;Next[++t]=head[z],head[z]=t;to[t]=x;return t; } int main(){int n;scanf("%d",&n);for(register int i=1;i<=n;++i){int x;scanf("%d",&x);printf("%d\n",ins(x));//返回離散后對應(yīng)的值 }return 0; } View Code

堆（優(yōu)先隊列）可以考慮手寫，不過大部分情況直接用就行

但手寫堆也有好處，就是快啊可以刪除堆中的元素

#include<cstdio> #include<cstring> using namespace std; int const N=1e5+5; int heap[N],n; inline void swap(int &x,int &y){x^=y^=x^=y;return ; } struct node{ //大根堆int heap[N],n;inline void clear(){ //清空n=0;memset(heap,0,sizeof(heap));return ;}inline bool empty(){ //判斷是否為空return !n;}inline int size(){ //返回元素個數(shù)return n;}inline void up(int x){ //向上調(diào)整while(x^1)if(heap[x]>heap[x>>1])swap(heap[x],heap[x>>1]),x>>=1;else return ;}inline void down(int x){ //向下調(diào)整int s=x<<1;while(s<=n){if(s<n && heap[s]<heap[s|1])s|=1;if(heap[s]>heap[x]){swap(heap[s],heap[x]);x=s,s<<=1;}else return ;}}inline void push(int x){ //插入元素xheap[++n]=x;up(n);return ;}inline int top(){return heap[1];} //返回堆中的最大值inline void pop(){heap[1]=heap[n--];down(1);return ;} //刪除堆頂inline void erase(int x){ //刪除下標為x的節(jié)點heap[x]=heap[n--];up(x),down(x);return ;}inline int* begin(){ //返回堆中第一個元素的指針（實在不會搞迭代器……）return &heap[1];}inline int* end(){ //返回堆的尾部邊界return &heap[n+1];}inline int &operator [] (int x){return heap[x];} }q; int main(){//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);int t;scanf("%d",&t);for(register int i=1;i<=t;++i){int z;scanf("%d",&z);q.push(z);}for(register int* i=q.begin();i!=q.end();++i) //遍歷1printf("%d ",*i);for(register int i=1;i<=q.size();++i) //遍歷2printf("%d\n",q[i]);while(!q.empty()){ //從大到小輸出printf("%d ",q.top());q.pop();}return 0; } View Code

至于stack和queue，必須手寫！！！

注意stack打法，do-while循環(huán)更加方便

#include<iostream> using namespace std; int stack[1000],top;//棧 int q[1000],t,u; //隊列 int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin>>n;for(register int i=1;i<=n;++i){cin>>q[++t];stack[top++]=q[t];}do{cout<<stack[--top]<<" ";}while(top);cout<<endl;while(u^t)cout<<q[++u]<<" ";return 0; } View Code

vector其實不是很快，有個題我沒用vecotr但比用vector的多個sort，結(jié)果比開vector的快1倍（雖然我二分手打sort隨機化還加了fread）

所以內(nèi)存允許的話直接開2維數(shù)組（但vector確實挺方便，也不能總犧牲碼量優(yōu)化時間吧，所以想用就用）

pair也挺好，不過自定義結(jié)構(gòu)體更快

總之，c++內(nèi)置的改成手打一定變快，除非你打錯了……

二.運算

mod定義成const

能乘不除，能加減別用魔法模法

能位運算就別用加減乘除···

x2^n改成<<n

/2^n改成>>n

swap(x,y)改成x^=y^=x^=y

模數(shù)若為2^n可以直接&(mod-1)

也可以先開unsigned int最后取模

兩個小于模數(shù)相加用down(x)

(x%mod+mod)%mod改成up(x%mod)

inline int down(int x){return x<mod?x:x-mod; } inline int up(int x){return x<0?x+mod:x; } View Code

數(shù)據(jù)范圍不大可以開long long，中間不取模最后再取

判斷奇偶&1

i!=-1改為～i

!=直接改成^

三.讀入

別用cin，用cin就在主函數(shù)加：

ios::sync_with_stdio(false);

cin.tie(0);

打著還麻煩，所以就用scanf或快讀

不超過1e5的數(shù)據(jù)scanf即可

再大了最好用快讀

記得位運算優(yōu)化···

還嫌慢上fread（不過這個玩意有時候還會有意想不到的奇效，比如讓你的程序慢十倍，慎用）

快讀還有一些妙用

比如定義常量不能scanf但可用快讀賦值

這在一些讀取模數(shù)的題目中很有用

下面代碼里快讀讀的是非負整數(shù)，讀整數(shù)特判一下有無‘-’即可，就不給出實現(xiàn)了

#include<cstdio> #include<iostream> using namespace std; int const L=1<<20|1; char buf[L],*S,*T; #define getchar() ((S==T&&(T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++) inline int read(){int ss=0;char bb=getchar();while(bb<48||bb>57)bb=getchar();while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();return ss; } int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin>>n;n=read();puts("233");return 0; } View Code

四.輸出

同理，用printf別用cout

快輸是個危險東西，搞不好還會變慢

慎用非遞歸版快輸，輸不了零

不過非遞歸快一點，實在不行特判~

#include<cstdio> #include<iostream> using namespace std; char ch[20],top; inline void write(int x){ //非遞歸 while(x){ch[top++]=x%10;x=x/10;}do{putchar(ch[--top]+48);}while(top);puts("");return ; } void out(int x){ //遞歸 if(x>=10)out(x/10);putchar(x%10+48);return ; } int main(){int n=233;write(n);out(n);return 0; } View Code

ps. skyh大神表示非遞歸版改成do-while循環(huán)就能輸出0了，%%%

#include<bits/stdc++.h> using namespace std; char ch[100],top; inline void write(int x){do{ch[top++]=x%10;x/=10;}while(x);do{putchar(ch[--top]+48);}while(top);return ; } signed main(){write(5);write(2);write(0);return 0; } View Code

五.dp

其實已經(jīng)不算卡常了，可以說是剪枝···

1.排除冗雜

能不dp的就別dp

說白了就是for循環(huán)里設(shè)個限制條件

比如可憐與超市一題

yzh巨佬重設(shè)了個tmp數(shù)組實現(xiàn)$\Theta(N^2)$轉(zhuǎn)移，還證明了一波復(fù)雜度，%%%

但其實$\Theta(N^3)$可過···

#include<cstdio> #include<cstring> using namespace std; int const N=5005,lar=0x3f3f3f3f,L=1<<20|1; char buf[L],*S,*T; #define getchar() ((S==T&&(T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++) inline int read(){int ss=0;char bb=getchar();while(bb<48 || bb>57)bb=getchar();while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();return ss; } inline void swap(int &x,int &y){int z=x;x=y,y=z;return ; } inline int max(int x,int y){return x>y?x:y; } inline int min(int x,int y){return x<y?x:y; } int n,m,pp; int c[N],d[N],f[N][N][2]; int head[N],Next[N],to[N],t; int siz[N],lim[N]; inline void add(int x,int y){to[++t]=y;Next[t]=head[x],head[x]=t;return ; } void dfs(int x){int y,now=2;siz[x]=1;f[x][1][0]=c[x];f[x][1][1]=c[x]-d[x];for(int i=head[x];i;i=Next[i]){dfs(y=to[i]);siz[x]+=siz[y=to[i]];for(register int j=siz[x];j>=0;--j){int lit=min(now,j);for(register int k=(j>lim[y])?j-lim[y]:1;k<lit;++k){int o=j-k;f[x][j][0]=min(f[x][j][0],f[y][o][0]+f[x][k][0]);f[x][j][1]=min(f[x][j][1],min(f[y][o][0],f[y][o][1])+f[x][k][1]);}f[x][j][0]=min(f[x][j][0],f[y][j][0]);}for(register int j=siz[x];j>=0;--j)if(f[x][j][0]<=m || f[x][j][1]<=m){now=j+1;break;}}for(register int i=1;i<=siz[x];++i)if(f[x][i][1]>=m && f[x][i][0]>=m){lim[x]=i;return ;}lim[x]=siz[x];return ; } int main(){memset(f,0x3f,sizeof(f));n=read(),m=read(),c[1]=read(),d[1]=read();for(register int i=2;i<=n;++i){c[i]=read(),d[i]=read();add(read(),i);}dfs(1);for(register int i=lim[1];i>=0;--i)if(f[1][i][0]<=m || f[1][i][1]<=m){printf("%d",i);return 0;} } View Code

2.等效替代

說起來很模糊···

以HAOI2015樹上染色為例

染黑點和染白點其實一樣

所以你完全可以加一句k=min(k,n-k);

六.初始化

單個變量可以直接初始化，好像比賦值初始化略快

小范圍初始化數(shù)組直接memset

對于單一數(shù)組memset就是比for循環(huán)要快，不要懷疑！！！

有時后你覺得for循環(huán)快，那不是因為數(shù)據(jù)水與極限數(shù)據(jù)相差太遠就是因為你連清了五個以上數(shù)組。

清大量范圍相同的數(shù)組才采用for

對于一些題目你覺得memset用sizeof(數(shù)組名)清數(shù)組很浪費也可以改成sizeof(int)*長度，不過一般沒有必要

當然一些情況你完全可以邊f(xié)or邊初始化

最典型的就是矩陣乘法

struct ljj{int a[101][101];friend ljj operator * (ljj a1,ljj a2){ljj c;for(register int i=1;i<=100;++i)for(register int j=1;j<=100;++j){c.a[i][j]=0;for(register int k=1;k<=100;++k)c.a[i][j]+=a1.a[i][k]*a2.a[k][j];}} }; View Code

七.排序

動態(tài)維護的用堆或者平衡樹

靜態(tài)可以sort，歸并并不推薦(主要是我不會···)

當然一些算法如CDQ可以邊分治邊歸并的就別sort了

sort結(jié)構(gòu)體時注意最好重載運算符，定義比較函數(shù)比較慢

值域小的桶排序

關(guān)于sort還有一個神奇操作

叫做隨機化快排

大量用sort且待排序的數(shù)比較多得話可以考慮一下，因為直接用庫函數(shù)容易棧溢出

順帶一提，隨機化快排對有序數(shù)列的排序比普通快排快上個幾百倍

說白了就是隨機化快排不容易被特殊數(shù)據(jù)卡

再說白了就是能多騙點分…

#include<bits/stdc++.h> using namespace std; int a[1000001]; int random_div(int *q,int l,int r){int z=l+rand()%(r-l+1),zl=l-1,tp;swap(q[z],q[r]),tp=q[r];for(register int i=l;i<r;++i)if(q[i]<=tp)++zl,swap(q[zl],q[i]);swap(q[++zl],q[r]);return zl; } void Random_Sort(int *q,int l,int r){if(l<r){int z=random_div(q,l,r);Random_Sort(q,l,z-1);Random_Sort(q,z+1,r);}return ; } int ran(int x){return (long long)rand()*rand()%x; } int main(){srand(time(NULL));int n;scanf("%d",&n);for(register int i=1;i<=n;++i)scanf("%d",&a[i]);Random_Sort(a,1,n);for(register int i=1;i<=n;++i)printf("%d ",a[i]);puts("");return 0; } View Code

當然實在不會打（比如我）只在sort前加個random_shuffle有時候也會讓sort飛快（也有可能讓你T飛）

八.頭文件

慎用！！！！！！！！

#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks")
這個的最大用處是：當你用上這些還TLE時，你程序已經(jīng)沒救了。

九.其他

其實這里才是精華

inline和register盡量用

注意inline不要在遞歸函數(shù)里用

register不要在遞歸過程中用，回溯時可以用

自加自減運算符前置，就是i++改成++i

內(nèi)存允許且不需memset時bool改int

能int絕對不要用long long（一哥們數(shù)顏色（洛谷上兔子那個，不是帶修莫隊）調(diào)了一下午一直TLE，我把他long long改成int就A了……）

如果方便可以循環(huán)展開，偶爾有奇效

if-else能改就改成三目運算符？：

邊權(quán)為1的圖跑最短路用bfs別用dijkstra

(一個名叫Journeys的題的暴力bfs比dijstra高10分···)

多維數(shù)組順序按for循環(huán)來！！！

eg. CodeForces 372CWatching Fireworks is fun

dp[N][M]與dp[M][N]一個TLE60，一個AC

其實就是內(nèi)存訪問的連續(xù)性，一直跳躍著訪問內(nèi)存自然慢

數(shù)組維數(shù)越少越好

離散化可以利用pair記錄下標，映射時更加方便，不用再lower_bound了

還有一個玄學(xué)操作叫做卡時

就是你打了個dfs，里面用clock()判斷運行時間

快TLE的時候直接輸出當前答案

注意clock()返回的時間不是特別準

別把跳出時間定的太極端

還有注意Linux下1e6是一秒，想象一下跳出時間設(shè)成1000的酸爽

完結(jié)撒花~~

轉(zhuǎn)載于:https://www.cnblogs.com/remarkable/p/11216246.html

總結(jié)

以上是生活随笔為你收集整理的常数优化的一些技巧的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。