OI算法竞赛常用套路及优化手段

标签：增量   处理   提高   推荐   queue   问题   数组   常用   etc   

 

 

经典的O3优化（一般写在开头）

 

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")

 

 

G++手动扩大栈（写在main的开始）

int size = 256 

 

 

C++手动扩大栈（一般比较少起作用，推荐上面那个）

 

#pragma comment(linker, "/STACK:102400000,102400000")

 

G++ 64位手动扩大栈

extern int main2(void) __asm__ ("main2"); 
int main2(){ exit(0); }//在这里写main函数
int main(){
	int size=64

读入优化

inline int rd(int& X){
    char ch=X=0;
    for(;ch‘9‘;ch=getchar());
    for(;ch>=‘0‘&&ch

 

 

更快的读入优化

 

char str[10000001]; int stl=0;
inline int rd(int& X){
    char ch=X=0;
    for(;ch‘9‘;ch=str[stl++]);
    for(;ch>=‘0‘&&ch

如果输入文件较大以上方法可以把ch=str[stl++]改成自己实现的getchar，具体代码如下

 

 

#define SIZE 1000000 
char str[SIZE]; int stl=SIZE;
inline char getch(){
	return stl==SIZE?fread(str,SIZE,1,stdin),str[stl=0]:str[stl++];
}
inline int rd(int& X){
    char ch=X=0;
    for(;ch‘9‘;ch=getch());
    for(;ch>=‘0‘&&ch

 

 

线段树和树状数组记得使用位运算

ST表

不要用math库的log！自己预处理！

对于s[i][j]=f(s[i][j-1],s[i+(1

特别是在二维ST表效果显著，速度提升四倍有多

 

取模

首先不得不说把模数写成变量是不太好的做法。。。

我们可以

 

#define M 1000000007
const int M=1000000007

 

 

如果题目要求输入模数呢？

我们还是可以

 

int main(){
	int p; scanf("%d",&p);
	const int Mod=p;
}

如果只有加法，我们考虑判定性取模即可

 

 

int mod(int x){ return x>Mod?x-Mod:x; }

 

 

空间优化，记得C++有一个不常用的东西:short

在64位机器上少用指针因为它和long long一样费空间

 

对于一些奇怪的64位的OJ，我们可以使用__int128来过一些毒瘤数论题（比如对10^18取模）

 

关于memset和memcpy以及memmove

这几个函数效率都非常高，比循环的速度快很多

其实用法也很简单，比如原code是这样的

 

for(int i=l;i

我们可以改成

 

 

memset(a+l,0,r-l+1

注意，左移的位数和a，b的类型有关，这里默认为int，sizeof(int)=4，所以就是左移2（乘4）

 

如果不知道a，b类型所占字节数，可以改成如下

 

memset(a+l,0,(r-l+1)*sizeof(a[0]));
memcpy(a+l,b+l,(r-l+1)*sizeof(a[0]));
memmove(a+l,b+l,(r-l+1)*sizeof(a[0]));

 

 

关于Dijkstra算法

一般的教材(误)上面都说：只适用于所有边权为正的情况

而实际上，dijk+heap是可以在负权图上面跑的，而且比spfa还好写

具体实现，去掉vis数组就好了，虽然这样效率可能比不上spfa了（因为有一个log）

 

关于负权回路和spfa

如果题目就是要你找一个负环，我们可以直接将queue改成priority_queue

这样通常效率会提高很多（仅限于找负环，跑一般的最短路会慢）

如果还想更快，就把priority_queue 的比较函数变成以下的函数（自己实现一个类似greater的东西）dist是距离

 

inline bool cmp(int a,int b){ return dist[a]>dist[b]; }

 

 

 

援引

https://www.cnblogs.com/BAJimH/p/10569411.html

https://blog.csdn.net/JacaJava/article/details/78336840?utm_source=blogxgwz5

OI算法竞赛常用套路及优化手段

标签：增量   处理   提高   推荐   queue   问题   数组   常用   etc   

原文地址：https://www.cnblogs.com/shenben/p/12769869.html