网易3.27笔试 算法 题解+讨论

n = int(input())
arr = list(map(int, input().split()))
colors = input().strip()
q = int(input())
red = [0]
purple = [0]
for i in range(n):
    if colors[i] == 'R':
        red.append(red[-1]+arr[i])
        purple.append(purple[-1])
    elif colors[i] == 'P':
        red.append(red[-1])
        purple.append(purple[-1]+arr[i])

for _ in range(q):
    x = int(input())
    quotient, remainder = divmod(x, n)
    red_res = quotient * red[-1] + red[remainder]
    purple_res = quotient * purple[-1] + purple[remainder]
    print(red_res, purple_res)

x_a, y_a, x_b, y_b, x_c, y_c = map(int, input().split())
v_1, d_1 = map(int, input().split())
v_2, d_2 = map(int, input().split())
import math
distance_ab = math.sqrt((x_a-x_b)**2+(y_a-y_b)**2)
distance_bc = math.sqrt((x_b-x_c)**2+(y_b-y_c)**2)
distance_ca = math.sqrt((x_c-x_a)**2+(y_c-y_a)**2)
if d_1 == 0 and d_2 == 1:
    distance = distance_ab
    print(distance / (v_1+v_2))
if d_1 == 1 and d_2 == 0:
    distance = distance_bc + distance_ca
    print(distance / (v_1+v_2))
if d_1 == 0 and d_2 == 0:
    if v_1 > v_2:
        distance = distance_ab
        print(distance / (v_1-v_2))
    elif v_1 < v_2:
        distance = distance_bc + distance_ca
        print(distance / (v_2-v_1))
    else:
        print(-1)
if d_1 == 1 and d_2 == 1:
    if v_1 > v_2:
        distance = distance_bc + distance_ca
        print(distance / (v_1-v_2))
    elif v_1 < v_2:
        distance = distance_ab
        print(distance / (v_2-v_1))
    else:
        print(-1)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
import sys
colors = sys.stdin.readline().strip()

def twofive(num):
    res_2 = 0
    res_5 = 0
    while num % 2 == 0:
        num //= 2
        res_2 += 1
    while num % 5 == 0:
        num //= 5
        res_5 += 1
    return res_2, res_5

# print(twofive(100))

# 滑动窗口
left = 0
cur = 0
red_2 = red_5 = 0
blue_2 = blue_5 = 0
min_ = float('inf')
for right in range(n):
    cur_2, cur_5 = twofive(arr[right])
    if colors[right] == 'R':
        red_2, red_5 = red_2+cur_2,red_5+cur_5
    elif colors[right] == 'B':
        blue_2, blue_5 = blue_2+cur_2, blue_5+cur_5
    zeros = min(red_2, red_5) + min(blue_2, blue_5)
    if zeros >= k:
        # 缩小
        while left <= right:
            cur_2, cur_5 = twofive(arr[left])
            if colors[left] == 'R':
                tmp_red_2, tmp_red_5 = red_2-cur_2,red_5-cur_5
                tmp_blue_2, tmp_blue_5 = blue_2, blue_5
            elif colors[left] == 'B':
                tmp_blue_2, tmp_blue_5 = blue_2-cur_2, blue_5-cur_5
                tmp_red_2, tmp_red_5 = red_2, red_5
            zeros = min(tmp_red_2, tmp_red_5) + min(tmp_blue_2, tmp_blue_5)
            if zeros >= k:
                left += 1
                red_2, red_5 = tmp_red_2, tmp_red_5
                blue_2, blue_5 = tmp_blue_2, tmp_blue_5
            else:
                break
        min_ = min(min_, right-left+1)
print(min_)

class UnionFind:
    def __init__(self):
        self.father = {}
        self.num = 0
    
    def find(self, x):
        root = x

        while self.father[root]:
            root = self.father[root]
        
        while x != root:
            pre_father = self.father[x]
            self.father[x] = root
            x = pre_father
        
        return root
    
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.father[root_x] = root_y
            self.num -= 1
    
    def add(self, x):
        if x not in self.father:
            self.father[x] = None
            self.num += 1

n, m = map(int, input().split())
grid = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    grid.append(tmp)

q = map(int, input())
nums = list(map(int, input().split()))
painted = [[0]*m for i in range(n)]
res = []
directions = [(1,0), (-1,0), (0,1), (0,-1)]

uf = UnionFind()
for num in nums:
    for i in range(n):
        for j in range(m):
            if grid[i][j] == num:
                painted[i][j] = 1
                uf.add((i, j))
                for di, dj in directions:
                    new_i, new_j = i+di, j+dj
                    if (new_i, new_j) in uf.father:
                        uf.union((i,j), (new_i, new_j))
    res.append(uf.num)
                
print(" ".join(map(str, res)))