备战蓝桥杯 ---- 刷题

一、二分查找

①题目链接：解方程 (nowcoder.com)

 ② 题目链接：圣诞节糖果 (nowcoder.com)

③ 题目链接： 完全平方数 (nowcoder.com)

④ 题目链接：wyh的物品 (nowcoder.com)

⑤ 题目链接： 解方程 (nowcoder.com)

⑥  渴望力量吗 (nowcoder.com)

⑦ 背包问题 (nowcoder.com)   ？递归

⑧ andy的树被砍了 (nowcoder.com)

⑨ A-[USACO 2009 Dec S]Music Notes_2021秋季算法入门班第三章习题：二分、三分、01 (nowcoder.com)

⑩ C-[NOIP2015]跳石头_2021秋季算法入门班第三章习题：二分、三分、01 (nowcoder.com) 

---

①题目链接：解方程 (nowcoder.com)

 考点：二分查找

我的思路：看到这道题的时候我的第一想法是直接暴力枚举即可，于是便开始了尝试，emmm样例是过了，但是超时，也是时间复杂度o(n**3), 然后看了题解说，知道了方程，直接将常数c移项即可，这样就变成了枚举a，b在一个序列中找是否存在一个数等于c，这样就可二分了。【我只想说太妙了！！】

我的代码：

def binary_search():
    n,x = map(int,input().split())
    num = list(map(int,input().split()))
    num.sort()
    for a in num:
        for b in num:
            left = 0
            right = len(num) -1
            target = -(a*(x**2) + b*x)
            # 二分查找
            while left <= right:
                mid = (left+right)//2
                if num[mid] == target:
                    print("YES")
                    return
                elif num[mid] < target:
                    left = mid+1
                else:
                    right = mid-1
    print("NO")
 
binary_search()

 ② 题目链接：圣诞节糖果 (nowcoder.com)

考点：二分查找、双指针

我的思路：刚看到这道题的时候挺蒙的感觉和二分查找没什么关系，看了题目下的题目说明，嗯！都有一个共性，取第一个值，然后第二个值取不大于p的值，然后二分操作一波，嗯！样例过了，提交，QAQ果然牛客的题不是白给的，一个点都没过，哎，思维还是太笨了，看题解去，看了一遍后还是很懵，不过有了思路，演算了一遍明白了。首先给全部堆的糖果对p求余，这时无非两种情况①两个堆相加大于等于p②两堆相加小于p。 情况一：answer =（ falg1 + flag2）- p ，flag1 = a1%p，falg2 = a2%p， a1，a2取最大的两堆，则answer最大。 情况二：flag1 + falg2 < p, 这就需要通过二分来进行。然后两种情况进行比较得出最大的即为答案！！

我的代码：

T = int(input())
for i in range(T):
    n, p = map(int,input().split())
    nums = list(map(int,input().split()))
    nums = [i%p for i in nums]
    nums.sort()
    answer  = (nums[-1] + nums[-2] - p)
    left = 0
    right = len(nums) - 1
    while left < right:
        if (nums[left] + nums[right]) >= p:
            right -= 1
        else:
            answer = max(answer,nums[left] + nums[right])
            left += 1
    print(answer)

③ 题目链接： 完全平方数 (nowcoder.com)

考点： 思维题，数学；也可以二分

我的思路：看到这个题目就想到，把1-31622范围内的平方数<1000000000的都列出来，然后根据l，r，边界通过二分来查找然后相减，我没出来QAQ，而且好像还是超时，也演算了好多次，写不出来；看题解，看到了一个思路，平方数开根号，是连续的，【1，2，3，4，5·········】，然后把左右边界都开根号向下取整，相减即可得到答案，例如：【2，4】---》开根号得------》【1，2】，相减答案为1。但是要注意如果左边界也是平方数的时候，相减后是要加上一的。

我的代码：

from math import sqrt
n = int(input())
for i in range(n):
    left,right = map(int,input().split())
    l = int(sqrt(left))
    r = int(sqrt(right))
    if  l*l == left:
        answer = r - l + 1
    else:
        answer = r - l
    
    print(answer)
 
#二分失败
# def binary_search(my_ls,target):
#     left = 0
#     right = len(my_ls) - 1
#     while left <= right:
#         mid = (left + right) //2
#         if my_ls[mid] == target:
#             return mid
#         elif my_ls[mid] <= target:
#             left = mid + 1
#         else:
#             right = mid - 1
#     return mid - 1
 
 
# n = int(input())
# for i in range(n):
#     sqrt_ls = []
#     l,r = map(int,input().split())
#     for i in range(1,31623):
#         if i**2 < 1000000000:
#             sqrt_ls.append(i**2)
 
