ACM竞赛技巧总结

目录1.更快（最快）的读入优化2.memset用来赋最大值（非0，-1）3.错排公式4. 圆周率5.自然对数6.浮点数比较时最好控制精度7.判断是不是2的幂8.lowbit函数 ：9.Runtime Error10.除vector和string以外的STL都不支持*（it+1）的访问形式11.位运算的妙用12.运用fill函数给任意容器赋任意值（1）给二维数组赋值（2）其他容器 1.更快（最快）的读入优化 struct ios { inline char gc(){ static const int IN_LEN=1<<18|1; static char buf[IN_LEN],*s,*t; return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++; } template inline ios & operator >> (_Tp&x){ static char ch,sgn; ch = gc(), sgn = 0; for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';} for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0'); sgn&&(x=-x); return *this; } } io; int main(){io>>a>>b;}

需要注意的是，一旦用了这个读入优化之后，scanf，getchar什么的都不能用了！

2.memset用来赋最大值（非0，-1）

注意：
memset(dis,0x7f,sizeof dis);
dis[0][0]=0x7f7f7f7f
但是dis必须是int型的

3.错排公式

错排公式D(n) = (n-1) [D(n-2) + D(n-1)]，特殊地，D(1) = 0, D(2) = 1.

4. 圆周率

圆周率=acos(-1.0)

5.自然对数

自然对数=exp(1.0)

6.浮点数比较时最好控制精度 #define eps 1e-6 fabs(a-b)<eps 7.判断是不是2的幂 x > 0 ? ( x & (x - 1)) == 0 : false 8.lowbit函数 ： return x & (-x) 9.Runtime Error

指你的程序发生了运行时错误。可能是由于内存访问违规（数组下标越界也包括运行时下标为负数的情况）、除0等运行时问题,不是超时！！

10.除vector和string以外的STL都不支持*（it+1）的访问形式 11.位运算的妙用

a&1 ⟹⟹⟹相当于a%2==1(判断奇偶性)；

a^b ⟹⟹⟹相当于a!=b(判断a，b是否相等）

1<<n ⟹⟹⟹ 2n

12.运用fill函数给任意容器赋任意值 （1）给二维数组赋值

fill(f[0], f[0]+N*N, k);
其中k就是要填充的值。

（2）其他容器
作者：繁凡さん

技巧 acm