AKSZ-二分算法
2024-04-04 17:16:58
发布于：广东
10阅读
0回复
0点赞
小码王打字网站
int 数据范围：；
long long:
文件判题：
freopen("input.in","r ",stdin);读入“input.in”文件。
freopen("output.out","w",stdout);输出“output.out”文件
/*
代码部分
*/
fclose(stdin);
fclose(stout);
优化cin,取消同步的方法：
ios::sync_with_stdio(0);
cin.tie(0);//cin
手写快读：
inline int read(){
int x=0,f=1;char ch=getchar();//x是数字
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
n=read()//使用方式
对拍 ：
mt19937 rnd(time(NULL));
int x=rnd()%10;//使用方式(一到十随机数)
cout<<x<<endl;//使用方式
二分查找：
1.模板：
int l=0,r=n;
while(l<=r){
mid=(l+r)>>1;
if(a[mid]>x){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
2.二分函数：
lower_bound
int p=lower_bound(a+1,a+1+n,x)-a;
//数组开始下标，数组结束下标加一，待查函数x,-a,返回是一个下标
//适用条件：升序数组
//找到第一个大于等于x的下标
upper_bound
int p=upper_bound(a+1,a+1+n,x)-a;
//数组开始下标，数组结束下标加一，待查函数x,-a,返回是一个下标
//适用条件：升序数组
//找到第一个大于x的下标
二分求平方根：
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(){
int n;
cin>>n;
double l=0.0,r=n;//小数二分
double ans;//记录答案
double eps=1e-6;
while(abs(r-l)>=eps){
double mid=(r+l)/2.0;
if(mid*mid>=n){
ans=mid;
r=mid;
}else{
l=mid;
}
}
printf("%.5lf\n",ans);
return 0;
}
原码：数字前加一个符号位（正0，负1）
反码：除符号位不变，其余位取反（正数反码与原码相同）
补码：正数补码与原码相同，负数在反码的基础上加1
这里空空如也
有帮助，赞一个