重大BUG+对拍模板+常数优化

某些单词GitHub会报错+图片博客网页加载不了

代码为以下这部分，防止报错每个以.隔开

报错原因在于双重的 {}，通过这种方式设置二维数组也会报错。

\.g.r.a.p.h.i.c.s.p.a.t.h.{.{.f.i.g./.}.}.
\.g.r.a.p.h.i.c.s.p.a.t.h.{.{.f.i.g.2./.}.}.

第二个BUG为图片在网站加载不了，在GitHub可以正常加载，如果必须看图片可以去GitHub仓库里看博客。

C++对拍模板

比赛时不知道自己的代码能否过全部的测试点，或者不清楚哪一种情况错误，不妨试试 对拍。

对拍有两个重要的点，构造数据和两种代码对比。

• 构造数据，包括输入和输出数据。如果输入情况复杂，不能方便手工构造，而要编一个小程序，随机生成。输出数据，则要通过下面的低效率代码来生成。

• 两种代码。用两种算法写代码进行对比：低效率代码、高效率代码。

低效率代码。一般用暴力法实现，代码简单、逻辑正确，但时间会超时很慢，用作基准代码，产生正确的输出数据。

高效率代码用来作为正解，把他与低效率代码产生的输出数据进行对比，便可知道错误。

随机数基础

C++中随机数都是伪随机。但是可以通过设计随机数种子来是伪随机不那么伪随机。

srand(x)：产生以x为种子的随机数列，可以用当前时间或女朋友生日。

time(0)：返回当前时间，即从1970.1.1日0时到达现在的秒数。

rand()：返回\([0,RAND\_MAX]\)内的一个随机正整数。

RAND_MAX：一般有RAND_MAX=32767，或2147483647。

构造实数和负数

需要\([-n,n]\)内的随机数时，先产生一个\([0,2n]\)的正随机数，然后减去n。例如：

int x=rand()%(2*n-1)-n;//生成的是[-n,n]内的随机数

需要实数可以先产生一个大的随机正整数，然后除以10的幂。

构造极大的随机数

1. 可以产生两个随机数相乘,rand()*rand()。但几乎不可能是质数。
2. 可以使用位运算，拼接起来。

生成 [a,b] 范围的随机数

x=rand()%(b-a+1)+a;

和[-n,n]差不多。

去重

使用数组下标或者map。

示例代码

#include<bits/stdc++.h>
using namespace std;
int x;
int bao(){//暴力代码
	//......
	return 0;
}
int solve(){//你的无敌代码
	//......
	return 1;
}
int main(){
	srand(time(0));
	while(1){
		x=rand();
		int ans1=bao(),ans2=solve();
		if(ans1!=ans2){
			printf("x=%d,ans1=%d,ans2=%d\n",x,ans1,ans2);
			return 0;
		}
	}
	return 0;
}

常数优化

• 过早的优化是万恶之源
• 只进行有效的优化
• 不要局限于常数优化

读写优化

1.换行不要使用 endl ，使用 \n。

2.如果使用 cin/cout ，可以关闭流同步，但再与 scanf\printf 混用会带来异常。

关闭流同步举例

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

3.需要更快，可以使用手写快读和快写。在 \(10^6\)个int的输入下，手写输入和标准库差距不到 0.1s。

int read(){
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

4.若仍要更快，可以优化getchar()，但是基本不需要到这地步，这方法没尝试，感兴趣可以自行尝试。

const int SIZE=1<<14;
char getc(){
	static char buf[SIZE],*begin=buf,*end=buf;
	if(begin==end){
		begin=buf;
		end=buf+fread(buf,1,SIZE,stdin);
	}
	return *begin++;
}
//用getc()替代getchar()

缓存优化

对于图的存储，使用结构体性能一般由于多个数组。

struct edge{int u,v,m;}e[m];//更优
int u[M],v[M],w[M];

编译优化

• 不要使用register
• 多使用局部变量

算法常数优化

模运算，比较缓慢。

• 对于整数而言，加减法、位运算最快，乘法次之，除法和取模最慢。
• 如果对特定的数进行取模或乘除，可以加上 const 修饰符。
• 考虑减少取模次数，或者用位运算替代取模