[数据结构与算法]D23-蓝桥杯-二分

新blog新气象，刚才花了两个小时调116的dfs，现在开始做深搜！！！

789

没有想象中的顺利
1、区分找左边界和右边界的函数
x》=a[mid]找的是右边界；
2、区分判断条件后是写l=还是r=
3、r应该对应的是mid-1

n,q = map(int,input().split())
a = list(map(int,input().split()))
def get_r(k):
    l,r=0,n-1
    while l<r:
        mid = l+r+1>>1
        if k>=a[mid]:
            l = mid
        else:
            r =mid-1
    if a[l]==k:
        return l
    else:
        return -1
def get_l(k):
    l,r = 0,n-1
    while l<r:
        mid=l+r>>1
        if k<=a[mid]:
            r = mid
        else:
            l = mid+1
    if a[l]==k:
        return l
    else:
        return -1
for _ in range(q):
    k = int(input())
    r = get_r(k)
    l = get_l(k)
    print(l,r)

790

格式化输出的时候差一个{}，已经进步很多了！！

n = float(input())

l,r=-100,100
while r-l>1e-8:
    x = (l+r)/2
    if x**3>n:
        r = x
    else:
        l = x
print("{:.6f}".format(l))
        

730

1、在知道是二分题目的情况下，可以写出来；如果不知道是二分，估计很难联想到。这个的数据范围是10**5
2、while（l<r）而不是>
3、这题自己找出了check条件——我要找的是大于等于E的左边界，找的check条件也是符合E要求的条件。——这里还需要听老师是如何讲解这个check条件的、

N = int(input())
nums = list(map(int,input().split()))
l,r =0,100010
def check(mid):
    for i in range(N):
        if mid>=nums[i]:
            mid+=mid-nums[i]
        else:
            mid -= nums[i]-mid
        if mid<0:
            return False
    return True
while(l<r):
    mid = l+r>>1
    if check(mid):
        r = mid
    else:
        l = mid+1
print(l)

1221

第一版本不太对，以为只要保证最大的被平方的顺序就可以，其实不然。

n = int(input())
ans=[]
while n!=0:
    l,r = 0,n
    while(l<r):
        mid = l+r+1>>1
        if mid**2<=n:
            l = mid
        else:
            r = mid-1
    ans.append(l)
    n = n-l**2
if len(ans)<4:
    ans.extend([0]*(4-len(ans)))
ans.sort()
for i in range(len(ans)):
    print(ans[i],end=' ')
        

好凌乱，先去干饭！！！

现在是2022.4.3的14:00
睡了一个很沉的午觉，在一 场的大四的自我介绍上听到一个不太聪明的小学同学笑着讲自己痛苦学习物理的经历。我的同学们，你们还好吗？好久不联系了~假期一定要补上，说一说我们没有说过的故事，可以吗

好了继续做二分了。

1221思路确实想不出来，一会听一下老师的

1227

更是没有思路了，听一下老师的讲解！

现在15:30了。听完了chap2的习题课，出去走了一圈。现在回来把两道二分的题和4道前缀和的题做一下。

1221

听完课后第一版，忘记用二分优化，超时了

N = 3000
n = int(input())
pre = []
ans = []
# 用空间换时间
for c in range(0,int(n**0.5)+2):
    for d in range(c,int(n**0.5)+2):
       pre.append([c*c+d*d,c,d])
pre.sort()
for a in range(0,int(n**0.5)+2):
    for b in range(0,int(n**0.5)+2):
        t = n-a*a-b*b
        for i in range(len(pre)):
            flag = False
            if pre[i][0]==t:
                flag=True
                ans.extend([pre[i][1],pre[i][2]])
                break
        if flag:   
            ans.extend([a,b])
            break
    if flag:
        break
ans.sort()
for i in ans:
    print(i,end=' ')

优化后，还是超时呀

N = 3000
n = int(input())
pre = []
ans = []
# 用空间换时间
for c in range(0,int(n**0.5)+2):
    for d in range(c,int(n**0.5)+2):
       pre.append([c*c+d*d,c,d])
pre.sort()
for a in range(0,int(n**0.5)+2):
    for b in range(0,int(n**0.5)+2):
        t = n-a*a-b*b
        l,r=0,len(pre)-1
        while l<r:
            mid = l+r>>1
            if pre[mid][0]>=t:
                r= mid
            else:
                l=mid+1
        ans.extend([pre[l][1],pre[l][2],a,b])
        break
    break
    #     for i in range(len(pre)):
    #         flag = False
    #         if pre[i][0]==t:
    #             flag=True
    #             ans.extend([pre[i][1],pre[i][2]])
    #             break
    #     if flag:   
    #         ans.extend([a,b])
    #         break
    # if flag:
    #     break
ans.sort()
for i in ans:
    print(i,end=' ')

可能python就是蠢蠢超时把叭
又找到一个错误：
二分后找到的不一定是等于t的，需要判断一下

N = 3000
n = int(input())
pre = []
ans = []
# 用空间换时间
c=0
while c*c<=n:
    d = c
    while c*c+d*d<=n:
        t = c*c+d*d
        pre.append([t,c,d])
        d += 1
    c += 1
        
pre.sort()
flag = False
for a in range(0,int(n**0.5)+2):
    for b in range(0,int(n**0.5)+2):
        t = n-a*a-b*b
        l,r=0,len(pre)-1
        while l<r:
            mid = l+r>>1
            if pre[mid][0]>=t:
                r= mid
            else:
                l=mid+1
        # 不一定能找到对应的t
        if pre[l][0]==t:
            flag = True
            ans.extend([pre[l][1],pre[l][2],a,b])
            break
    if flag:
        break
ans.sort()
for i in ans:
    print(i,end=' ')

这题还是直接暴力吧
甚至暴力写起来思路也不清晰。

这题怎么做都超时啊
复制别人的代码也超时，我丢

1227

这题还是蛮清楚的，二分写check函数真有意思

n,k = map(int,input().split())
N = 100010
h = [0]*N
w = [0]*N
for i in range(n):
    h[i],w[i] = map(int,input().split())

def check(mid):
    res =0
    for i in range(n):
        res += (h[i]//mid)*(w[i]//mid)
    if res>=k:
        return True
    else:
        return False
        
l,r=0,N
while l<r:
    mid = l+r+1>>1
    if check(mid):
        l = mid
    else:
        r = mid-1
        
print(l)

795

n,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
N = 100010
s = [0]*N
for i in range(1,n+1):
    s[i] = s[i-1]+a[i]
for _ in range(m):
    l,r = map(int,input().split())
    print(s[r]-s[l-1])

796

通过了，但是我感觉在读入方面还可以优化。看了一下别人的，发现自己已经写的很好了，没什么优化的，注意x,y都从1开始。

n,m,q = map(int,input().split())
N = 1010
g = [[0]*N for _ in range(N)]
s = [[0]*N for _ in range(N)]

for i in range(1,n+1):
    g[i][:] = [0] + list(map(int,input().split()))
for i in range(1,1+n):
    for j in range(1,1+m):
        s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i][j]

for _ in range(q):
    x1,y1,x2,y2 = map(int,input().split())
    print(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1])
    

1230

直接求，超时了

n,k = map(int,input().split())
N = 100010
s = [0]*N
for i in range(1,n+1):
    a = int(input())
    s[i] = s[i-1]+a
# 求区间和好求，但是暴力进行一段段筛选的话，会超时
res = 0
for i in range(1,n+1):
    for j in range(i,n+1):
        if (s[j]-s[i-1])%k==0:
            res+=1
print(res)

想不出优化方法