今天让我们整理一下一些常数优化技巧：
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; }
//使用方法 read(x);
这是一直基于getchar的快速读入。相比大家都会，不说了。
2.更快的读入优化：
#define getchar nc #define sight(c) ('0'<=c&&c<='9') inline char nc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,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(' '); }
要用的时候调用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 。
或者在宏中定义以下宏
#pragma GCC optimize("-O2")
8.Ox优化并不是越高越好：
我们发现Ox类的优化是有代价的。我们发现开着O类优化我们无法调试。
-O1 提供基础级别的优化
-O2提供更加高级的代码优化,会占用更长的编译时间
-O3提供最高级的代码优化
此外我们发现O3优化是以缩小栈空间为代价的，所以有递归的程序O2优化就够了，O3会更慢。
9.循环优化：
for (i=1;i<=b;i++)
这样写是很慢的。
for (int i=1;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=0;i<siz;i++) for (int j=i;j;j=(j-1)&i) f[i]=.....
这样子写是O（3^n）的，比常规枚举要快。
11.相同语句下，从速度上讲，宏>重载运算符>函数。
12.没有递归的程序前可以加inline，这样更快。
inline void X(int &x){ }
就是这样子。
13.我们可以这样子用位运算来加速逻辑判断：
if (a^b) 等价于 if (a!=b) if (!(a^b)) 等价于 if (a==b)
最后声明，其实在Os优化中，这些优化差不多都有，其实然并软。
好吧，我知道我写的很没有营养。还是举个栗子吧。
{以下测试都在一台配置如下的机子中：
CPU： intel i3-6100 3.7GHZ
RAM： 4.00GB
64 位操作系统
}
随便写了个程序 ：
#include<bits/stdc++.h> using namespace std; int n,a[300007],ans; int gcd(int x,int y){ return y?gcd(y,x%y):x; } signed main () { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) ans=max(ans,gcd(a[i],a[j])); printf("%d ",ans); }
然后造了一个2W数据规模的数据。 运行了38.85s.
在其上方加入以下指令：
#pragma GCC optimize("-O2") 28.48s
在编译器中加入O2优化指令： 28.22s
//以下操作都在O2的基础上
在gcd函数前加入inline 指令 28.5s （大概是系统忽视了inline ，因为递归的函数加inline讲道理会很假）
我们强制内联 ：加入 __attribute__((always_inline)) 28.49s。
把递归改成迭代：
#pragma GCC optimize("-O2") #include<bits/stdc++.h> using namespace std; int n,a[300007],ans,t; int gcd(int x,int y){ while (y) { t=x; x=y; y=t%x; } return x; } signed main () { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) ans=max(ans,gcd(a[i],a[j])); printf("%d ",ans); }
结果并没有快多少，应该是O2自动把gcd展开了吧。
#pragma GCC optimize("-O2") #include<bits/stdc++.h> using namespace std; int n,a[300007],ans,t; #define getchar nc #define sight(x) ('0'<=x&&x<='9') inline char nc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,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; } 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(' '); } inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } inline int gcd(int x,int y){ while (y) { t=x; x=y; y=t%x; } return x; } int p[13],ed,c[300007],pppp; signed main () { freopen("a.in","r",stdin); read(n); for (int i=1;i<=n;i++) read(a[i]); for (int i=n;i;--i) { ed=8; for (int j=1;ed<i;j+=8,ed+=8){ p[0]=gcd(a[i-j],a[j]); c[j]>p[0]?:c[j]=p[0]; p[1]=gcd(a[i-j-1],a[j+1]); c[j+1]>p[1]?:c[j+1]=p[1]; p[2]=gcd(a[i-j-2],a[j+2]); c[j+2]>p[2]?:c[j+2]=p[2]; p[3]=gcd(a[i-j-3],a[j+3]); c[j+3]>p[3]?:c[j+3]=p[3]; p[4]=gcd(a[i-j-4],a[j+4]); c[j+4]>p[4]?:c[j+4]=p[4]; p[5]=gcd(a[i-j-5],a[j+5]); c[j+5]>p[5]?:c[j+5]=p[5]; p[6]=gcd(a[i-j-6],a[j+6]); c[j+6]>p[6]?:c[j+6]=p[6]; p[7]=gcd(a[i-j-7],a[j+7]); c[j+7]>p[7]?:c[j+7]=p[7]; } for (int j=ed-7;j<i;++j){ pppp=gcd(a[i],a[j]); c[j]>pppp?:c[j]=pppp;} } for (int i=n;i;--i) ans>c[i]?:ans=c[i]; printf("%d ",ans); }
循环展开，但不知道为什么，并没有快。
应该是gcd太大了吧，反正循环展开就是这样的。