牛客挑战赛58

第一题

思路：简单二分查找（错因二分查找不熟）

代码如下

点击查看代码

#include<iostream>#include<algorithm>#include<unordered_map>using namespace std;long long a[1000010];unordered_map<long long,long long>mp;bool cmp(long long a,long long b){	return a<b;} int main(){	long long n,q,a1,x,y;	cin>>n>>q;	for(int i=0;i<n;i++){		scanf("%lld",&a1);		a[i]=a1*a1;	}	sort(a,a+n,cmp);	for(int i=0;i<q;i++){		scanf("%lld%lld",&x,&y); 		long long num=x*x+y*y;		int ans=upper_bound(a,a+n,num)-a;        printf("%d\n",ans);	}	return 0;}

二分查找的分类

1. 查找比刚好标准数大或小的数。

2. 查找标准数的下标，不存在就返回-1。

对于第一类查找，只需要upper_bound(a,a+n,x)-a和lower_bound(a,a+n,x)-a就可以判断

或者手写

1. 主要注意两点if（a【mid】<=k）判断有没有可能是答案，有可能则l=mid没可能则l=mid+1；

2. 判断是（l+r+1)>>1是(l+r)>>1，就是将ans=l带入第一个是mid恒为l一直执行，第二个mid=r终止，同理ans=r时，选第一个。

第二类查找就直接手写

while(l < r){
long long mid = (l + r + 1) >> 1; //因为l=mid,所以在折半取值时,mid应优先取ceil((l+r)/2),避免死循环
if(nums[mid] <= target){
l = mid; //nums[mid]可能为答案
}else{
r = mid - 1;//nums[mid]肯定不是答案了,就将该mid踢出答案所在的[l,r]区间内
}
}
if(nums[l] == target) return l;
return -1;

讲解连接 https://www.zhihu.com/question/268507619/answer/2333102984

第二题 位运算加思维

思路

1. 将a1|a2|a3|a4|a5|a6....和b1|b2|b3|b4|b5......看成一个二进制的字符串（010101101001100110）

2. 先考虑相等的情况，考虑第i位的二进制数决定a1...>b1...

得出以下结论：

1. 前i-1的二进制相等，a的前n个数的前i-1位可以乱取，b的前n-1个数前i-1位也可以乱取，因为b的第n个数的前i-1异或可为任意值，所以sum1=(2(i-1)n * (2(i-1))n-1=2**((i-1)(2n-1))
2. a的第i位为1且b的第i位为0 只要a的n数第i位中有一个不为0的，a的第i位不为0，b的前n-1个数的第i位任意，第n个数的第i位确定 所以sum2=2(n)-1 * 2(n-1)
3. a,b的m-i位可为任意值 sum=2(n(m-i)) * 2（n(m-i))=2**(2n(m-i))

3. 最后考虑a=b的情况 a可任取，b前n-1个数任取 sum3=2(m(n)) * 2(m(n-1))=2**(m(2n-1))

4. 枚举i的每一位即可

代码

点击查看代码

#include<bits/stdc++.h>#define ll long long#define cin(x) scanf("%d",&x)#define cout(x) printf("%d",x)#define cinll(x) scanf("%lld",&x)#define coutll(x) printf("%lld",x)#define pb(x) push_back(x)using namespace std;const int mod=1e9+7;int pow(int x,int y){	int res=1;	for(;y;x=1ll*x*x%mod,y>>=1){		if(y&1)res=1ll*res*x%mod;	}	return res;}int main(){	int n,m;	ll ans=0;	cin>>n>>m; 	for(int i=1;i<=m;i++){	    ans = (ans + 1ll *pow(pow(2, i - 1), 2 *n -1) *(pow(2, n) - 1) % mod*pow(2, n -1) % mod *pow(pow(2, m - i), 2 * n)) % mod;	}        ans=(ans+pow(pow(2,m),2*n-1))%mod;	cout<<ans;	return 0;}

注意

long long 不可以直接%，所以要先开成int型的数组，再用1ll*ans，可以变成ll型且可以求模