常见常数优化以及代码风格等

来源:

没有开启 -O2 优化

编译器没有开 -O2 优化,考虑重新实现库函数

• isdigit()
• max() / min()
• unique() / lower_bound() / upper_bound()
• IO:
  • C: scanf()/printf
  • C++: cin / cout
• STL
  • queue
  • stack
  • priority_queue /heap
  • deque
• ...

IO优化

src:

fread读入挂

const int BUF=40000000;char Buf[BUF],*buf=Buf;const int OUT=20000000;char Out[OUT],*ou=Out;int Outn[30],Outcnt;inline void write(int x){  if(!x)*ou++=48;  else{    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;    while(Outcnt)*ou++=Outn[Outcnt--];  }}inline void writell(ll x){  if(!x)*ou++=48;  else{    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;    while(Outcnt)*ou++=Outn[Outcnt--];  }}inline void writechar(char x){*ou++=x;}inline void writeln(){*ou++='\n';}inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}//这句话放到代码中fread(Buf,1,BUF,stdin);//样例#include
    
     using namespace std;typedef long long ll;const int BUF=40000000;char Buf[BUF],*buf=Buf;const int OUT=20000000;char Out[OUT],*ou=Out;int Outn[30],Outcnt;inline void write(int x){  if(!x)*ou++=48;  else{    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;    while(Outcnt)*ou++=Outn[Outcnt--];  }}inline void writell(ll x){  if(!x)*ou++=48;  else{    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;    while(Outcnt)*ou++=Outn[Outcnt--];  }}inline void writechar(char x){*ou++=x;}inline void writeln(){*ou++='\n';}inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}int main(){    fread(Buf,1,BUF,stdin);    int a,b;    read(a),read(b);    write(a+b);    writeln();    fwrite(Out,1,ou-Out,stdout);}
    

一般读入挂

inline ll 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*10+ch-'0';ch=getchar();}    return x*f;}

超神读入挂

