常数优化技巧

今天让我们整理一下一些常数优化技巧：

1. 读入优化：

#define sight(c) ('0'<=c&&c<='9')
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}<br />//使用方法 read(x);

这是一直基于getchar的快速读入。相比大家都会，不说了。

2.更快的读入优化：

#define getchar nc
#define sight(c) ('0'<=c&&c<='9')
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}

我们用buf数组把所有的输入都读入到buf数组里，还要快。（此后便不能用scanf和cin了，因为输入在buf数组里了）

3.如果我们大抵知道数据输入规模，我们可以这样写nc函数：

#define nc *p1++
char *p1=buf
fread(stdin,buf,1,100000);//主程序里加这句话

4.同理，我们有输出优化：

void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }

要用的时候调用writeln。（在写write函数的时候要少写判断。）

5.不要信仰STL的常数（sort除外）。

#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b

必要的时候一定要手写（尤其是bitset，queue，stack）。

such as bitset。

struct bitsets{
    long long t[4];
    void set(int x){
        int aa,bb;
        aa=x/60;bb=x%60;
        this->t[aa]|=1LL<<bb;
    }
    void reset(){
        this->t[0]=0;
        this->t[1]=0;
        this->t[2]=0;
        this->t[3]=0;
    }
    void ad(const bitsets &g){
        this->t[0]&=g.t[0];
        this->t[1]&=g.t[1];
        this->t[2]&=g.t[2];
        this->t[3]&=g.t[3];
    }
    void oo(const bitsets &g){
        this->t[0]|=g.t[0];
        this->t[1]|=g.t[1];
        this->t[2]|=g.t[2];
        this->t[3]|=g.t[3];
    }
    void xo(const bitsets &g){
        this->t[0]^=g.t[0];
        this->t[1]^=g.t[1];
        this->t[2]^=g.t[2];
        this->t[3]^=g.t[3];
    }
    bool tr(const bitsets &g){
        bool top=true;
        top&=((this->t[0]&g.t[0])==0);
        top&=((this->t[1]&g.t[1])==0);
        top&=((this->t[2]&g.t[2])==0);
        top&=((this->t[3]&g.t[3])==0);
        return top;
    }
};

6.大规模的函数参数调用最好引用（&）

比如这样：

void X(int &x){
}

7.我们要学会手开O2

#define MARICLE __attribute__((optimize("-O2")))

那么我们就可以在要开O2的函数过程前加MARICLE 。

8.Ox优化并不是越高越好：

我们发现Ox类的优化是有代价的。我们发现开着O类优化我们无法调试。

-O1 提供基础级别的优化

-O2提供更加高级的代码优化,会占用更长的编译时间

-O3提供最高级的代码优化

此外我们发现O3优化是以缩小栈空间为代价的，所以有递归的程序O2优化就够了，O3会更慢。

9.循环优化：

for (i=;i<=b;i++)

这样写是很慢的。

for (int i=;i<=b;i++)

这样写要快那么一丢丢，因为在循环体里面定义，编译器会把变量放到寄存器里，这样会更快。

for (int i=b;i;i--) //i从b到1
for (int i=b;~i;i--)//i从b到0

这样子更快。因为是位运算。

10.枚举子集。

for (int i=;i<siz;i++)
  for (int j=i;j;j=(j-)&i)
   f[i]=.....

这样子写是O（3^n）的，比常规枚举要快。

11.相同语句下，从速度上讲，宏>重载运算符>函数。

12.没有递归的程序前可以加inline，这样更快。

inline void X(int &x){
}

就是这样子。