Skip to main content

备战 NOIP2016 - 常数优化与压行技巧

· 4 min read

注意, 本文提到的部分内容违背了程序设计规范

常数优化​

卡常是最令 OIer 气愤的事情之一, 比如昨天 Cl dalao 就深陷卡常题无法自拔
那么我们应该如何优化呢?

冗余语句​

void pushdown(int u){//注意此处的delta就是代表上面所说的lazy_tag
    if(u==-1) return;//**写上最好防止出现奇奇怪怪的错误QAQ**
    SEG &now=Tree[u];
    if(now.delta)//如果lazy_tag不为空
    ...
}

代码中有时会出现一些不必要的语句, 比如 Coolkid dalao 曾经写过如下代码(来自这里)

inline 声明​

inline int max(int x,int y){
    ...
}

inline 建议编译器将该函数的函数体插到调用位置, 一般对函数体简单, 调用频繁, 非递归的函数有效, 现代编译器已经取消该选项

#define 声明​

#define PI 3.1415926
#define max(x,y) (x>y?x:y) //据说这样会BOMB， 请谨慎使用

define 声明的内容会在编译时就进行替换, 所以可以理解为将常量直接替换为它的值, 将函数强行加入调用位置, 注意不要用这种方法定义递归函数

压行技巧​

适当压行可以使代码更加简洁, 有时也会兼具常数优化的效果

带默认值的参数​

void build_tree (int l, int r, int p = 0) {}
int query (int l, int r, int p = 0) {}

将函数首部的变量, 引用的声明写入参数表并加入默认值可以起到定义变量的效果, 但需要保证调用方传入参数正确
这种方法也可以简化调用方传入的参数 

void build_tree (int r, int l = 1, int p = 0) {}
int main () {
    int n;
    scanf("%d", &n);
    buid_tree (n);
}

逗号运算符​

int swap (int x, int y) {
    int buf = x;
    x = y, y = buf;
}

在 C 语言中, 多个表达式可以用逗号分开, 其中用逗号分开的表达式的值分别结算, 但整个表达式的值是最后一个表达式的值
逗号运算的结合性是从左至右, 完毕之后整个表达式的值是最后一个表达式的值

三目运算符​

int max (int x, int y) {
    return x > y ? x : y;
}

三目运算符可以简洁地进行比较并返回相应的值, 但注意请不要滥用, 特别是三目运算符套三目运算符

暴力​

inline int max (int x, int y) {return x > y ? x : y;}

经过上面的各种压行可以发现, 有些函数体甚至可以写成一行
但压行过度会使代码可读性下降, 请谨慎而为

栗子​

inline int max (int x, int y) {return x > y ? x : y;}

inline int father (int x) {return x == fa[x] ? x : fa[x] = fahter(fa[x]);}

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);}

int exgcd (int a, int b, int &d, int &x, int &y) {//d 是 gcd(a, b)
    if (!b) {d = a; x = 1; y = 0;}
    else {exgcd(b, a%b, d, y, x); y -= x * (a / b);}
}