常数优化与底层优化的小技巧
扯淡
常数优化：
#1
常数优化一直是OI中存在的问题。很多知名选手轻松想出了正解，或者不知名选手（如鄙人）绞尽脑汁终于想出了正解，结果出题人用(Sang)心(xin)良(Bing)苦(Kuang)卡常让本应该得到的分数丢失。
这是一种值(Ying)得(Gai)推(Bei)广(Biao)的行为，考查OIer的综合素质。不过本蒟认为，OI本应该考察的核心应该是算法而不是编程技巧。但是为了对付这样高(Wu)明(Liao)的出题人，我们需要一些小小的卡常技巧。
另一个问题是在，想出了一个稍差的解法，如一个O(nlog^3n)的解法。然而标程是O(nlog^2n)。那么我们就需要使用一些卡常的技巧，拿到更高的分数。
#2
就算写出了标算，却由于常数巨大跑不过暴力。所谓标算与暴力的区别就在于通过计算次数的减少而实现时间的缩短。如果一个算法速度比不上某些所谓的暴力，那么这个算法也不好意思称当所谓的标程。
底层优化：
WC2017过后，底层优化真正进入了广大OIer的视野，见证了理论复杂度在底层优化面前的飘渺虚无。“n方过百万，暴力踩标程”不再是一纸空谈。
大概是湖(O)南(I)省(Sheng)选(Ya)前的最后一篇文章了吧。
>>>>>>先介绍一些小技巧
顺序寻址
操作：
很简单，就是按照顺序寻找地址。
原理：
顺序寻址加速程序的原理只是在于多了很多缓存(cache)来帮助访问。
实例：
差别比我想象中的大很多。本蒟尝试使用了随机寻址进行比较。
随机生成一个长度为n的数组。遍历这个数组的元素，并求和。
我们看下面这份代码：
T=-clock();
for(i=1; i<=n; i++)S+=A[H[i]];
printf("%lld\n",S);
T+=clock();
fprintf(stderr,"%.2lfms\n",T);
唯一影响访问速度的在于A[H[i]]这一部分。如果H[i]=i，就是我们所说的顺序遍历，如果H[i]是一个随机排列，那么就相当于我们的随机遍历。
那么用以下代码生成H[i]：
int randx(int x) {
return rand()*rand()%x+1;//Windows xp
}
for(i=1; i<=n; i++) H[i]=i;
for(i=1; i<=n; i++) {
u=randx(n);
v=randx(n);
swap(H[u],H[v]);
}
如果是顺序遍历，则将下面的部分删去。
运行代码之后。
当n=1e7时，顺序遍历为32ms，随机遍历是157ms。
当n=7e7的时候，顺序遍历为187ms，随机遍历是1015ms。
可见缓存可以实现高速遍历（相对于随机顺序）。
但是顺序访问与逆序访问，速度是差不多的，不会对缓存造成若干影响。
运用：
当我们在一些枚举的时候，连续的指针会积累缓存，比跳动的指针速度快。
所以当我们需要卡常的时候，尽量修改跳动的指针为连续的指针。
register
操作：
其实就是在int前面加一个register。
比方说下面两个代码：
for(int i=1; i<=n; i++) H[i]=i;
以及
for(register int i=1; i<=n; i++) H[i]=i;
原理：
据说这个玩意仅仅是在C++98 -O1的环境下有用。就目前的g++版本看来，似乎是用处不大了，本蒟就不再深究了。
听说在下一/两代的C++可能会取消register用法了。
（当然也是听说而已：https://zhidao.baidu.com/question/72189676.html）
inline
操作：
在过程与函数前面加上inline。
比方说下面的代码：
int C[200010];
void Change(int p,int w) {
for(; p<=maxn; p+=p&-p)C[p]+=w;
}
以及
int C[200010];
inline void Change(int p,int w) {
for(; p<=maxn; p+=p&-p)C[p]+=w;
}
原理：
inline使得函数与过程主程序内联（可能说法不太准确）。那么编译器做的事情就是把整个函数/过程直接放到主代码中。
如果过程中有for或者递归，编译器会自动拓展一些深度。
加速程序，在于减少了 反复频繁调用一些过程，指针的跃动的时间消耗。
运用：
xehoth大佬和我说，他的所有的过程和函数都是加了内联inline。
（在之前我也是这样，曾经有一段时间我也是inline党，后来由于Pb大佬说这样不好。据说是由于代码长度过长而使得inline缓慢）
也曾经有过一些不加"inline"就AC的经历。不过后来找不到代码了。
本蒟认为，代码短的加上inline还是可以加速的。代码巨大的过程/函数，还是暂且不要inline好了。
三目运算符
操作：
这是一种代替if的语言。
比方说下面的代码：
void Splay(int p) {
for(f=Fa[p],gf=Fa[f]; Fa[p]&&Fa[f]; rot(p),f=Fa[p],gf=Fa[f])
if((Btr[gf].s[0]!=f)^(Btr[f].s[0]!=p))rot(f);else rot(p);
if(Fa[p])rot(p); root=p;
}
以及
void Splay(int p) {
for(f=Fa[p],gf=Fa[f]; Fa[p]&&Fa[f]; rot(p),f=Fa[p],gf=Fa[f])
rot((Btr[gf].s[0]!=f)^(Btr[f].s[0]!=p)?p:f);
if(Fa[p])rot(p); root=p;
}
原理：
在if分支条件语句中，如果值为true，那么执行速度很快。如果值为false，那么执行速度很慢。三目运算符均衡了两种情况。
在O2的状况下，优化较为明显。
实例：
众所周知，NTT跑得没有FFT快，瓶颈在于多次取模
我们看一份NTT的核心代码：
for(vk=1,h=2; h<=len; vk++,h<<=1) {
for(vi=0; vi<len; vi+=h) {
int vt;
vl=(h>>1);
for(vj=0; vj<vl; vj++) {
vt=mul_mod(vw[vj][vk],Po[vi+vj+vl]);
Po[vi+vj+vl]=Po[vi+vj]-vt; if(Po[vi+vj+vl]<0)Po[vi+vj+vl]+=intp;
Po[vi+vj]=Po[vi+vj]+vt; if(Po[vi+vj]>=intp)Po[vi+vj]-=intp;
}
}
}
上述代码中，if分支语句是对多次取模的优化。但是分支语句还是太慢了。做一次1e5的次NTT大约需要94ms。
for(vk=1,h=2; h<=len; vk++,h<<=1) {
for(vi=0; vi<len; vi+=h) {
int vt;
vl=(h>>1);
for(vj=0; vj<vl; vj++) {
vt=mul_mod(vw[vj][vk],Po[vi+vj+vl]);
Po[vi+vj+vl]=Po[vi+vj]-vt; Po[vi+vj+vl]+=(Po[vi+vj+vl]>=0?0:intp);
Po[vi+vj]=Po[vi+vj]+vt; Po[vi+vj]-=(Po[vi+vj]>=intp?intp:0);
}
}
}
调整到上面这份代码之后，速度大增。“if-minus（减法）”比“mod”要快，在于模运算的O(6)常数。而“-?-:-（三目运算符）”比“if-minus”快则是在条件分支语句上的优化。
上述代码做一次NTT大约需要64ms。
循环展开
操作：
就是把一些循环展开来写。
比方说：
for(vi=0; vi<nowlen; vi++)Po[vi]=x.Po[vi];
以及
for(vi=0; vi<tmp; vi+=4) {
Po[vi]=x.Po[vi];
Po[vi+1]=x.Po[vi+1];
Po[vi+2]=x.Po[vi+2];
Po[vi+3]=x.Po[vi+3];
}
for(; vi<tmp; vi++)Po[vi]=x.Po[vi];
原理：
一般是利用寄存器，一次处理较多元素。比方说上述代码，寄存器一次处理了4个元素。
那么，按照松爷的课件来说，寄存器1次处理4个元素的时钟周期比4次处理1个元素的时钟周期短一些。那么理论上事实上减少了处理的时钟周期，使得时间减少。
扯淡一下：
上面写法还有缺陷。加法计算次数较多。一般我们用循环展开都是去跑1e9+的程序了，所以能在for中少一次 运算 都是很有效果的。
（然而如果仅仅为了处理1e5的运算，并没有很大效果）
所以我们可以参考松爷的程序，用4个变量记录指针，并每次移动4个指针。直观上比6次加法要好。
运用：
常常在数组的初始化中使用。虽然我们也不必处理1e9+的数组（自然也开不了这么大）
然而for多次，消耗的时间又回来了/手动滑稽
所以在一般的卡常（也就是前者——依靠理论复杂度的运算）中，这玩意用处并不是很大。当然如果你是准备在后者情况下卡常，想“n方过百万，暴力踩标程”。那么这也是有那么一点用的。
注意：
不要盲目展开！
如果展开层数较多，导致寄存器溢出，效率也会变慢。
扯淡一下：
Q:如何看寄存器有没有溢出？
拿Dev_cpp举例子。在调试的时候，左下角有一个“CPU窗口”的选项，点击查看：
弹出这个RE的时候常常会弹出的窗口。
右边“Register”一栏中，如果有很多一样的数字，比方说全是0x77c2fc80的，那么说明寄存器可能溢出了。
下面的SS/DS/ES常常会相同，不必把它们作为指标。
xehoth告诉我了这几个玩意的意义，不过感觉不重要，就不细细描述了。
高维寻址
操作：
计算出最后一维的指针遍历。
比方说：
T=-clock();
for(a=1; a<=n; a++)
for(b=1; b<=n; b++)
for(c=1; c<=n; c++)
for(d=1; d<=n; d++)
for(e=1; e<=n; e++)S+=F[a][b][c][d][e];
T+=clock();
以及
T=-clock();
for(a=1; a<=n; a++)
for(b=1; b<=n; b++)
for(c=1; c<=n; c++)
for(d=1; d<=n; d++) {
p=*F[a][b][c][d];//用一个指针直接计算出位置
for(e=1; e<=n; e++)S+=*(F[a][b][c][d]+p);
}
T+=clock();
原理：
给出一个高维数组F[47][47][47][47][47]。在这玩意里面寻址，事实上是要用到乘法的。所以速度较慢。
比方说要寻找F[5][4][3][2][1]，那么事实上指针会在5*47^4+4*47^3+3*47^2+2*47+1的地方。看着那个指针的位置就觉得很慢。
所以我们直接计算出底维的指针，然后就可以避免/减少部分乘法寻址了。
扯淡一下：
在高维数组中，数据的存放方式大概是这样（下面以二维数组为例）：
实例：
效果比我想象中的要惊人。
就拿上面的代码来举例子。得到数组之后，那两个程序运行了一下。
结果第一个代码计时为141ms，第二份代码计时为62ms。
注意：
在使用这个技巧的时候，需要用变量记录指针的位置。访问这个变量也是需要指针的跳动来消耗时间的。
总而言之一句话，“精细实现程序”（逃）
维度大小差异
操作：
这里分为两个内容：
先枚举维度范围广的
将维度更大的放在尽量靠前的维度
第一部分的意思，我们可以参考我们在做矩阵乘法的常识（“常识”一词是xehoth大佬说的，然而我恍然大悟——原来这是常识）：
我们先枚举i，再枚举k，最后枚举j。这样比先枚举k，之后枚举i，最后枚举j的速度快。（如果这是常识的话）想必大家已经熟悉通透了。
也就是说，如果给出一个高维数组F[x][y][z]，用3个for遍历一遍。那么先for(a=1;a<=x;a++)，比先for(b=1;b<=y;b++)或者for(c=1;c<=z;c++)快速一些。
第二部分的意思可以举例说明：
如果我们需要一个DP数组F[2][2][3][4000]。我们应该在保证正确的前提下，把数组变为F[4000][3][2][2]，然后按照第一部分的方法遍历。
原理：
把访问量越大的尽量放在前面枚举。
指针的跃动距离会少一些。
运用：
矩阵乘法就是一个生动形象的例子。
>>>>>>一些比较有效的常数优化/底层优化
CPU并发
扯淡一下：
此技巧十分强大。
再搬出这句话，“n方过百万，暴力踩标程”。
当然了，这也是夸张手法。正如介绍莫队的那一句话，“传说中可以解决一切区间问题的莫队算法”，事实上只是“传说中”而已……
但是这至少说明了描述的这玩意的一个特征。莫队十分强大。CPU并发，也十分强大。
操作：
把简单操作写在一起。常常与循环展开搭配使用。
切记切记，CPU并发不是循环展开。CPU并发是把大量简单运算写在一句话中，只是搭配使用效果极佳。
一般代码长成这鬼样子：
for(i=1; i<=n; i++) {
tmpj=A[i]-1-23;
for(j=1; j<=tmpj; j+=24) {
ans+=(*(Bu+j)+*(Bu+j+1)+*(Bu+j+2))+(*(Bu+j+3)+*(Bu+j+4)+*(Bu+j+5))+(*(Bu+j+6)+*(Bu+j+7)+*(Bu+j+8))+
(*(Bu+j+9)+*(Bu+j+10)+*(Bu+j+11))+(*(Bu+j+12)+*(Bu+j+13)+*(Bu+j+14))+*(Bu+j+15)+
(*(Bu+j+16)+*(Bu+j+17)+*(Bu+j+18))+(*(Bu+j+19)+*(Bu+j+20)+*(Bu+j+21))+(*(Bu+j+22)+*(Bu+j+23));
}
tmpj+=23;
for(; j<=tmpj; j++)ans+=*(Bu+j);
Bu[A[i]]++;
}
随便搬了一个CPU并发的代码……
Q:这玩意和普通的循环展开有啥区别？
原理：
CPU并发加速的原理在于刺激CPU，然后使得CPU高速运行。
（真简单的理由，liaoy是不是在扯淡？）
其实优化重点在于计算一个数字的时候需要枚举大量其他数字，并通过简单运算实现。
条件：
答案可以通过大量简单运算实现。
观察到寄存器不会溢出。
实例：
#1 BZOJ_3509/codechef_COUNTARI
题目大意：
找有多少个三元组(Ai,Aj,Ak)，满足2Aj=Ai+Ak
个人解法：
这是一道很经典的CPU并发练习题。（明明是分块+FFT 逃）
一种O(n^2)的办法是维护两个桶。初始状态下，第一个桶B1是满的，第二个桶B2是空的。
然后顺序遍历每一个元素：
B2[A[i]]--
之后枚举前面的一个数字x，拿的B1[x]*B2[2A[i]-x]来更新答案。
B1[A[i]]++
这个做法显然O(nmax(w))。
但是在CPU并发下：
for(i=1; i<=n; i++) {
B2[A[i]]--;
for(j=1,k=(A[i]<<1)-1; k>=14;) {
ans+=B1[j]*B2[k]+B1[j+1]*B2[k-1]+B1[j+2]*B2[k-2]+B1[j+3]*B2[k-3]+
B1[j+4]*B2[k-4]+B1[j+5]*B2[k-5]+B1[j+6]*B2[k-6]+B1[j+7]*B2[k-7]+
B1[j+8]*B2[k-8]+B1[j+9]*B2[k-9]+B1[j+10]*B2[k-10]+B1[j+11]*B2[k-11]+
B1[j+12]*B2[k-12]+B1[j+13]*B2[k-13];
j+=14; k-=14;
}
for(; k>=1;) {
ans+=B1[j]*B2[k]; j++; k--;
}
B1[A[i]]++;
}
printf("%lld\n",ans);
这份代码可以AC，codechef上1800ms。
xehoth使用CPU并发在BZOJ与codechef拿下Rank1，codechef仅需0.64s。
上面一题便是更新答案的时候大量简单运算。
#2 codevs_1080/codevs_1081
个人解法：
题目大意：
codevs_1080:
给出一个长度为n的序列，要求支持：
A[p]+=w
Ask A[l..r]
codevs_1081:
给出一个长度为n的序列，要求支持：
A[l..r]+=w
Ask A[p]
个人解法：
显然这是线段树/树状数组的模板题。看到这篇文章的大佬们应该早就烂熟于心了。
考虑暴力。
这里需要将codevs_1081转换一下。将数组差分，变为单点修改与前缀查询（相信看到这篇文章的大佬们对这套理论也是烂熟于心，不再赘述）
单点修改我们就直接修改。区间查询我们就扫一遍计算：
for(i=1; i<=m; i++) {
read(opt); read(x); read(y);
if(opt==1) {
A[x]+=y;
} else {
sum=0; tmpy=y-15;
for(j=x; j<=tmpy; j+=16) {
sum+=(*(A+j)+*(A+j+1))+(*(A+j+2)+*(A+j+3))+(*(A+j+4)+*(A+j+5))+(*(A+j+6)+*(A+j+7))
+(*(A+j+8)+*(A+j+9))+(*(A+j+10)+*(A+j+11))+(*(A+j+12)+*(A+j+13))+(*(A+j+14)+*(A+j+15));
}
for(; j<=y; j++)sum+=A[j];
printf("%d\n",sum);
}
}
注意需要时刻关注寄存器是否溢出，否则可能写了一大堆反而变得很慢。
随机数据下这份代码均可以在0.2s左右出解。codevs数据较水（我可以告诉你不用任何优化就可以AC本题，不过是用780ms+，已经有人在题解中写了）。
在使用了CPU并发之后，评测结果是147ms。优化较明显。
至于codevs_1081，数据极水，10ms即可……
扯淡一下：
Q:为什么不搬codevs_1082？
反复咀嚼使用条件：答案可以通过大量简单运算实现。
区间修改的话，我们直接维护同样需要大量枚举位置来维护，但是修改是不能一个式子解决的。
虽然存在一种转“区间修改-区间查询”为“单点修改-前缀查询”的方法（相信看到这篇文章的大佬们对这套理论也是烂熟于心，不再赘述），但是常数巨增，不再是我们这篇文章讨论的东西所需要的。
可见此操作一般/仅仅适用于单点修改/不修改的问题。
使用技巧：
搭配桶
题目大意：
给出一个长度为n的序列，求逆序对的个数。
PS:数据范围是骗人的，事实上n<=1e5。
个人解法：
一种很显然的暴力是O(n^2)枚举，假设(j<i)，那么就是判断(A[j]>A[i]?)即可。
最基本的算法是这样：
for(i=1; i<=n; i++)
for(j=1; j<=i-1; j++)
ans+=(A[j]>A[i]);
printf("%lld\n",ans);
这个代码只有20分，其余均TLE。我们可以使用CPU并发来加速。
例如下面的代码：
for(i=1; i<=n; i++) {
tmpj=i-1-15;
w=*(A+i);
for(j=1; j<=tmpj; j+=16) {
ans+=(*(A+j)>w)+((*(A+j+1)>w)+(*(A+j+2)>w))+((*(A+j+3)>w)+(*(A+j+4)>w))+((*(A+j+5)>w)+(*(A+j+6)>w))+
((*(A+j+7)>w)+(*(A+j+8)>w))+((*(A+j+9)>w)+(*(A+j+10)>w))+((*(A+j+11)>w)+(*(A+j+12)>w))+
((*(A+j+13)>w)+(*(A+j+14)>w)+(*(A+j+15)>w));
}
tmpj+=15;
for(; j<=tmpj; j++)ans+=(A[j]>A[i]);
}
printf("%lld\n",ans);
不难明白答案级别是O(long long)的。在luogu-O1的环境下拿到了50分。相比于裸的枚举的20分，有了很大进展。
但是显然这样枚举难以突破，因为答案的计算始终是一个一个累加，难以加到O(long long)级别还不超时。
我们需要一种更加高效的计算方法。也就是我们上文中提及到的桶。
这也是一个很简单的方法，我们顺序枚举，之后维护在i之前的桶，之后暴力扫描一遍这个桶。离散数字之后，时间复杂度仍然为O(n^2)。
代码大致长这鬼样：
for(i=1; i<=n; i++) {
tmpj=A[i]-1-23;
for(j=1; j<=tmpj; j+=24) {
ans+=(*(Bu+j)+*(Bu+j+1)+*(Bu+j+2))+(*(Bu+j+3)+*(Bu+j+4)+*(Bu+j+5))+(*(Bu+j+6)+*(Bu+j+7)+*(Bu+j+8))+
(*(Bu+j+9)+*(Bu+j+10)+*(Bu+j+11))+(*(Bu+j+12)+*(Bu+j+13)+*(Bu+j+14))+*(Bu+j+15)+
(*(Bu+j+16)+*(Bu+j+17)+*(Bu+j+18))+(*(Bu+j+19)+*(Bu+j+20)+*(Bu+j+21))+(*(Bu+j+22)+*(Bu+j+23));
}
tmpj+=23;
for(; j<=tmpj; j++)ans+=*(Bu+j);
Bu[A[i]]++;
}
printf("%lld\n",ans);
实际运行效果是，在luogu-O1的条件下80分。这玩意在本蒟的1e5随机数据下一般0.8-1.2s是可以出解的。
枚举部分并没有什么很大的优化。为什么这么快？
我们考虑，计算机的plus/minus/times都是需要时间的。我们自己手写计算器就可以感受到其复杂度。如果plus的对象是一个0，那么这次运算基本上消耗时间。如果是一个2^31-1，可能就需要O(32)的时间（这是针对于手写计算器而言……）。
恰好桶的性质正好是：大量位上的数字很小甚至为空，少部分位/甚至没有位的数字很大。那么事实上运算速度就会加速很大。
这就是CPU并发搭配桶的高效之处。
拒绝除法：
我们知道plus/minus/times都是需要时间的。division耗时更加长。我们具体分析一下这几个玩意：
题目大意：
计算∑{i=1~30000}∑{j=1~30000}(A[i]/B[j])
其中B[j]<=64,A[i]<=1048575
个人解法：
显然一个可以接受的标程就是把A[i]/1,A[i]/2...A[i]/64全部计算出来，之后计算B数组中有分别有多少1,2,3...64即可。
如果想使用暴力？
一个一个计算+循环展开：
for(j=1; j<=30000; j++) {
tmp=30000-5;
for(i=1; i<=tmp; i+=6) {
S+=A[i]/B[j]+A[i+1]/B[j]+A[i+2]/B[j]+A[i+3]/B[j]+A[i+4]/B[j]+A[i+5]/B[j];
}
for(; i<=30000; i++)S+=A[i]/B[j];
}
然后这个代码速度并没有之前想象的那么神。速度是一致的。
可能除法（整除）并不是我们所说的基本运算？隐隐约约记起来除法在C++形成的汇编语言中，似乎是通过“乘法+自然溢出”实现的？
总之，我们把除法这一套理论搬到CPU并发这上面就好。包括取模！！！
一只蒟蒻犯下的错误：
for(j=1; j<=30000; j++) {
tmp=30000-5;
for(i=1; i<=tmp; i+=6) {
S+=(A[i]+A[i+1]+A[i+2]+A[i+3]+A[i+4]+A[i+5])/B[j];
}
for(; i<=30000; i++)S+=A[i]/B[j];
}
本蒟忘记了是整除，上面代码是错误的。但是速度是可观的。均在580ms出解（虽然并没有什么用）
只不过是证明一下“加法+CPU并发”的速度是可观的。
小结：
这样做，CPU并发一般可以加速3-8倍不等。如果可以配套上循序枚举，再加速2-3倍，那么出现在上BZOJ_3509中“n方过百万，暴力踩标程”的情况也变得可以理解起来（好吧也就是跑过了1e9）。
如果是1e5的数据，那么O(n^2)会达到1e10，加速24倍，大概也就是5e8的样子，勉勉强强。但是如果是一般的分块/莫队+数据结构大题，大部分是5e4的数据，那么O(n^2)本来就比较小，大约2.5e9，加速24倍变为1e8显得可以接受，也许就比O(nsqrt(n)logn)的正解差不多，比O(nsqrt(n))也没有差的很远。
再强调一次：请不要尝试在1e5的数据下使用……3e4/5e4可以尝试……
不难联想到一种叫做bitset的东西，常常出现常数为1/32的玩意。这是压位的技巧。但是bitset只能够维护01的数组，而上述技巧实现了维护桶（并且还跑得飞快），是另一个方面的突破。
>>>>>>一些卡常需要注意的地方
整数解析
举一个例子：
在使用读入优化的时候，可能会使用到x=x*10这样的语句。
看到xehoth关于此的说明：
由于开了 O2，
x=x*10
会被优化为
x = x + (4 * x) // lea 一条指令搞定
x += x
一共两条指令。
整数解析的事情我们可以交给编译器来做。
然而有的同学这么写：
x = (x << 1) + (x << 3);
一共三条指令。
xehoth给出了O2下的正确姿势：
x = (x + (x << 2) << 1) + (c ^ '0');
学工程的大佬太强辣
然而我并不知道原理。大概这也是xehoth看汇编代码之后发现的？
多次计算
一个很简单的例子：
假设an与bn是一个字符数组。
for(i=0;i<strlen(an);i++)bn[i]=an[i]
以及
int lena=strlen(an);
for(i=0;i<lena;i++)bn[i]=an[i]
这是一个代码习惯问题。
感觉上我们就可以发现，上面的代码需要计算多次strlen(an)。虽然我认为不会像某文所说，退化成O(n^2)，但是我也认为这是极其慢的。
如果不愿意开新的数组，我们也可以使用下面的方法：
for(i=strlen(an)-1;i>=0;i--)bn[i]=an[i]
在之前的“顺序遍历”这一则，我们就已经知道了，数组的顺序遍历与逆序遍历，差别不会很大。
这个方法同样也运用到了若干STL中的有size函数的模板中。
对缓存友好的vector
在这里并不是要说明vector比数组快。
我们看几份代码：
for(i=0;i<A.size();i++)sum+=A[i]
以及
for(i=A.size()-1;i>=0;i--)sum+=A[i];
上面两份代码的A均为vector。
以及接下来这一份：
for(i=0;i<n;i++)sum+=A[i]
这一份代码，A为数组。
在O1环境下，vector是比较慢的。
因此第3份代码速度最快。第一份代码，需要多次计算A.size()。显然通过上面的分析，第一份代码速度不佳。
但是在O2环境下完全不同。
一者，O2环境会把A.size()的反复计算优化。我猜想应该是优化为指针。那么速度将会等同于用一个变量记录。
二者，O2环境下顺序遍历的vector堆缓存友好。速度高于逆序遍历的vector，以及数组。
所以在O2环境下，第一份代码速度最佳。
>>>>>>全文总结
卡常不能过火
如果一道题只能想出O(n^2)的暴力，那么不妨试试这些优化。
并不意味着拿到一个题，一眼过去就用暴力+卡常。
专注于算法
这只是卡常技巧。在文首就已经阐述了卡常的目的，不是为了偷懒避免对算法的深究，只是对于算法的一个优化，或者是拿到本应该拿到的分数。
偶尔可以用于帮助自己加速不那么优秀的算法。
但是作为一名OIer，更应该在算法上花功夫，而不是靠这样的“奇技淫巧”来骗分。
OIer是研究计算机领域中的算法的人。计算机科学的支柱是算法，而不是底层优化。
趋势？
趁着现在还没烂大街，抓住机会好好使用。
如果像DP那样，十多年前还是大学内容，现在小学生（特指会FFT的小学OIer）都瞧不起了。
不过总是在发展的。算法也在发展，CPU也在发展。这些技巧迟早会成为OIer必备。
虽然文首发泄了一下对“综合素质考察”的不满。不过OI向着综合素质发展，也是一件好事。
>>>>>>文末
湖(O)南(I)省(Sheng)选(Ya)前的最后一篇文章。无聊发发对未来OI的感慨罢……
感谢ruanxingzhi与xehoth大佬给予本蒟蒻的谆谆教导。
参考文献：
https://www.zybuluo.com/ruanxingzhi/note/712255
https://pyoj.ml/blogof/riteme/blog/65
https://www.cnblogs.com/lisperl/archive/2012/11/14/2770396.html
吐槽：liaoy写了一篇水文，搞得这么正式干啥？