namespace fastIO{    #define BUF_SIZE 100000    #define OUT_SIZE 100000    #define ll long long    //fread->read    bool IOerror=0;    inline char nc(){        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;        if (p1==pend){            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);            if (pend==p1){IOerror=1;return -1;}            //{printf("IO error!\n");system("pause");for (;;);exit(0);}        }        return *p1++;    }    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}    inline void read(int &x){        bool sign=0; char ch=nc(); x=0;        for (;blank(ch);ch=nc());        if (IOerror)return;        if (ch=='-')sign=1,ch=nc();        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';        if (sign)x=-x;    }    inline void read(ll &x){        bool sign=0; char ch=nc(); x=0;        for (;blank(ch);ch=nc());        if (IOerror)return;        if (ch=='-')sign=1,ch=nc();        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';        if (sign)x=-x;    }    inline void read(double &x){        bool sign=0; char ch=nc(); x=0;        for (;blank(ch);ch=nc());        if (IOerror)return;        if (ch=='-')sign=1,ch=nc();        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';        if (ch=='.'){            double tmp=1; ch=nc();            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');        }        if (sign)x=-x;    }    inline void read(char *s){        char ch=nc();        for (;blank(ch);ch=nc());        if (IOerror)return;        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;        *s=0;    }    inline void read(char &c){        for (c=nc();blank(c);c=nc());        if (IOerror){c=-1;return;}    }    //getchar->read    inline void read1(int &x){        char ch;int bo=0;x=0;        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());        if (bo)x=-x;    }    inline void read1(ll &x){        char ch;int bo=0;x=0;        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());        if (bo)x=-x;    }    inline void read1(double &x){        char ch;int bo=0;x=0;        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());        if (ch=='.'){            double tmp=1;            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());        }        if (bo)x=-x;    }    inline void read1(char *s){        char ch=getchar();        for (;blank(ch);ch=getchar());        for (;!blank(ch);ch=getchar())*s++=ch;        *s=0;    }    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}    //scanf->read    inline void read2(int &x){scanf("%d",&x);}    inline void read2(ll &x){        #ifdef _WIN32            scanf("%I64d",&x);        #else        #ifdef __linux            scanf("%lld",&x);        #else            puts("error:can't recognize the system!");        #endif        #endif    }    inline void read2(double &x){scanf("%lf",&x);}    inline void read2(char *s){scanf("%s",s);}    inline void read2(char &c){scanf(" %c",&c);}    inline void readln2(char *s){gets(s);}    //fwrite->write    struct Ostream_fwrite{        char *buf,*p1,*pend;        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}        void out(char ch){            if (p1==pend){                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;            }            *p1++=ch;        }        void print(int x){            static char s[15],*s1;s1=s;            if (!x)*s1++='0';if (x<0)out('-'),x=-x;            while(x)*s1++=x%10+'0',x/=10;            while(s1--!=s)out(*s1);        }        void println(int x){            static char s[15],*s1;s1=s;            if (!x)*s1++='0';if (x<0)out('-'),x=-x;            while(x)*s1++=x%10+'0',x/=10;            while(s1--!=s)out(*s1); out('\n');        }        void print(ll x){            static char s[25],*s1;s1=s;            if (!x)*s1++='0';if (x<0)out('-'),x=-x;            while(x)*s1++=x%10+'0',x/=10;            while(s1--!=s)out(*s1);        }        void println(ll x){            static char s[25],*s1;s1=s;            if (!x)*s1++='0';if (x<0)out('-'),x=-x;            while(x)*s1++=x%10+'0',x/=10;            while(s1--!=s)out(*s1); out('\n');        }        void print(double x,int y){            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};            if (x<-1e-12)out('-'),x=-x;x*=mul[y];            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);            if (y>0){out('.'); for (size_t i=1;i
    
     
      write    char Out[OUT_SIZE],*o=Out;    inline void print1(int x){        static char buf[15];        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;        while(x)*p1++=x%10+'0',x/=10;        while(p1--!=buf)*o++=*p1;    }    inline void println1(int x){print1(x);*o++='\n';}    inline void print1(ll x){        static char buf[25];        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;        while(x)*p1++=x%10+'0',x/=10;        while(p1--!=buf)*o++=*p1;    }    inline void println1(ll x){print1(x);*o++='\n';}    inline void print1(char c){*o++=c;}    inline void println1(char c){*o++=c;*o++='\n';}    inline void print1(char *s){while (*s)*o++=*s++;}    inline void println1(char *s){print1(s);*o++='\n';}    inline void println1(){*o++='\n';}    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}    struct puts_write{        ~puts_write(){flush1();}    }_puts;    inline void print2(int x){printf("%d",x);}    inline void println2(int x){printf("%d\n",x);}    inline void print2(char x){printf("%c",x);}    inline void println2(char x){printf("%c\n",x);}    inline void print2(ll x){        #ifdef _WIN32            printf("%I64d",x);        #else        #ifdef __linux            printf("%lld",x);        #else            puts("error:can't recognize the system!");        #endif        #endif    }    inline void println2(ll x){print2(x);printf("\n");}    inline void println2(){printf("\n");}    #undef ll    #undef OUT_SIZE    #undef BUF_SIZE};using namespace fastIO;
     
    

mmap 读入挂

/***************************************作者：xehoth链接：https://www.zhihu.com/question/49272859/answer/154084413来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。******************************************/#include 
    
     #include 
     
      #include 
      
       #define private private:#define public public:class BufferedInputStream {    private char *buf, *p;    private int size;    public inline void init() {        register int fd = fileno(stdin);        struct stat sb;        fstat(fd, &sb);        size = sb.st_size;        buf = reinterpret_cast
       
        (mmap(0, size, PROT_READ, MAP_PRIVATE, fileno(stdin), 0));        p = buf;    }    public inline char nextChar() {        return (p == buf + size || *p == -1) ? -1 : *p++;    }};
       
      
     
    

运算优化

用位运算来优化常数(有 -O2 时编译器会帮你优化)

