前言

卡常数操作并不是想象的那么简单ComeIntoPower dalao 的建议让我知道了这里的深度(实在做不来还是学算法吧 QAQ~~~

适当的优化可以帮你只能想出暴力的算法多A几个点,但是最终嘛

算法的学习和研究最有效 QwQ

a

内容

1.读入优化

2.宏定义

3.选用的数据类型

4.语句与运算优化

5.手写数据结构

6.对拍


One . 读入优化

这个基本都知道吧,我也就不细讲了


读入基于fread,这里实现的只能读入字符和整形,至于输出+stack,基于putchar就好了,反正输出量又不是很大(只是我懒,不愿写


我先说一下关于位运算什么想多了,你把 s*10 写成 (s<<1)+(s<<3)只会让你的程序更慢,因为同样在g++ 把程序编译之后的代码,后者比前者还多了几条语句 。

a

并且 x<<1 == x*2 ; x<<2 == x*4(在汇编里均为等价….) ,而且 如果

void swap(int &x,int &y){
    int temp = x;
    x = y;
    y = temp;
}
// 写成
void swap(int &x,int &y){
    x ^= y;
    y ^= x;
    x ^= y;
}
// 会变慢的 QAQ 原理也和上述类似 
// 所以从此 swap 再也没有 ^ 了  23333

当然位运算在除法里还是很有用的,对2的幂的运算,以及判断奇偶的时候

const int Size=1<<25|1;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2 = (p1=buf) + fread(buf,1,Size,stdin),p1 == p2) ? EOF : *p1++;
}
int read(){
    int s=0,f=1;
    char c=getch();
    while(!isdigit(c) || c == '-') {if(c=='-') f=-1; c=getch();}
    while(isdigit(c)) {s=s*10+(c-48);c=getch();}
    return s*f;
}
// c函数的isdigit()判断和你手写的汇编指令其实是一样 。QwQ
// 另外 把s*10 写成 (s<<1)+(s<<3) 的同学请自重吧 23333
void write(int x){
    static int sta[36];
    int top=0;
    if(x < 0) {
        putchar('-');
        x=-x;
    }
    do{
        sta[top++]=x%10;
        x/=10;
    }while(x);
    while(top) putchar(sta[--top]+48);

}



Second . 宏定义

s

宏定义是个啥? ——————— 也就是define

#define是个好东西啊OUO,不仅可以替换变量名使你的代码更短,还可以定义函数(实则就相当于直接替换),还有奇特的用法,那么开始演示

a

不过请注意 define的本质是替换,所以 如果宏的参数出现 ++x或者 x++ 之类的 请另外加语句除去,否则 x 在宏里会重复计算,导致你调试到死也不知道为什么答案不对

#define fors(i,a,b) for(int i=(a);i<=(b);++i)//首先普通的替代
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(x,val) (memset((x),(val),sizeof (x)))

#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define abs(x) ((x) < 0 ? -(x) : (x)) 
#define swap(x,y,tmp) ((tmp)=(x),(x)=(y),(y)=(tmp))
//注意使用的时候在前面多定义一个temp

#define forvit(i) for(vector<int> :: iterator it=(i).begin();it!=(i).end();++it) 
#define v *it
//注意定义之后,如果定义了一个v的变量会Error,因为已经被v替换成了*it

#define link(x , y) x##y //神奇的拼接,可以将两个int拼在一起
#define Tostring(x) #x
//例如 x=24,y=16 ;int a = link(x,y);  a=2416
//但注意不要超出int 的范围;
//或者你可以使用long long 这样就有18位数字了 ll-inf ~=9e18;
// Tostring 就相当于 给x加上一个""号 但是如果x是个变量的话,那就不行,
// a=12; cout<<Tostring(a)<<endl; 
//-> a 直接输出了变量名,好像没什么用啊 2333 QAQ 如果有dalao发现了这玩意的技巧请告诉我 QwQ


