本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 11:12:30

记录

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)$，瓶颈在排序。