一.STL
原则上手写要比用STL快，不过有些确实难打···
map和set直接用就好，都是基于红黑树实现（根本不会打），效率已经足够高
不过当然能用数组就别用map
优先队列可以考虑手写，不过大部分情况直接用就行
至于stack和queue，那就是必须手写的
vector内存允许的话直接开2维数组
注意stack打法，do-while循环特别帅!!!
1 #include<iostream> 2 using namespace std; 3 int stack[1000],top; 4 int main(){ 5 int n; 6 cin>>n; 7 stack[top++]=n; 8 do{ 9 cout<<stack[--top]<<" "; 10 }while(top); 11 return 0; 12 }
二.运算
mod定义成const
能乘不除，能加减别用魔法模法
能位运算就别用加减乘除···
x2^n改成<<n
/2^n改成>>n
swap(x,y)改成x^=y^=x^=y
模数若为2^n可以直接&(mod-1)
也可以先开unsigned int最后取模
两个小于模数相加用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; }
数据范围不大可以开long long，中间不取模最后再取
判断奇偶&1
!=直接改成^
三.读入
别用cin，用cin就在主函数加：
ios::sync_with_stdio(false);
cin.tie(0);
打着还麻烦，所以就用scanf或快读
不超过1e5的数据scanf即可
再大了最好用快读
记得位运算优化···
还嫌慢上fread
快读还有一些妙用
比如定义常量不能scanf但可用快读赋值
这在一些读取模数的题目中很有用
下面代码里快读读的是非负整数，读整数特判一下有无‘-’即可，就不给出实现了
#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; }
四.输出
同理，用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; }
五.dp
其实已经不算卡常了···
1.排除冗杂
能不dp的就别dp
说白了就是for循环里设个限制条件
比如可怜与超市一题
yzh巨佬重设了个tmp数组实现n^2转移，还证明了一波复杂度，%%%
但其实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; } }
2.等效替代
说起来很模糊···
以HAOI2015树上染色为例
染黑点和染白点其实一样
所以你完全可以加一句k=min(k,n-k);
六.初始化
单个变量可以直接初始化，好像比赋值初始化略快
大范围初始化直接memset
memset就是比for循环要快，不要怀疑！！！
当然一些情况你完全可以边for边初始化
最典型的就是矩阵乘法
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]; } } };
七.排序
动态维护的用堆或者平衡树
静态可以sort，归并并不推荐(主要是我不会···)
sort结构体时注意最好重载运算符，定义比较函数比较慢
值域小的桶排序
关于sort还有一个神奇操作
叫做随机化快排
大量用sort且待排序的数比较多得话可以考虑一下
顺带一提，随机化快排对有序数列的排序比普通快排快上个几百倍
说白了就是随机化快排不容易被特殊数据卡
再说白了就是能多骗点分…
八.其他
其实这里才是精华
inline和register尽量用
注意inline不要在递归函数里用
register不要在递归过程中用，回溯时可以用
自加自减运算符前置，就是i++改成++i
内存允许且不需memset时bool改int
如果方便可以循环展开
if-else能改就改成三目运算符？：
能用dfs就别用bfs
边权为1的图跑最短路用bfs别用dijkstra
(一个名叫Journeys的题的暴力bfs比dijstra高10分···)
多维数组顺序按for循环来！！！
eg. CodeForces 372CWatching Fireworks is fun
dp[N][M]与dp[M][N]一个TLE60，一个AC
数组维数越少越好
离散化可以利用pair记录下标，映射时更加方便，不用再lower_bound了
还有一个玄学操作叫做卡时
就是你打了个dfs，里面用clock()判断运行时间
快TLE的时候直接输出当前答案
注意clock()返回的时间不是特别准
别把跳出时间定的太极端
还有注意Linux下1e6是一秒，想象一下跳出时间设成1000的酸爽
完结撒花~~
原文：https://www.cnblogs.com/remarkable/p/11216246.html
