AtCoder Beginner Contest 409 补题

AtCoder Beginner Contest 409

Equilateral Triangle

考虑到既然是圆上的等边三角形，那么一定能把圆三等分。因此先找出每个点的位置，然后枚举每个点求解能和它组成等边三角形的点即I-L//3,I-2L//3，通过乘法定理求解，因为会对每个点求解一遍，所以一个三角形会重复计算三次。

n,k=RR()
# 要求周长能被三等分
if k%3:
    print(0)
    exit(0)
cur=0
arr=[cur]
for x in RR():
    cur+=x
    cur%=k
    arr.append(cur)
ans=0
memo=Counter(arr)
for idx in arr:
    ans+=memo[(idx-k//3)%k]*memo[(idx-2*k//3)%k]
print(ans//3)

Connecting Points

对于给定的数据范围可以直接操作

• 操作一：枚举所有的点计算距离，放入优先队列中
• 操作二：弹出优先队列的头，拼接
• 操作三：并查集操作

class UF:


n,q=RR()   
uf=UF(n+q)

nums=[]
h=[]

for i in range(n):
    x,y=RR()
    for j in range(i):
        px,py=nums[j]
        h.append((abs(px-x)+abs(py-y),i,j))
    nums.append([x,y])
m=n

heapify(h)

for _ in range(q):
    tmp=RR()
    if tmp[0]==1:
        x,y=tmp[1:]
        idx=0
        vis={}
        # 计算新添加的点与其他点的距离
        for px,py in nums:
            d=abs(px-x)+abs(py-y)
            root=uf.find(idx)
            if root in vis:vis[root]=min(vis[root],d)
            else:vis[root]=d
            idx+=1
        for k,v in vis.items():
            heappush(h,(v,k,n))        
        nums.append([x,y])
        m+=1
        n+=1


    elif tmp[0]==2:
        if m==1 or not h:print(-1)
        else:
            # 注意队列头有一些是已经连接上的需要清理掉
            while h and uf.connect(h[0][1],h[0][2]):heappop(h)

            d=h[0][0]
            while h and h[0][0]==d:
                _,i,j=heappop(h)
                if not uf.connect(i,j):
                    uf.union(i,j)
                    m-=1
            print(d)
    else:
        u,v=tmp[1:]
        v-=1
        u-=1
        if uf.connect(u,v):print('Yes')
        else:print('No')