#     left = binary_search(sqrt_ls, l)
#     right = binary_search(sqrt_ls, r)
#     print(right)
#     print(right - left)

④ 题目链接：wyh的物品 (nowcoder.com)

考点：01分数规划（二分）

我的思路：这道题超出我的能力，看了题解又去B站看视频又问了队里的大佬，才明白分数规划，

 我的代码：

def check(mid,ls,k):
    answer = []
    for i in ls:
        weight, prim = i[0], i[1]
        answer.append(prim - weight *mid)
    answer.sort(reverse= True)
    return sum(answer[:k]) > 0
        
T = int(input())
for i in range(T):
    n,k = map(int,input().split())
    pan_ls = []
    for i in range(n):
        a,b = map(int,input().split())
        pan_ls.append([a,b])
    l = 0
    r = 1000000
    while r - l > 0.001:
        mid = (l+r) / 2
        if check(mid,pan_ls,k):
            l = mid
        else:
            r = mid
    print("{:.2f}".format(l))
 

⑤ 题目链接： 解方程 (nowcoder.com)

考点： 二分查找

我的思路： 看到解方程，我就突然想到了前几天做的那道解方程题，但是两者不同，前者是移项，确定了target，遍历寻求即可； 而本题，是没办法移项的，所以直接使用二分猜答案，本题还要注意保留四位小数，所以while循环的条件要注意。

我的代码：

T = int(input())
for i in range(T):
    Y = float(input())
    left = 0
    right = 100
    while right - left > 0.00001:
        x = (left + right) / 2
        if 2018 * x ** 4 + 21 * x + 5 * x ** 3 + 5 * x ** 2 + 14 > Y:
            right = x
        elif 2018 * x ** 4 + 21 * x + 5 * x ** 3 + 5 * x ** 2 + 14  < Y:
            left = x
#如果left == 0 或者 right == 100 ，则说明遍历完了没有找到解 
    if left == 0 or right ==100:
        print("-1")
    else:
        print("{:.4f}".format(left))

⑥  渴望力量吗 (nowcoder.com)

考点：二分

我的思路：直接把目标区间确定，然后遍历寻找目标值即可。

我的代码： 其实并不用二分也行

while True:
    try:
        n = int(input())
        n_ls = list(map(int,input().split()))
        q = int(input())
        for i in range(q):
            try:
                l, r, k = map(int,input().split())
                find_ls = n_ls[l-1:r]
                answer = 0
                for j in range(len(find_ls)):
                    temp = find_ls.index(k)
                    if find_ls[temp] == k:
                        find_ls[temp] = 0
                        answer +=1
                print(answer)
            except:
                print(answer)
    except:
        break

还可以二分求解

if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            arr = list(map(int, input().strip().split()))
            q = int(input())
            for i in range(q):
                l, r, k = list(map(int, input().strip().split()))
                tmp = sorted(arr[l - 1: r])
#从左往右找到第一次出现的值的索引例如【1，2】找1返回0
                left = bisect.bisect_left(tmp, k)
# 从右往左找到第一次出现的值的索引，例如【1，2】找1返回1
                right = bisect.bisect_right(tmp, k)
                print(right - left)
        except:
            break

⑦ 背包问题 (nowcoder.com)   ？递归

考点：01背包问题，（emmm 咱也不清楚为啥这东西混进了二分题目列表里）

我的思路：看到这道题，直接暴力，把物品的所有组合情况考虑，然后依次遍历和背包容量比较。看题解，是用的深搜来解决这个问题，这个深搜的dfs函数，我是真蒙了，推理了三个多小时又和我们组的大佬讨论了，结果还是没搞懂这个dfs函数QAQ！

我的代码：

# 这个递归我是真推理不出来
def dfs(indexs,capacity):
    global answer
    if indexs == n:
        return
    if capacity + v_ls[indexs] <= m:
        answer += 1
        dfs(indexs + 1, capacity + v_ls[indexs])
    dfs(indexs + 1, capacity)
 
 
while True:
    try:
        n, m = map(int,input().split())
        v_ls = []
        answer = 1
        for i in range(n):
            v = int(input())
            v_ls.append(v)
        dfs(0,0)
        print(answer)
    except EOFError:
        break

⑧ andy的树被砍了 (nowcoder.com)

考点：二分思想

我的思路：看到这道题，我的第一想法是二分在每天种树对应的当天天数，然后在当天到最会一天砍树的列表里面寻找。但是因为其无序所以不行，然后我演算了一下，发现找到当天种的树，和当天至最后一天砍树的这个列表ls，day + index == answer，这个index是当天种的树经历 遍历ls寻求下标，加上day即为答案，嗯！巧妙，我真聪明！不过超时了，改了改代码，最终过了89%，挺好的。 看了题解，其实思路核心一模一样，有二分的那个感觉，但是又不太沾边，分析题解和我代码的时间复杂度的差距。

分析：

由于第一段代码（题解）中的内部循环的逻辑是通过修改变量 p 和 h 来实现的，因此内部循环的次数不会超过 n，时间复杂度是线性的（O(n)）。而第二段代码（我的代码）中的内部循环的逻辑是通过每次减少变量 ni 来实现的，导致内部循环的次数更多，时间复杂度也更高（O(n^2)）。

因此，第一段代码的性能更好，会比第二段代码更快。原因是第一段代码中的内部循环被正确地设计为在线性时间复杂度范围内执行，而第二段代码中的内部循环导致了二次时间复杂度。

对于大型输入，第二段代码会耗费更多的时间，导致超时。

我的代码：

#题解
n=int(input())
his=list(map(int, input().split()))
cis=list(map(float, input().split()))
res= [n + 1] * n
 
for i in range(n):
    h=his[i]
    p=i
# 有二分的感觉
    while p<n:
        c=cis[p]
        if h<=c:
            res[i]=p+1
            break
        p+=1
        h-=c
         
print(' '.join([str(e) for e in res]))
 
 
# 我的代码
answer_ls = []
def pan(ni,c_ls,day):
    answer = 0
    for j in range(len(c_ls)):
        pan = c_ls[j]
        if ni <= pan:
            answer_ls.append(answer + day)
            break
        else:
            ni -= pan
            answer += 1
 
n = int(input())
h = list(map(int,input().split()))
c = list(map(int,input().split()))
 
for hi in range(len(h)):
    pan(h[hi],c[hi:],hi+1)
 
answer_ls = answer_ls + [n+1]*(n-len(answer_ls))
 
print(" ".join(map(str,answer_ls)))
 

⑨ A-[USACO 2009 Dec S]Music Notes_2021秋季算法入门班第三章习题：二分、三分、01 (nowcoder.com)

考点：经典的二分

我的思路：这道题，超级经典的一个二分，上了，直接把二分模板写出来，然后把音节排序列了一个列表，把问题列为一个列表，然后二分，样例过了，但是提交没全过。看了题解，嗯！巧妙的一点出现了，把【2，1，3】音节的列表变为【0，2，3，6】，这点很巧妙，对应了音节长，然后二分找位置，找不到return left。

我的代码：

import bisect
def binary_search(my_ls, target):
    left = 0
    right = len(my_ls) -1
    while left <= right:
        mid = (left + right) //2
        if my_ls[mid] == target:
            return mid + 1
        elif my_ls[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left
 
N, Q = map(int,input().split())
N_ls = []
 
for i in range(N):
    N_ls.append(int(input()))
 
Q_ls = []  
for j in range(Q):
    Q_ls.append(int(input()))
 
pan_ls = [0]
for i in N_ls:
    pan_ls.append(pan_ls[-1] +i)
 
for k in Q_ls:
    answer = binary_search(pan_ls,k)
    if answer != -1:
        print(answer)
    else:
        if k < N_ls[0]:
            print(1)
        else:
            print(N)

⑩ C-[NOIP2015]跳石头_2021秋季算法入门班第三章习题：二分、三分、01 (nowcoder.com) 

 

考点：二分

我的思路：使得选手们在比赛过程中的最短跳跃距离尽可能长，当出现最小值最大或最大值最小或求最大值、最小值时，就可以考虑一下二分了。 拿走的石头越多，最短跳跃距离越大，具有单调性。假设最短跳跃距离为mid，那么显然1<=mid<L，所以我们就先让左端点l=1，右端点r=L，每次mid取中间值mid=(l+r)//2 ，检查是否可以通过移除不超过M块岩石来保持所有剩余岩石之间的最小距离至少为mid，如果可以返回True，如果不行返回False。

我的代码：

l,n,m = map(int,input().split())
ls = list(int(input()) for i in range(n))
 
def check(mid):
    m_nums = 0
    sit = 0
    for i in range(n):
        if ls[i] - sit < mid:
            m_nums += 1
        else:
            sit = ls[i]
    if m_nums <= m:
        return True
    else:
        return False
 
 
left, right = 1, l
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1
print(left - 1)