首页 > 文章 > 常数优化的一些技巧

常数优化的一些技巧

一.STL

原则上手写要比用STL快,不过有些确实难打···

map和set直接用就好,都是基于红黑树实现(根本不会打

优先队列可以考虑手写,不过大部分情况直接用就行

至于stack和queue,那就是必须手写的

vector内存允许的话直接开2维数组

注意stack打法,do-while循环特别帅!!!

分享图片
 1 #include<iostream>
 2 using namespace std;
 3 int stack[1000],top;
 4 int main(){
 5     int n;
 6     cin>>n;
 7     stack[top++]=n;
 8     do{
 9         cout<<stack[--top]<<" ";
10     }while(top);
11     return 0;
12 }
View Code

二.运算

mod定义成const

能乘不除,能加减别用魔法模法

能位运算就别用加减乘除···

x2^n改成<<n

/2^n改成>>n

swap(x,y)改成x^=y^=x^=y

模数若为2^n可以直接&(mod-1)

也可以先开unsigned int最后取模

两个小于模数相加用down(x)

(x%mod+mod)%mod改成up(x%mod)

分享图片
inline int down(int x){
    return x<mod?x:x-mod;
}
inline int up(int x){
    return x<0?x+mod:x;
}
View Code

数据范围不大可以开long long,中间不取模最后再取

判断奇偶&1

!=直接改成^

三.读入

别用cin,用cin就在主函数加:

ios::sync_with_stdio(false);

cin.tie(0);

打着还麻烦,所以就用scanf或快读

不超过1e5的数据scanf即可

再大了最好用快读

记得位运算优化···

还嫌慢上fread

快读还有一些妙用

比如定义常量不能scanf但可用快读赋值

这在一些读取模数的题目中很有用

下面代码里快读读的是非负整数,读整数特判一下有无‘-’即可,就不给出实现了

分享图片
#include<cstdio>
#include<iostream>
using namespace std;
int const L=1<<20|1;
char buf[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++)
inline int read(){
    int ss=0;char bb=getchar();
    while(bb<48||bb>57)bb=getchar();
    while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();
    return ss;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    n=read();
    puts("233");
    return 0;
}
View Code

四.输出

同理,用printf别用cout

快输是个危险东西,搞不好还会变慢

慎用非递归版快输,输不了零

不过非递归快一点,实在不行特判~

分享图片
#include<cstdio>
#include<iostream>
using namespace std;
char ch[20],top;
inline void write(int x){        //非递归 
    while(x){
        ch[top++]=x%10;
        x=x/10;
    }
    do{
        putchar(ch[--top]+48);
    }while(top);
    puts("");
    return ;
}
void out(int x){                //递归 
    if(x>=10)out(x/10);
    putchar(x%10+48);
    return ;
}
int main(){
    int n=233;
    write(n);
    out(n);
    return 0;
}
View Code

五.dp

其实已经不算卡常了···

1.排除冗杂

能不dp的就别dp

说白了就是for循环里设个限制条件

比如可怜与超市一题

yzh巨佬重设了个tmp数组实现n^2转移,还证明了一波复杂度,%%%

但其实n^3可过···

分享图片
#include<cstdio>
#include<cstring>
using namespace std;
int const N=5005,lar=0x3f3f3f3f,L=1<<20|1;
char buf[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++)
inline int read(){
    int ss=0;char bb=getchar();
    while(bb<48 || bb>57)bb=getchar();
    while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();
    return ss;
}
inline void swap(int &x,int &y){
    int z=x;
    x=y,y=z;
    return ;
}
inline int max(int x,int y){
    return x>y?x:y;
}
inline int min(int x,int y){
    return x<y?x:y;
}
int n,m,pp;
int c[N],d[N],f[N][N][2];
int head[N],Next[N],to[N],t;
int siz[N],lim[N];
inline void add(int x,int y){
    to[++t]=y;
    Next[t]=head[x],head[x]=t;
    return ;
}
void dfs(int x){
    int y,now=2;
    siz[x]=1;
    f[x][1][0]=c[x];
    f[x][1][1]=c[x]-d[x];
    for(int i=head[x];i;i=Next[i]){
        dfs(y=to[i]);
        siz[x]+=siz[y=to[i]];
        for(register int j=siz[x];j>=0;--j){
            int lit=min(now,j);
            for(register int k=(j>lim[y])?j-lim[y]:1;k<lit;++k){
                int o=j-k;
                f[x][j][0]=min(f[x][j][0],f[y][o][0]+f[x][k][0]);
                f[x][j][1]=min(f[x][j][1],min(f[y][o][0],f[y][o][1])+f[x][k][1]);
            }
            f[x][j][0]=min(f[x][j][0],f[y][j][0]);
        }
        for(register int j=siz[x];j>=0;--j)
            if(f[x][j][0]<=m || f[x][j][1]<=m){now=j+1;break;}
    }
    for(register int i=1;i<=siz[x];++i)
        if(f[x][i][1]>=m && f[x][i][0]>=m){lim[x]=i;return ;}
    lim[x]=siz[x];
    return ;
}
int main(){
    memset(f,0x3f,sizeof(f));
    n=read(),m=read(),c[1]=read(),d[1]=read();
    for(register int i=2;i<=n;++i){
        c[i]=read(),d[i]=read();
        add(read(),i);
    }
    dfs(1);
    for(register int i=lim[1];i>=0;--i)
        if(f[1][i][0]<=m || f[1][i][1]<=m){
            printf("%d",i);
            return 0;
        }
}
View Code

2.等效替代

说起来很模糊···

以HAOI2015树上染色为例

染黑点和染白点其实一样

所以你完全可以加一句k=min(k,n-k);

六.初始化

单个变量可以直接初始化,好像比赋值初始化略快

大范围初始化直接memset

memset就是比for循环要快,不要怀疑!!!

当然一些情况你完全可以边for边初始化

最典型的就是矩阵乘法

分享图片
struct ljj{
    int a[101][101];
    friend ljj operator * (ljj a1,ljj a2){
        ljj c;
        for(register int i=1;i<=100;++i)
            for(register int j=1;j<=100;++j){
                c.a[i][j]=0;
                for(register int k=1;k<=100;++k)
                    c.a[i][j]+=a1.a[i][k]*a2.a[k][j];
            }
    }
};
View Code

七.排序

动态维护的用堆或者平衡树

静态可以sort,归并并不推荐(主要是我不会···)

值域小的桶排序

关于sort还有一个神奇操作

叫做随机化快排

大量用sort且待排序的数比较多得话可以考虑一下

顺带一提,随机化快排对有序数列的排序比普通快排快上个几百倍

说白了就是随机化快排不容易被特殊数据卡

再说白了就是能多骗点分…

八.其他

其实这里才是精华

inline和register尽量用

注意inline不要在递归函数里用

register不要在递归过程中用,回溯时可以用

自加自减运算符前置,就是i++改成++i

内存允许且不需memset时bool改int

如果方便可以循环展开

if-else能改就改成三目运算符?:

能用dfs就别用bfs

边权为1的图跑最短路用bfs别用dijkstra

(一个名叫Journeys的题的暴力bfs比dijstra高10分···)

多维数组顺序按for循环来!!!

eg. CodeForces 372CWatching Fireworks is fun

dp[N][M]与dp[M][N]一个TLE60,一个AC

数组维数越少越好

离散化可以利用pair记录下标,映射时更加方便,不用再lower_bound了

还有一个玄学操作叫做卡时

就是你打了个dfs,里面用clock()判断运行时间

快TLE的时候直接输出当前答案

注意clock()返回的时间不是特别准

别把跳出时间定的太极端

还有注意Linux下1e6是一秒,想象一下跳出时间设成1000的酸爽

完结撒花~~

时间:2019-07-20 00:06:53阅读(36)
联系我们 - 留言反馈
© 2017 版权所有 鲁ICP备17052893号