滴滴笔试

第一题：

按位与

题目描述:

C/C++ 中的按位与运算符“&”，需要我们自己计算，其功能是参与运算的两个数对应的二进制

相与，只有对应的两个二进位都为1时，结果位才为1，参与运算的两个数均以补码参与运算。

例如: 10的二进制是 0000000011111010，& 0000000010101010 = 0000000010101010。

现在，给你n个数字，请你从中挑选2个数字，使他们的按位与运算结果在所有可能的挑选

方式中是最大的。

输入描述

第一行包含一个正整数n (2≤n≤300000)，表示给定数字的数量。

接下来n行，每行包含1个整数a(0≤a≤2000000000)，表示一个给定的数字。

输出描述

输出仅一行，包含一个数字，表示题目所求的最大按位与的结果。

样例输入

样例输出

参考答案

思路：

尽可能保持最高位为1

从最高位计算，先是1000..，如果有两个数的最高位都是1，那么下一个是110000...；否则是0100000....

n=int(input())
nums=[int(input()) for _ in range(n)]
mask=0
for k in range(30,-1,-1):
    test_mask=mask | (1<<k)
    count=0
    for num in nums:
        if(num&test_mask)==test_mask: # 当 num 和 test_mask 为1的位都是1的时候，才会成立
            count+=1
        if count>=2: # 当有两个这样的数的时候，说明存在x 和y， 有x&y能取到当前的最大值 test_mask
            break
    if count>=2:
        mask=test_mask
print(mask)

第二题：

输入描述

第一行输入一个正整数 T ，表示测试用例数。对于每个测试用例：

第一行包含两个整数 n 和 m ，其中 1 \leq n \leq 10^9 （领地总数上限）， 1 \leq m \leq 100000 （更新操作次数）。
第二行包含 m 个整数 q_1, q_2, \dots, q_m ， q_i=0 表示删除出生地， q_i=1 表示新增出生地。
第三行包含 m 个整数 l_1, l_2, \dots, l_m ，表示每次更新对应的出生地领地左端点，满足 1 \leq l_i \leq n 。
第四行包含 m 个整数 r_1, r_2, \dots, r_m ，表示每次更新对应的出生地领地右端点，满足 1 \leq r_i \leq n 。

输出描述

对于每个测试用例，输出一行共 m 个答案，分别表示对应每次更新后的结果：如果存在两个无交集的出生地（即两个出生地的领地范围没有重叠）输出 YES ，否则输出 NO 。

参考答案

思路：因为题目只要求找到两个不重叠的领地即可，只需要维护 min_R < max_L，就一定有两个领地（一个 min_R 左边的领地，一个 max_l 右边的领地）不重叠。

那么问题就在于怎么快速插入、查询、del 元素

其中字典适合快速del 和快速插入，但是不适合查询最大最小值

结合 heap，可以实现最大最小值的维护

import sys
import heapq
def main():
    input=sys.stdin.read().split()
    ptr=0
    T=int(input[ptr])
    ptr+=1
    out=[]
    for _ in range(T):
        n,m=int(input[ptr]),int(input[ptr+1])
        ptr+=2
        q=list(map(int,input[ptr:ptr+m]))
        ptr+=m
        l_list=list(map(int,input[ptr:ptr+m]))
        ptr+=m
        r_list=list(map(int,input[ptr:ptr+m]))
        ptr+=m
        heap_L = []
        cnt_L={}
        heap_R=[]
        cnt_R={}
        res=[]
        tot=0
        for i in range(m):
            qi=q[i]
            li=l_list[i]
            ri=r_list[i]
            if qi==1:
                tot+=1
                heapq.heappush(heap_L,-li) # - 将最小堆 等价于 最大堆
                cnt_L[li]=cnt_L.get(li,0)+1
                heapq.heappush(heap_R,ri)
                cnt_R[ri]=cnt_R.get(ri,0)+1
            else:
                tot-=1
                cnt_L[li]-=1
                if cnt_L[li]==0:
                    del cnt_L[li]
                cnt_R[ri]-=1
                if cnt_R[ri]==0:
                    del cnt_R[ri]
            # 字典为空，pop heap中的元素 
            while heap_L:
                current_neg_L=heap_L[0]
                current_l=-current_neg_L
                if cnt_L.get(current_l,0)>0:
                    break
                heapq.heappop(heap_L)
            # 字典为空，pop heap中的元素 
            while heap_R:
                current_r=heap_R[0]
                if cnt_R.get(current_r,0)>0:
                    break
                heapq.heappop(heap_R)
            
            if tot>=2 and heap_L and heap_R:
                max_l=-heap_L[0]
                min_r=heap_R[0]
                if min_r < max_l:
                    res.append("YES")
                else:
                    res.append("NO")
            else:
                res.append("NO")
        out.append(" ".join(res))
        
    sys.stdout.write("\n".join(out))
main()

26秋招算法笔试文章被收录于专栏

26秋招算法笔试