Solved 6 problems (ABCDEF),Rank 395,Account Enucai

55 题很简单,但是 D 脑抽挂了 22 发。F 也想了好久。

F - Pay or Receive

给你一张 nn 个点 mm 条边的有向图,便有边权,对于一条有向边 (u,v,w)(u,v,w),均存在一条与之对应的边 (v,u,w)(v,u,-w)qq 次询问,每次询问给定 uuvv,求 uuvv 的最长路。n,m,q105n,m,q\le 10^5

直接跑 SPFA,每一个连通块内选一个点,跑他到所有点的最长路,设为 disudis_u,那么答案就是 disvdisudis_v-dis_u

因为 uuvv 的最长路一定有一条经过环内任意点(走错了可以走回来,代价是 00)。

提交记录:link

G - Do Use Hexagon Grid 2

在一个六边形网格上,有 nn 个点,同时给定一个 dd,求有多少个点集,使得集合内的每对点的距离都不超过 ddn300n\le 300

首先考虑从 (0,0)(0,0) 到点 (x,y)(x,y) 的距离怎么算。由于 (x,y)(x,y) 可以向四方向走,可以向 (1,1)(1,1)(1,1)(-1,-1) 方向走,所以距离是 max(x,y,xy)\max(|x|,|y|,|x-y|)。考虑将一个点 (x,y)(x,y) 直接映射成一个三元组 (x,y,xy)(x,y,x-y)。那么问题就转化为:在一个三维空间内,有多少个点集是在同一个 (d+1)×(d+1)×(d+1)(d+1)\times (d+1)\times (d+1) 的立方体内。

考虑钦定前两维的最小值位置,然后双指针去扫第三维在范围内的数。即钦定所有点的前两维为 [x,x+d],[y,y+d][x,x+d],[y,y+d]

但是这样会算重,所以考虑做一个小容斥,即 (x,y)(x+1,y)(x,y+1)+(x+1,y+1)(x,y)-(x+1,y)-(x,y+1)+(x+1,y+1)

最终复杂度 O(n3logn)O(n^3\log n)logn\log n 由于要排序。

提交记录:link