省流
\(40min\) 切掉前五题，后面再无建树。
10.16
内含剧透，请vp后再来。
不是题解！！！！！！！
赛时
A B C 均为简单模拟，省略不谈。
D 题给了一个矩阵，矩阵中有空地，墙，关着的门，开着的门，转换器几种东西。当碰到转换器时门的开关改变。问最短多少步从起点走到终点。用双层 \(BFS\) 记录转换器的两种状态即可。
E 题给了 \(n\) 个白点，中间没有线。有三个操作，连接两个点，把点的黑白转换，问这个点是否连接到黑点。用并查集维护即可。此时不到 \(40min\) 没吃罚时。
然后根据难度先开 G 题，题目给一个 \(-1e14 \leq n \leq 1e14\)，要求找到一个数 \(x\) 使 \(x ^ 2 + x + n\) 为一个完全平方数，输出所有 \(x\)。我一开始花了大量时间在打表找规律上，无果。到最后剩二十分钟左右才开始推。不妨表示 \(x\) 为 \(x + i\)，那么平方就是 \(x ^ 2 + 2ix + i ^ 2\)，把 \(n\) 替换掉后面的部分，就可以求出 \(x\)。如果 \(x\) 是一个整数，那么这个就可以。枚举足够多的 \(i\)，但不知道最大能是什么情况，结果挂了一个点。没有时间，比赛结束。
赛后
看题解，发现推式子的方向不太一样。题解直接设 \(y ^ 2 = x ^ 2 + x + n\)，然后使用配方法进行一些变换。
\[4x^2 + 4x + 4n = 4y^2
\]
\[(2x+1)^2 - 1 + 4n = (2y)^2
\]
\[(2y)^2 - (2x+1)^2 = 4n - 1
\]
\[(2y - (2x+1))(2y + (2x+1)) = 4n - 1
\]
所以我们只要枚举 \(4n - 1\) 的全部因子看符合公式的有多少就可以了，复杂度就确定为了根号的。
2025年10月16日