【VP 记录】ABC361

· · 个人记录

记录

B 吃一发不应该，D 调很久不应该，F 不知道怎么回事挂一个点。E 是板子，切得比较快。G 太困难了（好像也不是那么困难）。

题解

A - Insert

基本循环题，略过不表。

B - Intersection of Cuboids

有体积交等价于每一维上都有交的区间，对每一维分别判断即可。

C - Make Them Narrow

先排序，显然取的一定是连续的 n-k 个数，所以枚举起点 i，答案为 \min_{i=1}^{k+1}a_{i+n-k-1}-a_i。

D - Go Stone Puzzle

状压 + BFS，需要记录的状态为每一位上是黑还是白的 S 串，以及目前空着的位置 x，状态数 (n+2)2^{n+2}，BFS 转移时枚举哪两位移到 x,x+1 即可。只要保证空着的两个位置均为 0，就可以直接用相等判断是否是结果串。

E - Tree and Hamilton Path 2

发现一定要走每一条边以到达每一个点，同时走到最后一个没走的点 x 时不用走回来，也就是从 x 回到 st 的路不用走。所以记树的边权和 tot，最长链长度 dis，答案为 2tot-dis。也就是从最长链一端开始走，最后走到另一端，这条链上的边只会经过一次。求 dis 用 DFS 求树的直径即可。

F - x = a^b

发现 10^{18} 内最多只有 2^{59}，所以没有次数高于 59 的数。考虑设 f_i 表示 x^i\le n 的 x 个数，那么 f_i=\lfloor\sqrt[i]{n}\rfloor。

但是直接加会算重很多 x，考虑每个 x 都在最大的使得 k_i\le n 的 i 处计算，那么考虑到 i 时就需要将 f_i 减去 \sum_{j=2i}^{P}f_j,i\mid j，也就是把在 i 的倍数处考虑过的减掉。

但是，用枚举和 pow 函数求 f_i 都挂了几个点，目前不知道原因，是因为前者中我用来求 f_2 的 sqrt 函数以及 pow 函数均有精度问题，导致挂了，需要注意。

G - Go Territory

考虑如果直接 BFS 找出所有与 (-1,-1) 相连的点，复杂度会到 O(XY)，大约 4\times10^{10} 级别。考虑减少点数，发现如果分行考虑，每行每一段连续的白点为一个连通块，那么连通块总数为 X+n，可以接受。相邻两行连边时用双指针可以做到总共 O(n)，总时间复杂度 O(n\log n)，瓶颈在排序。