OI/ACM最全卡常大招

NO.10: 循环展开：

在缓存和寄存器允许的情况下一条语句内大量的展开运算会刺激 CPU 并发(蛤？这是个什么原理，算了，反正写了没坏处就这么写吧)

NO.9: 特殊运算优化：(或许这真的没用)

取模优化：

inline int inc(int x,int v,int mod){x+=v;return x>=mod?x-mod:x;}//代替取模+

inline int dec(int x,int v,int mod){x-=v;return x<?x+mod:x;}//代替取模-

或者对于模数p进行#define宏定义

绝对值优化：

inline int Abs(int a){//绝对值优化
{

    int b=a>>;

    return (a+b)^b;

}

NO.8: 前置++/--运算符：(有利无弊)

NO.7: if()else语句比()?():()语句慢(但慢的不多，在判断较少的时候还是用if吧)。

网上很多说if比?:慢，但是其实不是这样的。二者的汇编除了文件名不一样其他都一模一样。其实不是?:比if快而是?:比if-else快。

NO.6: 内联：

函数内联：比如说：

inline add(int u,int v)

{

    star[++cnt].to=v;

    star[cnt].nxt=head[u];

    head[u]=cnt;

}

但要拒绝inline大递归函数，用的少的函数比如只用1次的就不要inline了，那样反而更慢；

另类内联：

struct haha{

    int v,x;

    inline bool operator < (haha tar){//强制内联

        return v<tar.v;

    }

}lala[MAXN+];

NO.5:使用局部变量的效率比使用静态变量要高。

因为局部变量是存在于堆栈中的，对其空间的分配仅仅是修改一次\(esp\)寄存器的内容即可.而局部变量存在于堆栈中最大的好处是，函数能重复使用内存，当一个函数调用完毕时，退出程序堆栈，内存空间被回收，当新的函数被调用时，局部变量又可以重新使用相同的地址。当一块数据被反复读写，其数据会留在\(CPU\)的一级缓存（\(Cache\)）中，访问速度非常快。而静态变量却不存在于堆栈中。

NO.4:优化STL

大部分的STL较慢的原因是在动态内存分配时对push_back()的函数大大的不友好；

我们可以手写足够大小的内存池来代替动态分配内存。

#include<bits/stdc++.h>

using namespace std;

#define reg register

static char space[],*sp=space;

template<typename T>

struct myalloc:allocator<T>{

    myalloc(){}

    template<typename T2>

    myalloc(const myalloc<T2> &a){}

    template<typename T2>

    myalloc<T>& operator=(const myalloc<T2> &a){return *this;}

    template<typename T2>

    struct rebind{typedef myalloc<T2> other;};

    inline T* allocate(size_t n){

        T *result=(T*)sp;sp+=n*sizeof(T);

        return result;

    }

    inline void deallocate(T* p,size_t n){}

};

list<int,myalloc<int> > L;vector<double,myalloc<double> > vec //容量的定义

但当内存过大时，不要套用此代码，因为该代码为了简短并没有释放内存；

NO.3: I/O优化

scanf比cin快得多，printf比cout快得多，如果你不知道就……就现在知道了

普通版：(适用于正负int范围内的数)

void read(int &x)

{

     int f=;x=;char s=getchar();

     while(s<''||s>''){if(s=='-')f=-;s=getchar();}

     while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

     x*=f;

}

提升版:(快是快，但在考试中的性价比并不高)

inline char get_char(){//超级快读

    static char buf[],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

}

inline int read(){

    int num=;

    char c;

    while(isspace(c=get_char()));

    while(num=num*+c-,isdigit(c=get_char()));

    return num;

}

NO.2: register

在定义一个变量时加一个register，其意义是将该变量放入寄存器中进行运算(如果可以的话),

它的效果在该变量不断重复使用时间的优化极大，往往用时是不优化的40%；

NO.1: #pragma GCC optimize(2)（请勿在NOIP中作死）

这便是O2优化

它的作用极大，但如果代码不规范，它在优化时会改变某句代码的含义，所以在用时一定要小心从30%TLE变为100%WA;

实践证明开了O2的莫队快的飞起，模拟退火烧到了你上辈子的屁股；

巴特西

OI/ACM最全卡常大招

最新文章

热门文章