#define pr(...) printf(__VA_ARGS__);


//__VA_ARGS__相当于一个可变参数宏(无关重点
// 主要是 可以这么用 pr("QVQ %d\n" , 1231);就当作printf啦

#define I_O(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout);
// 用于读入文件 , 使用时注意"的位置 , I_O(文件名) 不用加后缀 2333

#define Debug(...) fprintf(stderr,__VA_ARGS__)
// Debug 就是用来调试的 fprintf 和 stderr -> cerr,具体和printf一个用法
// 可以在使用freopen的时候将 Debug 输出到屏幕
// 调试时用fprintf(stderr, "%d", clock())更方便
// Debug("Ans = %d   Time: %d",Ans,clock()); 


Third . 数据类型

1.首先速度的话 int好像是最快的,所以不考虑内存,精度的话尽量都用int存吧


2.vectoriterator 比使用下标 访问 快一点了(虽然 STL 普遍比较慢,如果开O2,vector取下标和数组取下标速度差不多(不过vector要判越界,当然不开O2你最好连vector都不要用


3.数据极为强大的最大流使用 vector 存图,不信的话,你可以自己试试 原因在于数据太过巨大,vector动态的劣势已降至极低,而大量访问连续的内存地址显然比前向星更优


4.提高时空局部性

提高时间与空间局部性即可使你的程序对高速缓存友好。

如果你写一个树剖,上来先开一大堆数组:
int siz[maxn], top[maxn], son[maxn], fa[maxn], depth[maxn];
而访问的时候,却总是siz[i], top[i]之类的连着访问,这样做空间局部性极差,所以为了提高运行速度,我们可以把这些东西扔进结构体里,由于结构体内的元素在内存里是按顺序排列的,所以可以提高空间局部性,虽然有时也可能变慢 QAQ

struct node
{
    int siz, top, son, depth, fa;
    node() { siz = top = depth = fa = 0;}
};
node nd[maxn];

避免使用步长为2的n次幂的内存引用由于高速缓存不是全相连的,使用步长为2的n 次幂的内存引用模式所以会导致每次访问都不命中,效率会比较低不过,基本很少会开2^n的空间吧 2333。


5.bitset 大法 相当于一个二进制类,有很多好用的东西,而且可以优化复杂度,当$n=m=1e5$有时可以用$O(nm/w)$过,w=32/64 字长。

1.用于存储0、1元素。

2.模拟了bool数组,但是单个元素占空间只有1bit。 !!! OVO

3.每个位都能被独立访问。

4.而且这玩意还提供转化成其他类型的函数

5.最重要的是她快 OUO

bitset大法好啊

#include<iostream>
#include<cstdio>
#include<bitset>

using namespace std;

int main()
{
    bitset<1000> a;定义一个 1000 位的bitset 2^1000

    a[100]=1;    //直接赋值 000..1..000
    cout << a.count() << endl;    //计数1的个数  1
    cout << a.size() << endl;    //返回空间大小 100 
    cout << a.test(1) << endl;   0
    cout << a.test(100) << endl;    //判断第i位是否为1 1 
    cout << a.any() << endl;    //是否非空  1
    cout << a.none() << endl;    //是否全空 0
    cout << a.all() << endl;    //是否全满  0

    a.set(2);    //将第2位变成1,不过下标是从0开始 所以是000100 这样的,一定要记住 QAQ
    //如果你直接 a.set();的话,就是全部设为0
    cout << a[2] << endl;    //直接访问,与test相同 1 

    a.reset();    //清空 000...0000
    a.reset(2)    //将第2位变成0,
    cout << a.count() << endl;// 0
    cout << a.none() << endl;// 1

    a.flip();    //反置 1111...1111
    a.flip(2);   //反置第二位从右到左从0开始 Re.Zero
    cout << a.count() << endl;// 100
    cout << a.all() << endl;// 1
    a = a & b;//按位与 这里要b要bitset类型,你也可以重载一下
    a = a | b;//按位或
    a = a ^ b;//按位异或
    a = ~a;//按位补
    a = a << 3;//移位


    bitset<16> b (0xfa2); // 直接赋值
    cout<<b<<endl;
    b: 0000111110100010

    bitset<16> b (string("0101111001"));
    cout<<b<<endl;
    b: 0000000101111001
    // 甚至可以直接赋值01字符串

    b.reset();
    b[8]=1;
    b.to_ulong() 
    //返回它转换为unsigned long的结果,如果超出范围则报错 --256
    b.to_ullong() 
    //返回它转换为unsigned long long的结果,如果超出范围则报错--256
    b.to_string() 
    //返回它转换为string的结果 --010000000
}

实例:[JSOI2010]连通数

这是一个是传递闭包问题所以我们定义$f[i][j]$表示$i$是否能到$j$,然后使用Floyd大法 + bitset 就水过了 2333

#define fors(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=3000;
int n,ans;
char s[maxn];
bitset<maxn> f[maxn];
int main(){
    n=read();
    fors(i,1,n){
        scanf("%s",s);
        fors(j,1,n)
         if(s[j-1]=='1' || i==j)
            f[i][j]=1;
    }
    fors(i,1,n)
        fors(j,1,n)
            if(f[j].test(i))
                f[j]|=f[i];
    fors(i,1,n)
        ans+=f[i].count();
    writen(ans);
    return 0;
}

据说可以用bitset+分块+可持久化过静态仙人掌,不过我是完全看不懂 Orz。接着最后我们再来Orz 一下Cai dalao的手写bitset tql



Four. 语句与运算优化

前言:一般我们的程序会编译器转化为汇编语言,

而一些语句在汇编里是等价的,所以不要轻易相信网上的一些什么语句比什么语句快之类的,如果有对语句相同觉得疑惑的话请自行去这里验证c++ ->汇编

编译器远比你想象的聪明,所以最适合优化的便是所谓“少一些变量”,“少一些判断”等人工的的优化方式了


I.很明显位运算(在某些情况下)十分高效

1. 消去x二进制下最后一个1之后的值

int x = 1100
x - 1 = 1011
x & (x - 1) = 1000

2. 查找x二进制下最后一个1所代表的值(lowbit)

int x = 1100
-x = 0100
x & (-x) = 0100

3. 判断 x 是否是 2 的幂次。

 return ((x & (x - 1)) == 0) ? true : false;
 //因为如果x是2的幂,那么x的二进制表示只有一个1 
 //所以我们只要x & (x-1) 消去最后一个1在判断就可以了

4. x 的二进制表示下 1 的个数

int count(int x){
    x=(x & 0x55555555) + ((x >> 1) & 0x55555555);
    x=(x & 0x33333333) + ((x >> 2) & 0x33333333);
    x=(x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x=(x & 0X00ff00ff) + ((x >> 8) & 0X00ff00ff);
    x=(x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return x;
}
 //分别求出二进制数相邻两个区块的1的个数,再合并相加
 //比用lowbit算快多了 

5.反转pos开始,长度为len的区域

int flip(int n, int pos, int len = 1) {
    return n ^ (((1 << len) - 1) << pos); 
    //16 - 10000
    // flip(16,1,4)- 01110
    // flip(16,1,3)- 11110
    //如果你要反转第0位的话-+1就好了
}

6.取得从pos开始,长度为len的区域对应的整数值

int get(int n, int pos, int len = 1) {
    return (n >> pos) & ((1 << len) - 1); 
    // 14 - 1110
    // gets(14,1,3)-> 7   111 
}

7.取从pos开始,长度为len的区域设置为v

int sets(int n, int pos, int v,int len = 1){
    int o = ((1 << len) - 1);
    return n = (n & (~(o << pos))) | ((v & o) << pos);
    // 15 - 1111
    // sets(15,1,0,3)-> 1   0001
    // sets(16,1,7,3)-> 30 11111   7--- 111
    // 10000 - 11110 就相当于填充
}

8. 求n的二进制表示下后缀0的个数

int count_houzhui(int x){
    int ret=0;
    if( !(x & 65535)) x >>= 16 , ret |= 16;
    if( !(x & 255)) x >>= 8 , ret |= 8;
    if( !(x & 15)) x >>= 4, ret |= 4;
    if( !(x & 3)) x >>= 2 , ret |= 2;
    if( !(x & 1)) x >>=1 , ret |=1;
    return ret + !x;
}
// 17 - 10001 count_houzhui(17) -> 0
// 16 - 10000 count_houzhui(16) -> 4

II. 条件语句

当你的if(A && B)中 如果Bfalse的可能性比A大的话,你就需要互换位置,因为当第一个表达式为false的时候,程序就不会执行后面的表达式


III. 关于取模的优化 实测比普通的 % 快一倍 OvO。

因为避免了模数的除指令运算很费事,所以我们使用加避免了除指令。

inline int modadd(int a,int b){a+=b;return a>=p ? (a-=p) : a;}

// (a+=b) % = p;
// 加法,注意一下大小问题,因为有可能 在a远大于p的时候答案会大于P

inline int moddel(int a,int b){a-=b;return a<0 ? (a+=p) : a;}
// (a-=b) % = p;

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

//这个性质也许会对你的解题有帮助 

inline int mod_mul(int a,int b,int mod){
    int ret=0;
    __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n" : "=d"(ret):"a"(a),"b"(b),"c"(mod));
    return ret;
}
//据说直接使用汇编语言做a*b%c 会比直接% 快,
//不过 NOI系列的比赛都不让用 所以GG , 不过你可以搞搞其他的(例如毒瘤的月赛,逃


ll mul(ll a,ll b,ll p){
    a=a%p,b=b%p;
    return ((a*b - (ll)(( (long double)a * b + 0.5 ) / p) * p )%p +p)%p;
}//防止精度爆炸的乘
//原理就是n%p == n-n/p*p 。
//而后面的则是计算了实数(a*b)/p,向下取整。
//由于C++中long double的精度是超过10^18级别的,因此可以保证结果正确。
//并且式子里两次乘法运算超过了ll的范围,由于C++会高位溢出,
//忽略符号位相当于是在模2^63的意义下做。所以最终结果在2^63以内,因此结果正确


IV.对于矩阵乘法可以通过调整for的顺序使得访问相对连续使得程序运行加快

int c[];
fors(i,1,n)
    fors(k,1,n)
        fors(j,1,n)
            c.m[i][j]=c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod;

fors(i,1,n)
     fors(j,1,n){
        int ik=x.m[i][k];
        fors(k,1,n)
            c.m[i][j]=c.m[i][j]%mod+ik*y.m[k][j]%mod;
          }

// 数组连续访问,简单点就是下标在前的循环也在前(k)
//下标在后的循环也在后(j)
//矩阵乘法用i,k,j的同时将x[i][k]用一个临时变量保存貌似可以快很多 QwQ

也就是说减少不必要的计算,对于一个重复计算的值存入临时变量,并且把访问量越大的尽量放在前面枚举。这样指针的跃动距离会少一些。


V.顺序访问

顺序访问的话缓存可以实现高速遍历(相对于随机顺序)。但是顺序访问与逆序访问,速度是差不多的,不会对缓存造成什么影响,所以我们在遍历数组的时候要尽量修改跳动的指针为连续的指针

fors(i,1,n)
    S+=A[H[i]];
cout<<S<<endl;

H[i] - > rand()
fors(i,1,n)
    S+=A[H[i]];
cout<<S<<endl;

//如果H[i]是一个随机数列的话,那么就会比较慢

VI.循环展开+多路并行

在不超过cache大小的情况下循环展开越深优化越大

由于cpu整数加法运算器有多个,而同一个时间可以最多运算两个整数加法,通过这种方法可以增加流水线吞吐量。实际上,编译器会在第二次隐式汇编优化时候做这个优化,如果你把gcc开到o3以上的优化程度就可以自动在汇编指令层级变成这种形式

//如松爷 pdf 中的例子
double sum(double *a, int n) {
    double s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}
double sum(double *a, int n) {
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    for (int i = 0; i < n; i += 4) {
        s0 += a[i];
        s1 += a[i + 1];
        s2 += a[i + 2];
        s3 += a[i + 3];
    }
    return s0 + s1 + s2 + s3;
}

不过当展开次数过多时,性能反而下降,因为寄存器不够用 也就是 寄存器溢出,比较玄学 ,所以你可以使用Dev c++的调试看看寄存器是否溢出,或者用clock()函数看看怎么展开耗时少。

循环次数未知的循环并行性很差,基本没有研究的价值。如果循环展开k次,就可以把上限设为n-k+1,那么最大循环索引i+k-1将会比n小。然后,再加上第二个循环,以每次处理一个元素的方式处理数组的最后几个元素

优点

1.分支预测失败减少。

2.如果循环体内语句没有数据相关,增加了并发执行的机会。

3.可以在执行时动态循环展开。这种情况在编译时也不可能掌握。

缺点

1.代码膨胀

2.代码可读性降低,除非是编译器透明执行循环展开。

3.循环体内包含递归可能会降低循环展开的得益。

摘自维基百科

VIII. CPU 并发

注意:在使用这个技巧时,需要自行判断能否使用,否则后果…

这个技巧看似简单,但能带来常数级别的飞越,可能出现的情况$n^2$过百万,暴力踩标程。QAQ ,差不多就这么个鬼玩意

fors(int j=1;j<=n; j+=24) {

    ans+=(*(A+j)+*(A+j+1)+*(A+j+2))+(*(A+j+3)+*(A+j+4)+*(A+j+5))+(*(A+j+6)+*(A+j+7)+*(A+j+8))+

                 (*(A+j+9)+*(A+j+10)+*(A+j+11))+(*(A+j+12)+*(A+j+13)+*(A+j+14))+*(A+j+15)+

                 (*(A+j+16)+*(A+j+17)+*(A+j+18))+(*(A+j+19)+*(A+j+20)+*(A+j+21))+(*(A+j+22)+*(A+j+23));

        }

使用条件:

循环展开后,可以方便地用大量简单的运算完成对答案的更新。

观察到你的寄存器并不会溢出。

例题 计算 $∑{i=from ~1 ~to~30000} ~ ~∑{j=from~1~to~30000}(A[i] ~/~B[j]) $ 其中 $B[j]<=64,A[i]<=1e6$ 保留小数点4位

我们首先使用普通的循环展开

fors(j,1,30000) {
    tmp=30000-5;
    for(i=1; i<=tmp; i+=6) {
     ans+=A[i]/B[j]+A[i+1]/B[j]+A[i+2]/B[j]+A[i+3]/B[j]+A[i+4]/B[j]+A[i+5]/B[j];

    }
    for(;i<=30000;++i)
        ans+=A[i]/B[j];

}//2280s

然而速度并没有变得很快???

因为其中的除法运算过多,所以我们再改进一下就ok了

fors(j,1,30000){
    tmp=30000-5;
    for(int i=1; i<=tmp; i+=6) {
        ans+=(A[i]+A[i+1]+A[i+2]+A[i+3]+A[i+4]+A[i+5])/B[j];
    }
    for(;i<=30000;++i)
        ans+=A[i]/B[j];
}//876ms

这里只是简单运用,有兴趣的可以自行尝试一下,CPU并发一般可以加速3倍以上。如果可以配套上循序枚举,再加速2-3倍,那么出现在上BZOJ_3509中“n方过百万,暴力踩标程”的情况也变得可以理解起来

如果是1e5的数据,那么O(n^2)会达到1e10,cup 并行后相当于1e95e8差不多吧

再强调一次:请不要尝试在1e5的数据下使用……3e4/5e4可以尝试一下

Five.手写数据结构

众所周知C++的STL 好用的很(不开O2,甚至有些容器常数大得可以让你的程序T上天

所以你要注意能手写STL就手写不然

ads

所以对于简单的数据结构我们需要手写,例如栈和队列

注意我这里的queues遇到数据需要 pushpop 十分多的时候 ,会RE(超内存 QAQ 希望有dalao告诉我怎么解决

struct stacks
{
    int a[10000];
    int l=0;
    void push(int x){
        a[++l] = x;
    }
    int top(){
        return a[l];
    }
    void pop(){
        --l;
    }
    int empty(){
        return !l;
    }
};

//单调栈
//将一个元素插入单调栈时,为了维护栈的单调性,需要在保证将该元素插入到
//栈顶后整个栈满足单调性的前提下弹出最少的元素。
fors(i,1,n){
    a[i]=read();
}
fors(i,1,n){
    while(!s.empty()&&s.top()<=a[i])
        s.pop();
    ans+=s.size();
    s.push(a[i]);
}
//自然就是从栈顶读出来一个元素,该元素满足单调性的某一端。
//例如代码中取出的即栈中的最小值。


struct queues
{
    int l=0,r=0;
    int a[10000];
    void push(int x){
        a[++r] = x;
    }
    int front(){
        return a[l];
    }
    int back(){
        return a[r];
    }
    void pop(){
        ++l;
    }
    int empty(){
        return l > r ? 1 : 0;
    }
};

//单调队列就是单调递增或者是单调递减的一种队列,就像一个递增队列,
//每当放入的元素使得队列不在单调,则弹出队尾的元素,直到使得队列元素单调一般使用deque实现
int a[maxn]={};
int main(){
    fors(i,1,n){
        while(!q.empty()&&q.back()>=a[i]) 
            q.pop_back();
        q.push_back(a[i]);
    }
    int m=q.size();
    fors(i,1,m){
        printf("%d ",q.front());
        q.pop_front();
    }
    return 0;
}

struct Min_Heap{//priority_queue<int,vector<int>,greater<int> > q
    int lengths,h[5000005];
    void swap_h(int &x,int &y){
        int temp;
        temp=x,x=y,y=temp;
    }
    void Min_Heapify(int i){
        int l=i+i , r=i+i+1 , small;

        (l<=lengths && h[l]<h[i]) ? (small=l) : (small=i);

        if (r<=lengths && h[r]<h[small])
            small=r;

        if (small!=i){
            swap_h(h[i],h[small]);
            Min_Heapify(small);
        }
    }

    void Heap_in(int i,int key){
        h[i]=key;
        while(i>1 && h[i >> 1]>h[i]){
            swap_h(h[i],h[i >> 1]);
            i>>=1;
        }
    }
    int top(){
        return h[1];
    }
    void pop(){
        h[1]=h[lengths];
        --lengths;
        Min_Heapify(1);
    }
    void push(int key){
        ++lengths;
        h[lengths]=key;
        Heap_in(lengths,key);
    }
    bool empty(){
        return !lengths;
    }
    int size(){
        return lengths;
    }
    void clear(){
        lengths=0;
    }
};

struct  Max_Heap{//priority_queue<int> q
    int lengths,h[5000005];
    void swap_h(int &x,int &y){
        int temp;
        temp=x,x=y,y=temp;
    }
    void Heap_out(int i){
        int l=i+i , r=i+i+1 , large; 

        (l<=lengths && h[l] > h[i]) ? large=l : large=i;

        if(r<=lengths && h[r] > h[large])
            large=r;
            if (large!=i){ 
                swap_h(h[i],h[large]); 
                Heap_out(large); 
           }
       }
    void Heap_in(int i,int key){
        h[i]=key;
        while (i>1 && h[i >> 1]<h[i]){
            swap_h(h[i],h[i >> 1]);
            i>>=1;
        }
    }
    void pop(){
        h[1]=h[lengths];
        --lengths;
        Heap_out(1);
    }
    void push(int key){
        ++lengths;
        h[lengths]=key;
        Heap_in(lengths,key);
    }
    int top(){
        return h[1];
    }
    bool empty(){
        return !lengths;
    }
    int size(){
        return lengths;
    }
    void clear(){
        lengths=0;
    }
};



Six.对拍

clock()函数可以返回程序的运行时间,这对于考试中对拍里判断是否超时有帮助(顺便附带一个对拍 2333

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std; 
int main(){
    for(int i=1;i<=23333;++i){
        system("data.exe > date.out");//data是你的随机数据程序(记得不要加freopen)
        double st=clock();//计算开始时间
        system("plus.exe < date.out > plus.out");
        double ed=clock();//计算你的正解运行速度,也记得不要加freopen
        system("pre.exe < date.out > pre.out");
        if(system("fc plus.out pre.out")){
            cout<<"WA"<<endl;
            return 0; 
        //接着你就可以在data.out里查看是你程序答案错误的数据
        }
        else
            printf("Ac,测试点 #%d, 用时 %.0lfms\n",i,ed-st);
    }
    return 0;
}


其他的一些技巧

  1. 尽量不要使用递归。递归可以很优雅和简洁,但是太多的函数调用会造成巨大的开销。

  2. 避免在循环中使用sqrt()函数,因为计算平方根是非常消耗CPU的。

  3. 一维数组比多维数组更快。所以你可以多想一下将维的方法

  4. 浮点数的乘法通常比除法快–使用val * 0.5 而不是val / 2.0。

  5. 加法运算比乘法更快–使用val + val + val而不是val * 3。puts()函数比printf()函数快,虽然不是很灵活。

6.如果你还想研究的话就 并行展开,用大数据多次测量比较。用汇编指令说话,比较编译后的汇编差别。以及了解时间周期,便于指出最慢的那个操作。以及背后的原理(看不懂汇编 逃

  1. 内存开小:主要是数量级上要小,比如O(nlogn)->O(n),O(n^2)->O(n)等。申请内存和释放内存次数尽量少:数据结构中使用内存池就是个好例子。

  2. 对于很大的图/树重标号,即按dfs序重新标号,可以让内存连续。

9.减少瓶颈操作次数,比如LCT/线段树的pushup,pushdown是瓶颈,所以应该减少它们的次数。ZKW线段树正是因为减少了期望次数才变快了

10.dp的时候精确计算上界,减少状态数。

#### 最后5点我是直接加上 ComeIntoPower dalao的话的,因为我并不怎么会这些操作 还是等我技术再好一点的时候说吧,读者可以自行研究一下(太难了 ,QAQ 逃

总结一下

首先对于一道题,如果只能想出O(n^2)的暴力,那么不妨试试这些优化。而不是着拿到一个题,一眼过去就用暴力+卡常。

优化你的算法最重要,计算机科学的支柱是算法,而不是底层优化。

本文到此结束 OvO,如果有dalao 指明有什么不对的地方,十分感谢

分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。

4 条评论

wendster · 2018年10月15日 12:07 下午

诡异,超大字体而又超长文章严重搅乱了我的大脑皮层灰质……

    B_Z_B_Y · 2018年10月15日 2:41 下午

    等我 有时间 改改 QAQ

by · 2018年10月14日 12:18 下午

这篇文章的数学公式好像都没显示出来?

    by · 2018年10月14日 12:20 下午

    好吧, 我的锅。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *