AKSZ-二分算法

tourism

2024-03-31 17:41:03

发布于：广东

7阅读

0回复

0点赞

今日份竞赛技巧

读写文件

#include<fstream>//文件读写 
#include<iostream>
int main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	//正常代码，cin和cout照常
	fclose(stdin);
	fclose(stdout);
	return 0;
}

提高输入速度

1.用scanf();
2.用cin和cout,在之前加两行代码：

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

3.手搓手写快读（最快！）

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		f(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

注意，这一段代码仅用于输入int类型

随机生成数（最快！）

用万能头,~~因为不知道是哪个头文件里的~~

mt19937 rnd(time(NULL));
int x=1+rnd()%1000000000;

用途：对拍时用于生成随机数据

比赛中想到思路之后怎么做：

1.只能敲暴力（下下策但是极其重要）
2.先敲正解，调试过样例，文件过大样例
3.写暴力对拍，生成随机测试数据，有错则改
4.检查freopen()

二分查找

整数二分

模板：

#include<iostream>
using namespace std;
int n,a[1000005];
bool check(int a){
	return/*判断条件*/; 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);//提速，可省略 
	
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cin>>x;
	int l=1,r=n,ans=-1;
	//闭区间[l,r],开区间[l,r)不包括最后一个节点 
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

`upper_bound()`和`lower_bound()`

头文件：algorithm
lower_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end
upper_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end
若想要得到这个数字的下标而不是它的地址，需要减去一个begin

小数二分(以计算平方根近似值为例)

#include<iostream>
#include<cmath>
using namespace std;
int n;
bool check(double mid){
	return mid*mid<=n; 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);//提速，可省略 
	
	cin>>n;
	double l=0.0,r=n,ans=-1;
	double eps=1e-6;//精度控制 
	//闭区间[l,r],开区间[l,r)不包括最后一个节点 
	while(abs(r-l)>=eps){
		double mid=(l+r)/2.0;
		if(check(mid))l=mid,ans=mid;
		else r=mid;
	}
	printf("%.5lf",ans);
	return 0;
}