Solved 6 problems (ABCDEF),Rank 395,Account Enucai。
前 5 题很简单,但是 D 脑抽挂了 2 发。F 也想了好久。
F - Pay or Receive
给你一张 n 个点 m 条边的有向图,便有边权,对于一条有向边 (u,v,w),均存在一条与之对应的边 (v,u,−w)。q 次询问,每次询问给定 u 和 v,求 u 到 v 的最长路。n,m,q≤105。
直接跑 SPFA,每一个连通块内选一个点,跑他到所有点的最长路,设为 disu,那么答案就是 disv−disu。
因为 u 到 v 的最长路一定有一条经过环内任意点(走错了可以走回来,代价是 0)。
提交记录:link。
G - Do Use Hexagon Grid 2
在一个六边形网格上,有 n 个点,同时给定一个 d,求有多少个点集,使得集合内的每对点的距离都不超过 d。n≤300。
首先考虑从 (0,0) 到点 (x,y) 的距离怎么算。由于 (x,y) 可以向四方向走,可以向 (1,1) 和 (−1,−1) 方向走,所以距离是 max(∣x∣,∣y∣,∣x−y∣)。考虑将一个点 (x,y) 直接映射成一个三元组 (x,y,x−y)。那么问题就转化为:在一个三维空间内,有多少个点集是在同一个 (d+1)×(d+1)×(d+1) 的立方体内。
考虑钦定前两维的最小值位置,然后双指针去扫第三维在范围内的数。即钦定所有点的前两维为 [x,x+d],[y,y+d]。
但是这样会算重,所以考虑做一个小容斥,即 (x,y)−(x+1,y)−(x,y+1)+(x+1,y+1)。
最终复杂度 O(n3logn),logn 由于要排序。
提交记录:link。