Part 0 时间复杂度常数优化的意义
在科学研究意义上，时间复杂度的常数优化并不是十分重要的。
但在信息学竞赛中，同样的复杂度为$O(n^2)$的程序，对于一组 $n=5000$ 的数据，有的可能常数为20，需要运行1000ms，有的可能常数为5，需要运行500ms。
这样，两个看似相同的算法，一个超时错误，一个正确得分。
同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同，执行起来效率也会有所不同。
当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。
Part 1 基本运算
众所周知，除法和取模运算的运行时间相对赋值、比较、加、减、乘运算要慢得多，而由于计算机内部的原因，位运算的速度是最快的。
因此，我们应当尽可能用速度较快的运算代替速度慢的运算。
位压缩的技巧：
读取第 k 位： a >> k & 1
读取第 k 位并取反： ~a >> k & 1
将第 k 位清 0： a &= ~(1 << k)
将第 k 位置 1： a |= 1 << k
将第 k 位取反： a ^= 1 << k
将第 k1~k2 位反转： a ^= ((1 << (k2 - k1 + 1)) - 1) << k2
是否恰好只有一个 true： !(x & (x - 1)) && x
判断是否有两个相邻的 true： x >> 1 & x
是否有三个相邻的 true： x >> 1 & x >> 2 & x特殊运算：
乘除2的整数幂
x*(2^k)=x<<k
x/(2^k)=x>>k
乘除常数的优化
x*10=(x<<1)+(x<<3)
x*13=x+(x+(x<<1)<<2)
x*14=(x<<1)+(x+(x<<1)<<2)
x*17=(x<<4)+x
x*63=(x<<6)-x
对2^k取模优化
x%(1<<k)=x&(1<<k)-1位运算代替四则运算：
int add(int a, int b) {
if (b == 0)
return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return add(sum, carry);
} //加法
int negative(int a) {
return add(~a, 1);
} //取补码
int sub(int a, int b) {
return add(a, negative(b));
} //减法
int mul(int a, int b) {
int ans = 0;
while (b) {
if (b & 1) //b最后一位是否为1
ans = add(ans, a);
a <<= 1;
b >>= 1;
}
return ans;
} //正数乘法
int div(int x, int y) {
int ans = 0;
for (int i = 31; i >= 0; i--) {
//比较x是否大于y的(1<<i)次方，避免将x与(y<<i)比较，因为不确定y的(1<<i)次方是否溢出
if ((x >> i) >= y) {
ans += (1 << i);
x -= (y << i);
}
}
return ans;
} //除法对于取模的优化：
可以将其优化为：
inline int MOD(int x) { return x < Mod ? x : x % Mod; }而对于某些题目，仅需要对答案取模。这类题目要边运算边取模的目的一般是防止溢出。
故我们甚至可以写成这样：
inline int MOD(int x) { return x <= 0x3f3f3f3f ? x : x % Mod; }如果是乘法，我们相应地可以写成：
inline int MOD(int x) { return x <= 45000 ? x : x % Mod; }总之，这个范围要保证结果在计算时不会有溢出的风险。但采用了这种方式后，最后输出时一定要取模。
对于负数取模的优化：
inline int MODF(int x) {
x = MOD(x);
return x < 0 ? x + MOD : x;
}Part 2 内存优化
内存的访问是非常慢的，除了内存，还有寄存器(register)、高速缓存(cache)，它们的访问速度比内存更快。
register循环：
寄存器具有最高的访问速度，在变量前加关键词register即将其加入寄存器。但寄存器的空间是有限的，不应该滥用register，应该仅在访问最频繁的几个变量（如循环变量）前加register。
for(register int i = 0; i < n; i++)让某个数组的大小能够卡进cache
cache即高速缓存，一般分为3级（有些电脑为2级），访问速度逐级递减。访问变量时，CPU会优先在cache而不是内存中查找，如果cache中不存在此变量，则会进入内存查找，这称为cache miss。
与register一样，cache的大小同样有限。一些过大的内存是不可以进入cache的。
基数排序时，以256为基数会比256*256更快。因为256大小的四个数组可以轻松进入cache。
保证时空局部性
时间局部性：当一个变量被使用时，它会在短时间内再次被使用。
空间局部性：当一个变量被使用时，它的内存附近的变量会再次被使用。
保证这两样东西的良好有益于减少cache miss。
怎样优化空间局部性？
- 将一些关系密切，例如经常连着使用的变量尽量定义在一起，或用结构体封装起来。
- 适当调整变量定义顺序
- 保证内存连续访问。例如：Floyd和矩阵乘法的程序中，将第三层循环作为第一层会大大提高速度。
怎样优化时间局部性？
- 尽量使用局部变量。因为堆栈的数据访问十分频繁。
Part 3 I\O优化
C++为了兼容性导致cin、cout极慢，对于大量数据的读入和输出往往不堪重负。这个时候使用读入优化、输出优化可以节省数倍的时间。
简单使用可以用scanf和printf代替cin和cout。
基本读入优化
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}fread优化
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;基本输出优化
其实没有printf快
char F[200];
inline void write(int x) {
int tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}fwrite优化
不会ing
留坑待填(逃
