- C24tanhaolun's blog
二分
-
C24tanhaolun
LV 4
@
2025-3-13 13:15:30
存一下二分代码
在排序数组中查找元素的第一个和最后一个位置
#include<bits/stdc++.h>
using namespace std;
const int npr=1E6;
int num[npr];
int target;
// int isblue(int i){
// if(num[i]<=target){
// return 0;
// }
// return 1;
// }
int n;
// void two_fen(int l,int r){
// while(l!=r){
// int middle=(l+r)/2;
// if(isblue(middle)){
// l=middle;
// }
// else{
// r=middle;
// }
// }
// cout<<l<<" "<<r;
// }
int twoleft() {
int left=-1,right=n;
while (left+1 <right) {
int mid=(left+right)/2;
if (num[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if(right<n&&num[right]==target){
return right;
}
return -1;
}
int twoRight() {
int left = -1, right = n;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (num[mid] <= target) {
left = mid;
} else {
right = mid;
}
}
if(left >= 0 && num[left] == target){
return left;
}
return -1;
}
signed main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
cin>>target;
cout<<twoleft()<<" "<<twoRight();
return 0;
}
循环比赛日程表
#include<bits/stdc++.h>
using namespace std;
const int maxn=1025,maxm=11;
int compt[maxn][maxn];
int m;
int main(){
scanf("%d",&m);
int n=1<<m,k=1,half=1;
compt[0][0]=1;
while(k<=m)
{
for(int i=0;i<half;i++)
for(int j=0;j<half;j++)
compt[i][j+half]=compt[i][j]+half;//���Ͻǣ����Ͻ�+2^(n-1)
for(int i=0;i<half;i++)
for(int j=0;j<half;j++)
{
compt[i+half][j]=compt[i][j+half];//���½ǣ����Ͻ�
compt[i+half][j+half]=compt[i][j];//���½ǣ����Ͻ�
}
half*=2;
k++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d ",compt[i][j]);
putchar('\n');
}
return 0;
}
取模运算
#include<bits/stdc++.h>
using namespace std;
// int modder(int a,int b){
// int c=a;
// for(int i=1;i<b;i++){
// a*=c;
// }
// return a;
// }
long long c;
long long modder(long long x,long long y){
if(y==0){
return 1;
}
long long isy=modder(x,y/2);
if(y%2==0){
return (isy*isy)%c;
}
return x*(isy)%c*(isy)%c;
}
signed main(){
long long a,b;
cin>>a>>b>>c;
long long modi=modder(a,b);
// cout<<modi<<endl;;
cout<<a<<"^"<<b<<" mod "<<c<<"="<<modi;
return 0;
}
2011
#include<bits/stdc++.h>
using namespace std;
// int modder(int a,int b){
// int c=a;
// for(int i=1;i<b;i++){
// a*=c;
// }
// return a;
// }
string b;
// long long c;
// long long modder(long long x,long long y){
// if(y==0){
// return 1;
// }
// long long isy=modder(x,y/2);
// if(y%2==0){
// return (isy*isy)%1000;
// }
// return x*(isy)%1000*(isy)%1000;
// }
signed main(){
long long a,m=0,s=1;
cin>>a;
while(a--){
cin>>b;
// printf("%.lld\n",modder(2011,m));
m=0;
for(int i=1;i<=3;i++){
if(b.length()>=i)
m+=(b[b.length()-i]-'0')*pow(10,i-1);
}
for(int i=0;i<m;i++){
s=s*2011%10000;
}
cout<<s<<endl;
s=1;
}
// long long modi=modder(a,b);
// // cout<<modi<<endl;;
// cout<<a<<"^"<<b<<" mod "<<c<<"="<<modi;
return 0;
}
一元三次
#include <bits/stdc++.h>
using namespace std;
double a, b, c, d;
double fx(double x) {
return a*x*x*x+b*x*x+c*x+d;
}
void finder() {
double l=-100;double r=100;
for(double i=-100;i<100;i+=1.0001){
l=i;
r=i+1;
if(fx(l)*fx(r)>0){
continue;
}
while(r-l>1e-6){
double mid=(l+r)/2;
if (fx(mid)*fx(r) <= 0) {
l = mid;
}
else {
r = mid;
}
}
printf("%.2f ",r);
// return l;
}
// printf("%.2f ",r);
}
vector<double> roots;
int main() {
cin>>a>>b>>c>>d;
finder();
}
特定值
#include<bits/stdc++.h>
using namespace std;
int a[114514],b[114514];
int main(){
int n,x;
cin>>n;
for(int i=0;i<=n-1;i++){
cin>>a[i];
b[i]=i+1;
}
cin>>x;
for(int j=0;j<=n-1;j++){
if(x==a[j]){
cout<<b[j];
break;
}
}
return 0;
}
最接近元素
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxs=1e6+10;
int n;
ll a[maxs],num=0;
ll jiejin(ll b){
ll l=0,r=n-1;
if(b<=a[l]){
return a[l];
}
if(b>=a[r]){
return a[r];
}
//ll m=(l+r)/2;//放这里的时候进入循环m不会更新h_h 被卡了好久555
while(r-l>1){
// if(b<a[m]){
// r=m;
// }
ll m=(l+r)/2;
if(b>=a[m]){
//r=m;
l=m;
}
else{
r=m;
}
}
if(abs(a[l]-b)<=abs(a[r]-b)){
return a[l];
}
return a[r];
}
signed main(){
ll x,s;
cin>>n;
for(ll i=0;i<n;i++){
cin>>a[i];
}
cin>>x;;
for(ll i=0;i<x;i++){
cin>>s;
cout<<jiejin(s)<<endl;
// b[++num]=jiejin(s);
}
// sort(b,b+num,greater<int>());
// for(int i=0;i<num;i++){
// cout<<b[i]<<endl;
// }
return 0;
}
函数零点
#include<bits/stdc++.h>
using namespace std;
long double l=1.5,r=2.4,cen=(l+r)/2;
long double x;
long double f=pow(x,5)-15*pow(x,4)+85*pow(x,3)-225*pow(x,2)+274*x-121;
long double fx(){
while(r-l>=0.00000001){
cen=(r+l)/2;
long double mmcen=pow(cen,5)-15*pow(cen,4)+85*pow(cen,3)-225*pow(cen,2)+274*cen-121;
long double mmr=pow(r,5)-15*pow(r,4)+85*pow(r,3)-225*pow(r,2)+274*r-121;
long double mml=pow(l,5)-15*pow(l,4)+85*pow(l,3)-225*pow(l,2)+274*l-121;
if(mmr*mmcen<0){
l=cen;//如果f(mid)和f(r)的符号相反则说明在[mid,r]区间内存在一个零点
}
if(mml*mmcen<0){
r=cen;//如果f(mid)和f(l)的符号相反则说明在[mid,l]区间内存在一个零点
}
}
return cen;
}
signed main(){
printf("%.6Lf",fx());
return 0;
}
三分
#include<bits/stdc++.h>
using namespace std;
int n;
long double l,r,a[100010];
long double ccccccc(long double x){
long double cnt=0;
for(int j=1;j<=n+1;j++){
cnt=cnt*x+a[j];
}
return cnt;
}
int main(){
cin>>n>>l>>r;
for(int j=1;j<=n+1;j++){
cin>>a[j];
}
while(r-l>=0.0000000000000001){
if(ccccccc(l+(r-l)/3.0)<ccccccc(r-(r-l)/3.0)){
l=l+(r-l)/3;
}else{
r=r-(r-l)/3;
}
}
cout<<l;
}
数列分段
#include<iostream>
using namespace std;
int n,m;
int a[100000];
int sum=1,cnt;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
if(cnt+a[i]>m){
cnt=0;
sum++;
}
cnt+=a[i];
}
cout<<sum;
return 0;
}
木材加工
#include<bits/stdc++.h>
using namespace std;
#define int long long
int s,n;
int a[9000000];
int l=1,r=1e8;
// void l(int l,int r){
// while(l<=r){
// int mid=(l+r)/2;
// int sum=0;
// for(int i=0;i<n;i++){
// sum+=a[i]/mid;
// }
// if(sum<s){
// l=mid-1;
// }
// else{
// r=mid+1;
// }
// }
// cout<<l;
// }
signed main(){
cin>>n>>s;
for(int i=0;i<n;i++ ){
cin>>a[i];
}
// l(ls,rs);
// cout<<l;
while(l<=r){
int mid=(l+r)/2;
int sum=0;
for(int i=0;i<n;i++){
sum+=a[i]/mid;
}
if(sum<s){
r=mid-1;
}
else{
l=mid+1;
}
// sum=0;
}
cout<<l-1;
return 0;
}