- 金裕仓 的博客
论如何在不开火车头的情况下避免卡常
- @ 2024-10-1 12:09:41
首先,也是废话,多去学算法!!!
下面是正文
1,最有效的避免卡常数的方法:快读快写
建议用我的模板(变量类型不全,暂不支持读入&读出浮点数类型,不过对于大部分题来说应该是够用了)
lky告诉我要压行,所以我搞了一波极致压行
namespace fastIO{char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
inline void read(string&s){char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
inline void write(const string&s){for(register int i=0;i<(int)s.size();i++){putchar(s[i]);}}
inline void write(const char&c){putchar(c);}
}using namespace fastIO;
把这坨代码扔到using namespace std;下面那一行就可以用了~
2,在for循环中,我们经常会这样写:,但是这边给大家推荐另外一个东西:。
这东西可以优化你的循环,加快&省空间。具体直接去百度吧
我的习惯是写,然后写。但是大家千万不要去!!!这样是极为不可取的。这个东西只能在循环里面用
3,优化函数。当你绞尽脑汁也优化不了你的算法的时候,你可以尝试以下内容:在函数前面写上。当函数参数在这个函数中是一个定量的话,可以这么写:例如inline int f(const int &x)。前提是在此次函数执行中是一个定量。递归也可以这么做,如果是递归层数,并且在递归函数中并没有加他或者减他或者对他做任何其他的操作,你可以对他加和取地址符,这样能加快一点函数的执行速度。哦对了,这玩意对所有常用的变量类型都可以用,结构体都行。
4,看情况使用位运算。比如说,你在写一个算法的时候,你写到了,那么你可以这么写:n^=lowbit(n)。具体为何自己去查和体会。反正位运算比普通的四则运算要快好多好多
5,如果你想将数组的大小定为常量,那么推荐你写。这个比普通的要快一点点。虽然优化不了多少,但苍蝇肉也是肉
6,手写常用STL,例如队列,栈。
我们都知道STL是较慢的,所以用手写栈与队列会更快。但是难度较大的不推荐手写,比如堆,我听说这玩意手写一个好像需要100多行,手写普通的STL就行了。
哦对了,图论的链式前向星也是这个道理。不推荐大家使用vector,虽然之前我也用vector,但是自从我被卡过一次常之后我就一直用链式前向星了。大家可以去学学这东西的好处以及vector的坏处,对比一下自然就会发现哪个好哪个不好了。
如果你想写二元组,多元组,我也不建议你写STL。结构体是更加优秀的选择。
7,别用endl!别用endl!别用endl!这玩意慢的要死,都给我换成'\n'