AtCoder-ABC319A Legendary Players
使用 map
即可。
提交记录:Submission - AtCoder
AtCoder-ABC319B Measure
依题意模拟。
提交记录:Submission - AtCoder
AtCoder-ABC319C False Hope
题目说得很模糊。
直接 \(9!\) 枚举所有顺序,判断行列对角线是否出现顺序靠前的两个数相等且与第三个数不相等。
提交记录:Submission - AtCoder
AtCoder-ABC319D Minimum Width
直接二分。
提交记录:Submission - AtCoder
AtCoder-ABC319E Bus Stops
注意到 \(P_i\) 很小,而 \(\mathrm{lcm}\{1,2,3,4,5,6,7,8\}=840\),那么模 \(840\) 同余的询问从起点到终点的耗时是相等的。
提交记录:Submission - AtCoder
AtCoder-ABC319F Fighter Takahashi
不会。
贪心策略是有可以打怪增加的一定打怪增加,这个过程是关于 \(s\) 的小根堆。
但是吃药不好处理,位置很少可以状压,设 \(f(S)\) 表示吃了 \(S\) 集合的药达到的最大力量值,这样避免了吃药的决策。
转移就是枚举最后一个吃的药 \(i\),先判断以 \(S\) 状态能不能走到 \(i\),可以直接对于每个 \(S\) 记录在此状态下 \(u\) 节点是否可达,再以 \(S\cup \{i\}\) 去尽可能去打之前没有打到的怪并增加力量,这个过程用小根堆 BFS 一遍即可。
时间复杂度 \(O(2^{10}n\log n)\)。
提交记录:Submission - AtCoder
AtCoder-ABC319G Counting Shortest Paths
算是一个小技巧。
对于完全图删去一些边,可以使用补图来求解。
先考虑如何求最短路,维护一个当前没有遍历到的节点集合,再对于每个节点用 set
维护与其没有连边的节点。
首先将 \(1\) 加入队列,并从没有遍历到的节点集合中删去,之后每次将队首 \(u\) 取出,枚举没有被遍历到的节点集合,大部分节点与 \(u\) 有连边,可以入队并从集合中删去,因此节点总共最多被枚举但不删去 \(O(m)\) 次,复杂度 \(O(m\log n)\)。
之后统计路径个数类似,也是 BFS,设 \(f_u\) 表示到 \(u\) 的最短路径个数,\(sum_d\) 表示最短路为 \(d\) 的节点 \(f\) 之和。大部分节点都可以直接从 \(sum_{d_u-1}\) 转移,再减去与 \(u\) 的连边被删去的即可,复杂度也是 \(O(m\log n)\)。
提交记录:Submission - AtCoder