【二分答案+倍增快速幂】课堂练习

P1678 烦恼的高考志愿

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N];long long bs(int x){int l=1,r=n;while(l<=r){int mid=l+r>>1;if(a[mid]==x) return 0;if(a[mid]>x) r=mid-1;else l=mid+1;}//根据前驱后继返回最小差值//printf("前驱%d，后继%d\n",a[r],a[l]);return min(abs(a[r]-x),abs(a[l]-x));
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)	scanf("%d",&a[i]);sort(a+1,a+1+n);a[0]=a[n+1]=INT_MAX; // 0x3fffffff  //给每位学生找分数最近的学校long long ans=0;while(m--){int x;scanf("%d",&x);//二分查找返回最接近的差值，找x本身，找不到x那么就找前驱、后继ans+=bs(x);	}printf("%ld",ans);return 0;
}

P1024 [NOIP2001 提高组] 一元三次方程求解

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;double f(double x){return a*x*x*x+b*x*x+c*x+d;
}int main()
{cin>>a>>b>>c>>d;for(int i=-100;i<100;i++){double l=i,r=i+1;//端点l或者r是答案 if(f(l)==0){printf("%.2lf ",l);continue;} if(f(l)*f(r)<0){//答案在l和r之间while(r-l>0.0001)  // 1/0.00001=10000{double mid=(l+r)/2;if(f(mid)*f(r)<0) l=mid; //f(l)*f(mid)>0else r=mid;}printf("%.2lf ",l);}}return 0;
}

B2062 乘方计算

#include<bits/stdc++.h>
using namespace std;
int a,n;
int main(){//朴素法求a的n次方cin>>a>>n;int ans=1;for(int i=0;i<n;i++)ans*=a;cout<<ans<<endl;//cout<<pow(a,n)<<endl;return 0;
}

P8813 [CSP-J 2022] 乘方

#include<bits/stdc++.h>
using namespace std;
int a,n;int quickm(long long a,long long n){//倍增法求快速幂long long ans=1;while(n){if(a>1e9)  return -1;if(n&1) ans*=a;//如果对应的二进制为1,那么累乘n>>=1;a*=a;//倍增if(ans>1e9) return -1; }return ans;
}int main()
{cin>>a>>n;cout<<quickm(a,n);return 0;
}