AtCoder Beginner Contest 408 补题

AtCoder Beginner Contest 408

Minimum OR Path

一开始使用爆搜求解，想着可以利用或运算的性质提前退出，然而超时。

这里需要用位运算拆位的技巧，先保证高位为0，即使低位都为1也是更小的，因此从高位到低位求解，使用并查集连接所有使当前位为0的边，然后判断1和n是否连接，如果连接则后续在保证该位为0的情况下继续求解下一位，反之这位只能为1

class UF:
    def __init__(self,n):
        self.parent=[*range(n)]
        self.size=[1]*n
    def union(self,u,v):
        u,v=self.find(u),self.find(v)
        if u==v:
            return 
        # 小的连接到大的上面，如果要固定为j连接到i，则无需判断交换
        if self.size[u]<self.size[v]:
            u,v=v,u
        self.parent[v]=u
        self.size[u]+=self.size[v]
    # find函数不能递归计算
    def find(self,k):
        root=k
        # 先找到该连通块的根
        while self.parent[root]!=root:
            root=self.parent[root]
        # 不断向上连接，节点等于它的父节点，父节点的等于根节点
        while k!=root:
            k,self.parent[k]=self.parent[k],root
        return root
    def connect(self,u,v):
        return self.find(u)==self.find(v)

Athletic

虽然每个位置可以往两边移动，但是每次只能去到高度更小的位置，因此可以考虑DP求解

有公式

按照高度大小排序求解，同时记录在原数组中的索引，用线段树找出区间最大值

class SegmentTree:
    def __init__(self,n):
        self.tree=[0]*(4*n)
    
    def add(self,o,l,r,idx,val):
        if l==r:
            self.tree[o]=val
            return 
        mid=(l+r)>>1
        if idx<=mid:
            self.add(o*2,l,mid,idx,val)
        else:
            self.add(o*2+1,mid+1,r,idx,val)
        self.tree[o]=max(self.tree[o*2],self.tree[o*2+1])
    def query(self,o,l,r,L,R):
        if L<=l and R>=r:
            return self.tree[o]
        res=-1
        mid=(l+r)>>1
        if L<=mid:
            res=max(res,self.query(o*2,l,mid,L,R))
        if R>mid:
            res=max(res,self.query(o*2+1,mid+1,r,L,R))
        return res 

n,D,r=RR()
nums=RR()

# 定义f[i]表示第i小的位置能移动的最大次数
f=[0]*n

# 按照高度排序，同时记录索引
h=[(x,i) for i,x in enumerate(nums)]
h.sort()
t=SegmentTree(n)

# 记录状态，每个状态不是一计算完就可以用于下个状态的求解，需要满足相差为D的条件
d=deque()

# 先初始化为-1，防止对无法跳跃的状态求解出1
for i in range(n):
    t.add(1,0,n-1,i,-1)

idx=0
for hi,i in h:
    # 满足差值才能用于求解下一状态
    while d and hi-d[0][0]>=D:
        x,j,res=d.popleft()
        # 更新
        t.add(1,0,n-1,j,res)
    # 求解最大值
    mx=t.query(1,0,n-1,max(0,i-r),min(n-1,i+r))
    f[idx]=mx+1    
    d.append((hi,i,f[idx]))
    idx+=1
print(max(f))