• x * 10 => (x << 3) + (x << 1)
• x != y => (x^y)
• x != -1 => (~x)
• x * 2 => (x << 1)
• x * 2 + 1 => (x << 1 | 1)
• x/2 => (x>>1)
• (x + 1) % 2 =>(x^1)```
• x % 2 => (x&1)
• x % 2 == 0 => (~(x & 1))

寻址优化

循环展开

循环展开也许只是表面，在缓存和寄存器允许的情况下一条语句内大量的展开运算会刺激 CPU 并发(前提是你的 CPU 不是某 CPU) ---- xehoth

如 BZOJ-3509，暴力+刺激并发就能拿下 rk1，以下是关键代码：

/*********************************************************作者：xehoth链接：https://www.zhihu.com/question/49272859/answer/154084413来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。***************************************************************/while (p1 <= pr) {    tmp += (*p1) * (*p2) + (*(p1 + 1)) * (*(p2 + 1)) + (*(p1 + 2)) *        (*(p2 + 2)) + (*(p1 + 3)) * (*(p2 + 3)) + (*(p1 + 4)) * (*(p2 + 4))        + (*(p1 + 5)) * (*(p2 + 5)) + (*(p1 + 6)) * (*(p2 + 6)) + (*(p1 + 7))        * (*(p2 + 7)) + (*(p1 + 8)) * (*(p2 + 8)) + (*(p1 + 9)) * (*(p2 + 9))        + (*(p1 + 10)) * (*(p2 + 10)) + (*(p1 + 11)) * (*(p2 + 11))        + (*(p1 + 12)) * (*(p2 + 12)) + (*(p1 + 13)) * (*(p2 + 13))        + (*(p1 + 14)) * (*(p2 + 14));    p1 += 15, p2 += 15;}

vector 存图

数据极为强大的最大流使用 vector 存图，例如 1000000 个点，4000000 条边，vector 存图只需要 450ms 左右，而前向星需要 1800ms

原因在于数据太过巨大， vector 动态的劣势已降至极低，而大量访问连续的内存地址显然比前向星更优，如下：

/*作者：xehoth链接：https://www.zhihu.com/question/49272859/answer/154084413来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/for (register int i = iter[v]; i < edge[v].size(); i++) {    Node *p = &edge[v][i];    if (h[v] == h[p->v] + 1) {        register int ret = sap(p->v, std::min(flow - rec, p->f), s, t, n);        p->f -= ret, edge[p->v][p->index].f += ret, iter[v] = i;        if ((rec += ret) == flow) return flow;    }}

语法优化

• inline 在非递归函数前加修饰
• 循环变量 int i => register int i
• 手写栈来优化递归
• 减少乘/除/取模 指令
  x+=add;x%=mod;=> x+=add;x>=mod?x%=mod:1;
• 使用三目运算符 A?B:C

• memset初始化细节 memset(a,0x3f,sizeof(a));

  最后的 a[1] = 0x3f3f3f3f

  int的极限是 0x7fffffff

  还可以 ~0u

  INF有的时候不要刚好赋值到 0X7FFFFFFF ,如果有2个inf的值相加就会溢出。

• 不同类型的话最好在前面显示的强转一下(编译器一般自动处理)
• 常量 >INT_MAX 的话加上 LL
• 后置 ++

• 建议平时在编译的时候把编译指令加上 -ansi

• __attribute__ ，__fastcall (然而这玩意并不能在考试时用)

__attribute__((optimize("Ofast"))) __attribute__((__gnu_inline__, __always_inline__, __artificial__))__attribute__((aligned))

• SIMD 指令集优化矩阵乘法(同样并没有什么用)

/*作者：xehoth链接：https://www.zhihu.com/question/49272859/answer/154084413来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/#include 
    
     #include 
     
      #define DIFFERENT_ORDER 0 static inline void lincomb_SSE(const float *a, const __m128 b[4], float *out) {    __m128 result;    __m128 column = _mm_load_ps(a);    result = _mm_mul_ps(_mm_shuffle_ps(column, column, 0x00), b[0]);    result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0x55), b[1]));    result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0xaa), b[2]));    result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0xff), b[3]));    _mm_store_ps(out, result);} void matmult_SSE(float *A, const float *B) {    _MM_ALIGN16 float mA[16], mB[16];#if DIFFERENT_ORDER    float *out = mA;    memcpy(mA, A, 16 * sizeof(float));    memcpy(mB, B, 16 * sizeof(float));#else    _MM_ALIGN16 float out[16];    memcpy(mB, A, 16 * sizeof(float));    memcpy(mA, B, 16 * sizeof(float));#endif    __m128 Bcolumns[] = {         _mm_load_ps(mB + 0),        _mm_load_ps(mB + 4),        _mm_load_ps(mB + 8),        _mm_load_ps(mB + 12)    };    lincomb_SSE(mA + 0,  Bcolumns, out + 0);    lincomb_SSE(mA + 4,  Bcolumns, out + 4);    lincomb_SSE(mA + 8,  Bcolumns, out + 8);    lincomb_SSE(mA + 12, Bcolumns, out + 12);    memcpy(A, out, 16 * sizeof(float));
     
    

一些注意事项

• OI考场不允许使用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。)
• OI考场严禁使用带下划线的库函数。eg. __gcd()
• 编程时利用宏可以减少代码量，但是请务必在每个变量里加括号。
  #define rep(i,s,t) for(int i=(s);i<=(t);i++)
• 循环变量for(int i;…;…;)请不要放到全局上。这种常数不会卡。相反会带来很多隐式的错误
• 如果你不精通指针请少用它。指针的代码很难查错。竞赛里面请避免使用函数指针，多级指针，指针数组这样的语法。
• 如果可以静态实现，请先考虑静态版本的代码。而不是写动态。(malloc() new)
• 引用不等于指针。这个语法我已经不想解释了。去买本语法书细读。
• OI 考试少用C++的OOP特性，可以使用STL ,template, class, namespace 但不推荐使用。

• 熟悉STL里面的 string ,queue, stack ,vector, set ,map

  后面这些用的少,仅供参考并且在pascal选手消失前应该是不会考的前面这些只是方便才用，

  请注意常数！推荐自己实现。 deque multiset multimap bitset

• memset() 底层是用汇编实现的效率要比直接的快4倍，不是所有的库函数都是c\c++实现的。
• 多维数组请把大的放前面 (开了 -O2 后差别不明显)
• 大量调用 memcpy 还不如直接循环
• C++ 和 c 的 IO 混用时请谨慎
• 宏指令少用( #progma 等)

• 未测试请不要内嵌汇编

代码风格

方便 debug

• 上下括号请对齐
• 请保持缩进
• 变量名函数名推荐按照驼峰命名法
• 取有意义的函数,变量名
• 约定俗成的命名
• 插入适当的空格
• 不要在一行做过多的事
• 多次调用，写成函数

上下括号请对齐 AND 保持缩进

#include
    
     using namespace std;int main(){    //do sth..    return 0;}
    

变量名函数名推荐按照驼峰命名法 checkOfInput()

函数名，变量名最好不要用没有意义的名字。

比如，你要检查素数，函数名更好是 checkPrime() or isPrime() 这类的，而不是solve()

f() 当然也可以直接check() 但是当你有多个函数的时候为了不让自己混淆请使用最前面的方法。

比如，你要写动态规划，状态数组最好开成dp[][]...

这是大家约定俗成的。这样方便大家互相阅读。也方便别人帮你查错。

dfs() //deep-first-searchbfs() //bread-first-searchmaxflow()，dinic() 等//最大流isprime()，getprime()//检查素数，筛素数getdis()//计算欧几里德距离，曼哈顿距离query()//查询操作queryMax()/querySum()update()//更新操作tarjan()//有多种tarjan..找强联通分量/双联通分量/LCA的tarjan算法。LCA（）、RMQ（）//字面意思..check()//一般是二分的check()函数solve()//字面意思..match()//二分图匹配..gethash()//字面意思..getid()//字面意思..getrank()//字面意思..sort()//字面意思..pre()//预处理dp[][] 一般是dp状态定义 或者f[][]/g[][]dfn[] dfs序 que[]/q[]/sta[]/s[] 手写栈/队列 head,tail维护首尾。//边一般意义下: M->边 N->点 Q->操作数struct Edge{ int to,next,w;}e[M]struct Edge{ int u,v,w;}e[M]#define maxn ..#define N ..#define M ...#define mod ...#define max3(a,b,c) max(a,max(b,c))#define isdigit(x) (x>='0'&&x<='9')#define lson u<<1#define rson u<<1|1...

代码中插入适当的空格

for(int i = 1; i <= n; i++)x = (a + b) / 2ans = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

视个人习惯,有的地方空格可以略去

for(int i=1;i<=n;i++)for(int i = 1;i <= n; i++)for(int i = 1; i < = n ; i++)for(int i = 1; i <= n ; i++)for(int i=1;i <= n;i++)#define rep(i,s,t) for(int i=(s);i<=(t);i++)rep(i,1,n)

请不要在一行做过多的事

for(int i = 1; i <= n ; i++)scanf("%d",&a[i]),a[i]<0?a[i]=-a[i]:1;/************************/for(int i = 1; i <= n ; i++)    scanf("%d",&a[i]),a[i]<0?a[i]=-a[i]:1;for(int i = 1; i <= n ; i++){    scanf("%d",&a[i]);    a[i]<0?a[i]=-a[i]:1;}for(int i = 1; i <= n ; i++){    scanf("%d",&a[i]);    if(a[i]<0)a[i] = -a[i];}

如果同样的计算要出现3次以上请写成函数 getdis(),abs()

代码压行

比赛时间短，浪费在代码风格上无意义

for(int i=1;i<=n;i++){    //do sth..}========================for(int i=1;i<=n;i++{    //do sth..}========================#define rep(i,s,t) for(int i=(s);i<=(t);i++)rep(i,1,n){    //do sth..}=========================#define rep(i,t) for(int i=1;i<=(t);i++)rep(i,t){/*do sth..*/}======================================================for(int i=head[u];~i;i=e[i].next){    //do sth..}==============================#define each(x) for(int i=head[x];~i;i=e[i].next)each(u){ /*do sth ..*/}================================================================int gcd(int a,int b){    if(!b)return a;    else return gcd(b,a%b);}================================int gcd(int a,int b){return !b?a:gcd(b,a%b);}================================int gcd(int a,int b){    int t;    while(b!=0)    {        t = a;        a = b;        b = t%b;    }}===============================int gcd(int a,int b){for(int t;b!=0;t=a,a=b,b=t%b);}===============================

附注：

• ACM 赛前请仔细阅读参赛手册,一般会有编译参数
• #progma 手动扩栈在 ACM 中一般是允许的(模板中时常有扩栈)
• ACM 中是否允许内嵌汇编:未知
• Callgrind gprof（或者 windows 上可以用 CodeXL），对症下药