防卡常的奇技淫巧?

发布于 2019-09-08  104 次阅读


1.读优跟快速输出

这个东西应该很常见

直接上我现在在用的板子

namespace IO {
    const int MX = 4e7;		
    char buf[MX];
    int c, sz;

    void begin() {			
        c = 0;
        sz = fread(buf, 1, MX, stdin);  
    }

    inline bool read(int &t) {		
        while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) ++c;
        if (c >= sz) return false;			
        bool flag = 0; if(buf[c] == '-') {
        	flag = 1;
            ++c;
        }
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; ++c)
        	t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}//using namespace IO ;
namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

对于1e7的随机数据

io_1 :0.7036 seconds

io_2 :1.581 seconds

scanf: 6.444 seconds

还有一种神级读优

int read()
{
   int a ;
   cin>>a;
   return a ;
}

2.少用{}与()

在清楚优先级以及作用范围的情况下,尽量少用大括号与小括号。

不过这个优化并不大;

3.多用前缀++

比如

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

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

前者的i自增时会多一个临时变量

so……

4.展开循环(骗开多线程?

#include <stdio.h>
#include <time.h>
int a[80000050][6]={0} ;
int main()
{
	
	time_t st1 = clock() ; 
	for(  long long int i=1ll ; i<=80000000 ; ++i)
 	{
 		a[i][1]+=a[i-1][1];
		a[i][2]+=a[i-1][2];
		a[i][3]+=a[i-1][3];
		a[i][4]+=a[i-1][4];
		a[i][5]+=a[i-1][5];
 	}
	time_t st2 = clock() ;
	printf("%d\n",st2-st1) ;
	printf("time start,end is %f\n",difftime(st2,st1)/CLOCKS_PER_SEC);
	//printf("time t1 t2 is %f\n",difftime(st2,st1));
}

time start,end is 2.39100

#include <stdio.h>
#include <time.h>
int a[80000050][6]={0} ;
int main()
{
	
	time_t st1 = clock() ; 
	for(  long long int i=1ll ; i<=80000000 ; ++i)
	for( long long int j=1ll; j<=5; ++j)
		a[i][j]+=a[i-1][j];
			
	time_t st2 = clock() ;
	printf("%d\n",st2-st1) ;
	printf("time start,end is %f\n",difftime(st2,st1)/CLOCKS_PER_SEC);
	//printf("time t1 t2 is %f\n",difftime(st2,st1));
}

time start,end is 2.842000

当然,一两组数据不能说明什么,但是多组试验下确实是前者比较快。

使用条件就是后行的运算对前行的没有依赖性。

5.前缀register

将变量放到寄存器中加快速度

在ccf中非常好用= =

#include <stdio.h>
#include <time.h>
int main()
{
	int a=0 ;
	time_t st1 = clock() ; 
	for( register long long int i=1ll ; i<1e10 ; ++i);
	time_t st2 = clock() ;
	printf("%d\n",st2-st1) ;
	printf("time start,end is %f\n",difftime(st2,st1)/CLOCKS_PER_SEC);
	//printf("time t1 t2 is %f\n",difftime(st2,st1));
}

 

time start,end is 6.705000

#include <stdio.h>
#include <time.h>
int main()
{
	int a=0 ;
	time_t st1 = clock() ; 
	for( long long int i=1ll ; i<1e10 ; ++i);
	time_t st2 = clock() ;
	printf("%d\n",st2-st1) ;
	printf("time start,end is %f\n",difftime(st2,st1)/CLOCKS_PER_SEC);
	//printf("time t1 t2 is %f\n",difftime(st2,st1));
}

time start,end is 22.361000

离谱(´_ゝ`) 

6.const也有用?

简单地说,const之后,模运算就被优化为了移位与减法,从而使得运算速度略微提高。

相关网址:传送门

使用方法自行 Google or Baidu

7.少用内部较慢的运算

在不损失精度的前提下

尽量少用

  1. 取余:%
  2. sqrt()
  3. 除法 /

其中原因没有深入了解。

8.循环的步进尽量大

这里也没有特别说明,知道就行了,灵活使用。

9.while > for

for在汇编的时候多了一条jump语句

so……,尽量使用while?

10.老生常谈位运算

虽然说这是非常常见的防卡常手段

但是必须了解位运算的原理,以及各自的优先级

才能用的最好。

比如说

if( !n%2 ) 
    return n / 2 %2 ;

可以改成

if (n&1^1)
     return n>>1&1;

还有:

x * 2 +1 == x<<1 | 1 

之类的

需要注意的是:不要使用括号!

11.三目

三目快。

12.寻址优化——减少指针跳动

#include <stdio.h>
#include <time.h>
int a1[40050][10050]={0} ;
int main()
{
	
	time_t st1 = clock() ; 
	int T = 50 ;
	while( T-- )
		for(  long long int i=1ll ; i<=10000 ; ++i )
			for(  long long int j=1ll ; j<=10000 ; ++j )
				a1[i][j] ;
	time_t st2 = clock() ;
	printf("%d\n",st2-st1) ;
	printf("time start,end is %f\n",difftime(st2,st1)/CLOCKS_PER_SEC);
	//printf("time t1 t2 is %f\n",difftime(st2,st1));
}
for(  long long int i=1ll ; i<=10000 ; ++i )
			for(  long long int j=1ll ; j<=10000 ; ++j )
				a1[j][i] ;

后者是要比前者快的

这是一种 底层优化

距离CPU非常近的地方有一个高速缓存Cashe

Cashe会在你访问某段信息时,将该信息以及附近的信息都放进Cashe

所以只要我们访问的时候只要让地址比较接近

就可以提高速度。

13.内联inline

非递归,简单语句,就用 ;

14.传参时使用“引用”+“指针”

不使用引用,好像也会有一个拷贝,跟后缀++类似;

15.使用常量函数

不作说明

(是因为作者没去了解。

16.强制内联

#define Inline __inline__ __attribute__((always_inline))

直接在函数前面加

__attribute__((noinline))

17.加速器作弊

没错,这东西就是在作弊

Noip中禁止使用!

(你会获得0分的好成绩以及禁赛三年。

开启O2优化之后,STL的速度可以到达神仙级别


#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline" );
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

P:手动加栈

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

 

这其实不是优化速度

扩大栈,提高递归层数。

喜欢这篇文章吗,不妨分享给朋友们吧!

科学是第一生产力