C++优化

先直接放一个快读快输的优化模板吧

//此优化模板由御·Dragon亲手打制 
#include<bits/stdc++.h>
//万能头，有点耗时间 
#include<cctype>
//供快读快输使用 
#pragma GCC optimize(2)
//O2优化
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define Max(a,b) a > b ? a : b
#define Min(a,b) a < b ? a : b
//outn输出并换行
//out仅输出
//in输入
#define ll long long
#define rg register 
#define New int
//上面的int可以根据需求修改类型
//注意：这里一旦修改为某个类型后
//      优化里面所有的东西都会是此类型，可以单独修改 
//long long与int需要及其区分注意
using namespace std;
namespace OI_Optimization{//自定义优化库 
    /*
    //文件专用快速读入
    char buf[1<<21], *p1 = buf, *p2 = buf;
    inline char gc() {
        if(p1 != p2) return *p1++;
        p1 = buf;
        p2 = p1 + fread(buf, 1, 1 << 21, stdin);
        return p1 == p2 ? EOF : *p1++;
    }
    #define G gc

    #ifndef ONLINE_JUDGE
    #undef G
    #define G getchar
    #endif

    template<class I>
    inline void read(I &x) {
        x = 0; I f = 1; char c = G();
        while(c < '0' || c > '9') {if(c == '-') f = -1; c = G(); }
        while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = G(); }
        x *= f;
    }
    */

    inline New read()//快速读入
    {
        New X = 0,w = 0;
        char ch = 0;

        while(!isdigit(ch))
        {
            w |= ch == '-';
            ch=getchar();
        }
        while(isdigit(ch))
        {
            X = (X << 3) + (X << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -X : X;
    }

    /*char F[200] ;
    inline void write(New x) //快速输出 空间
    {
        if(x == 0)
        {
            putchar('0');
            return;
        }

        New tmp = x > 0 ? x : -x;
        int cnt = 0;

        if(x < 0)
            putchar( '-' );

        while(tmp > 0)
        {
            F[cnt++] = tmp % 10 + '0';
            tmp /= 10;
        }

        while(cnt > 0)
            putchar(F[--cnt]) ;
    }*/

    inline void write(New x)//快速输出 时间
    {
         if(x < 0) putchar('-'),x = -x;
         if(x > 9) write(x/10);
         putchar(x % 10 + '0');
    }

    //附加实数输入
     inline New dbread()
    {
        New X = 0,Y = 1.0;
        int w = 0;
        char ch = 0;

        while(!isdigit(ch))
        {
            w |= ch == '-';
            ch=getchar();
        }
        while(isdigit(ch))
        {
            X = X * 10 + (ch ^ 48);
            ch = getchar();
        }
        ch = getchar();//读入小数点
        while(isdigit(ch))
        {
            X += (Y /= 10) * (ch ^ 48);
            ch = getchar();
        }
        return w ? -X : X;
    }

    #undef New
}
using namespace OI_Optimization;//开启库 

int main()
{//大括号换行更美观 
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

    return 0;
}

循环

值得注意的是，我们通常写循环为

for(int i=1;i<=n;i++)

但是这种写法在效率上浪费时间，码风还奇丑，故按照下面的写法

（\(i++\) 的效率比 \(++i\) 满得多）

for(rg/*这里原本是register，前面define过了*/ int i = 1;i <= n; ++i)

STL

STL好用是好用，但是有些函数很慢（比如 \(max\) 和 \(min\)）。建议手写STL。

故优化模板中有

#define Max(a,b) a > b ? a : b
#define Min(a,b) a < b ? a : b

在后期直接将 \(max(a,b)\) 写成 \(Max(a,b)\) 即可。

函数

我们举个例子：比如求 \(a\) 和 \(b\) 的平方和

大家通常都是这么写

int calc(int a,int b)
{
    int c = a * a + b * b;
    return c;
}

然而这样有点慢，故需要在 \(int\) 前面加上 \(inline\) 加速

inline int calc(int a,int b)
{
    return a * a + b * b;
}

基本码风

像加减乘除、位运算、判断大小等符号，最好前后都加上空格，如

a = b
a *= b
a /= b
a %= b
a += b
a -= b

a < b
a > b
a <= b
a >= b
a != b
a == b

a & b
a | b
a ^ b
a << b
a >> b

优秀卡常

有时候遇到一个重复出现的运算式子，且式子的结果为常数，如下

a = 4,b = 10;
for(rg int i = 1;i <= (a * a) + b; ++i)

那么不难看出循环变量 \(i\) 的最大值每循环一次就要算一遍，当常熟很大时就会浪费许多时间。我们不妨如下

int tmp = 4 * 4 + 10;
for(rg int i = 1;i <= tmp; ++i)

速度就快了很多。

再比如说 ，我们在图论中使用 \(vector\) 存的图需要被遍历的时候，邻居个数通常使用 \(edge[i].size()\) 来得到。然而 \(.size()\) 其实就是往前面不断判断是否还有元素并累加。

这样， \(vector\) 中有多少元素 就要花多少时间 来得到 \(size\)。在遍历邻居的循环里面就会不断调用，浪费时间。

故可以如下

len = edge[i].size();
for(rg int i = 0;i < len; ++i)

你可以在我博客图论详解里面看到。

我们可以多用复合语句和位运算，略。