[奇技淫巧]算法竞赛常数优化技巧/代码风格总结

序言

这几天被卡常恶心到的挺多的..所以不得不恶补了一波黑科技的卡常技巧，然后代码风格的问题很久就想写了..

所以就当做个总结吧。

卡常技巧

修饰符的运用

1.多在非递归函数/过程加inline,好像是说这样编译后调用速度加快..

2.i++比++i慢

3.算是个玄学的东西叫做register,原理在于把变量存在CPU的寄存器中计算快.

一般有需要的话可以这么写

1 2	#define RG register #define rep(i,a,b) for(RG int i=(a);i<=(b);i++)

但是奇怪的是hjq上次帮我调的时候加了RG反而变慢了1s..鬼畜啊..

4.常数少用#define 多用const/typedef

5.少用if else 多用三目运算符

计算优化

6.循环展开,可以在展开的时候每个写成函数会美观一点.

7.读入优化（我的标准写法差不多这样↓）

inline void read()
{
	int x = 0,f = 1;char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * f;
}

上面的x = (x << 1) + (x << 3) + ch - ‘0’;还是cgc想到的马叉虫写法.

8.abs自己写.

函数调用优化

9.某些不开O2时候的函数/STL慢的要死不如自己实现.

e.g.

isdigit(),isalpha(),

max(),min(),

queue<>,map<>,priority_queue<>,

binary_search(),upper/lower_bound().

etc.

奇怪的等价

x10 <=> (x<<3)+(x<<1) x!="y" <=""> x^y
x!=-1 <=> ~x
x2 <=> x<<1 x*2+1="" <=""> x<<1|1 2="" x="" <=""> x>>1
(x+1)%2 <=> x^1
x%2 <=> x&1
x%2==0 <=> ~(x&1)

其他事项

被卡到常数的时候碰到重复变量多开一个记录来减少寻址次数.

比如频繁调用sqrt(x)的时候就可以开个rt记录,频繁调用strlen()的时候如果每次都这么写

1	for (int i=0; i<strlen(s); i++)

后果是这样的时间复杂度为$O(nL)$，死得不明不白.

多维数组请把大的放在前面,寻址的时候如果小的在前,在后面的寻址时间大大加长.

而且开了$O2$后更加的明显,几乎可以快1倍的速度。

~~上面的差不多已经够用了~~

语法问题

下列资料转自http://blog.csdn.net/qq_33583069/article/details/53086992

pow()函数请慎用，低版本有的时候会CE。
考场不允许使用“bits/stdc++.h”库，并且使用该库变量名可能不能使用next （C++库里面有个template是next会CE）
请尽力少用黑语法。
二分图匹配避免link做变量名（还有个什么变量名Linux也会CE我突然记不到了..~~有时其实也可以用“中国式的变量名命名法”这样不会CE。拼音大法好啊~~ 不推荐这种诡异的风格），Linux环境可能会CE。
少用“math.h”|“cmath”库。因为_x,_y,y1,y2,x1,x2,x0,y0,这类命名有时会CE。
考场严禁使用带下划线的库函数。eg. __gcd()
编程时利用宏可以减少代码量，但是请务必在每个变量里加括号。 eg. #define rep(i,s,t) for(int i=(s);i<=(t);i++)
循环变量for(int i;…;…;)请不要放到全局上。这种常数不会卡。相反会带来很多隐式的错误
如果你不精通指针请少用它。指针的代码很难查错。竞赛里面请避免使用函数指针，多级指针，指针数组这样的语法。
如果可以静态实现，请先考虑静态版本的代码。而不是写动态。（malloc() new）
引用和指针不是一个东西。这个语法我已经不想解释了。去买本语法书细读。
考试少用C++的OOP特性，可以使用STL template<> class namespace 但不推荐使用。
请熟悉STL里面的 string queue stack vector set map 后面这些用的少,仅供参考并且在pascal选手消失前应该是不会考的前面这些只是方便才用，但请注意常数！推荐自己实现。 deque multiset multimap bitset
宏指令少用,#progma 肯定是禁了的，别想手动扩栈。涉及操作编译器和系统的函数都要挂。
内嵌汇编也是算作弊处理，毕竟这是算法竞赛，不是信息安全竞赛，也不是编程能力竞赛。
别再用了ios::sync_with_stdio(false)作死再写scanf("%d",&n)；

代码风格

个人习惯而已如果有不太好的毒瘤习惯还是指出来吧.

压行/缩进

如果函数较短而且已经用烂且炒鸡熟悉选择压行,比如

int gcd(int x,int y){return y==0?x:gcd(y%x,x);}

甚至有的时候还会直接define掉.

对于其他较长/重要的严格缩进.

空格

适当增加空格.运算符前后必须加空格.
for (int i = a; i <= b; i++)

Others

int main()必须写成int main(int argc, char *argv[])

void init()必须写成 void init(void)

多组输入输出的一般格式:

while(scanf(....) == .. && .. && ..){
  
}
或者
while(T--)
{
  init();
  solve();
  output();
}

差不多就这样了.