ABC280比赛小记

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\le 10^5$。

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

因为 $u$ 到 $v$ 的最长路一定有一条经过环内任意点（走错了可以走回来，代价是 $0$）。

提交记录：link。

G - Do Use Hexagon Grid 2

在一个六边形网格上，有 $n$ 个点，同时给定一个 $d$，求有多少个点集，使得集合内的每对点的距离都不超过 $d$。$n\le 300$。

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

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

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

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

提交记录：link。