第一题
文章图片
文章图片
思路：简单二分查找（错因二分查找不熟）
代码如下
点击查看代码
二分查找的分类
1. 查找比刚好标准数大或小的数。
#include
2. 查找标准数的下标，不存在就返回-1。
对于第一类查找，只需要upper_bound(a,a+n,x)-a和lower_bound(a,a+n,x)-a就可以判断
或者手写
- 主要注意两点if（a【mid】<=k）判断有没有可能是答案，有可能则l=mid没可能则l=mid+1；
- 判断是（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... 得出以下结论：
- 前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))
- 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)
- a,b的m-i位可为任意值 sum=2(n(m-i)) * 2（n(m-i))=2**(2n(m-i))
点击查看代码
注意
【牛客挑战赛58】long long 不可以直接%，所以要先开成int型的数组，再用1ll*ans，可以变成ll型且可以求模#include
#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< 
