网易3.27笔试 算法 题解+讨论
1. 小红小紫
前缀和算法
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)2. 小明追小红
直接分情况判断即可
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)3. 后尾0
滑动窗口
记录红色和蓝色乘积的因子个数（2和5）
不知道为什么只过了88%的样例，在某些情况下colors字符串竟然读不进去，用input()将会出发EOF error，怀疑是BUG。
请问大家是否遇到这个情况？求讨论！
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_) 4. 染色连通问题 可以采用BFS去统计连通块个数，但是只能过50%。
为了加快计算可以采用并查集的方法来利用前面的连通信息。
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))) 
