随笔题解 Ct. 2
来源：COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
21：35 开始 5h，02：35 结束。
群友「多打打，运气好直接少走 $70$ 年弯路。」
当然我是 1：00 就去睡觉了，剩下一个 C 交给 chr 写了。
当然之前 20：00 的 ARC 我是不可能一不小心下了一波小分的。没有这种事。
A. Accumulation of Dominoes
有一个 $N\times M$ 的网格写有数字，第一行从左到右依次是 $1,2,\dots,M$，第二行是 $M+1,M+2,\dots,2M$，以此类推。试求有多少对格子四联通且数字相差恰好 $1$。
$1\leqslant N,M\leqslant 10^9$。
$\texttt{1s/256MB}$。
签到题一号。
显然 $M\gt 1$ 时答案为 $N\times(M-1)$；$M=1$ 时答案为 $N-1$。
B. Basketball Together
有 $N$ 个人，第 $i$ 个人的力量是 $P_i$。可以把若干个人组成队伍，这样同一个队伍里的所有人的力量都会变为队伍中力量最大的人的力量。一个队伍是合法的当且仅当其中所有人的力量之和严格大于 $D$。试求至多能组成多少个合法的队伍。
$1\leqslant N\leqslant 10^5$，$1\leqslant D,P_i\leqslant 10^9$。
$\texttt{1s/256MB}$。
签到题二号。
显然最优策略是选定一个剩下的人里面力量最大的。设这个人的力量为 $A$，那么在从剩下的人里面抽出来力量最小的 $\left\lceil\frac{D+1}{A}\right\rceil-1$ 个人凑成一个队伍即可。
G. Garage
如果一个正整数 $x$ 能够被表示成 $b^2-a^2$ 的形式，其中 $1\lt a\lt b$，那么称 $x$ 是好的。试求第 $N$ 小的好的正整数。
$1\leqslant N\leqslant 10^9$。
$\texttt{1s/128MB}$。
当然，OEIS 上是能够找到这个数列的。它是 A024352。
我们可以看到，有 $a_n=4+\left\lfloor\frac{4n-3}{3}\right\rfloor\;(n\gt 1)$。特殊地，$a_1=3$。
M. Moving Both Hands
有一张 $N$ 个点 $M$ 条边的有向图，无重边，无自环，边有边权。现在 Challestend 想要玩一个游戏：首先将他的两只手分别放在两个不同的点上。每次他可以将其中一只手沿着一条边移动到一个相邻的点。这一过程需要花费的时间等于边的边权。如果某个时刻 Challestend 的两只手停留在了同一个点上，那么结束游戏。
试求，对于所有 $2\leqslant p\leqslant N$，如果 Challestend 的左手放在 $1$ 号点上，右手放在 $p$ 号点上，那么他是否能够在有限时间内结束游戏，以及如果答案为是，结束游戏的最短用时是多少。
$2\leqslant N\leqslant 10^5$，$0\leqslant M\leqslant 2\times 10^5$，边权 $1\leqslant W_i\leqslant 10^9$。
$\texttt{1s/256MB}$。
日常花式求最短路。相当于求 $1$ 到 $p$ 的最短路，但是要求路径的前半段正常走，后半段要按照边的反方向走。
总之就是正着求一遍最短路然后倒着再求一遍就可以了。
H. Hot Black Hot White
令 $\operatorname{concat}(x,y)$ 表示将 $x$ 和 $y$ 在 $10$ 进制下拼接起来得到的数，如 $\operatorname{concat}(10,24)=1024$。
给定 $N$ 个数 $A_1,A_2,\dots,A_N$，保证 $N$ 是偶数。将这 $N$ 个数分成两类，每类 $\frac{N}{2}$ 个。如果存在一个数 $Z\in[0,3)$，使得对于任意一对被分到不同类的 $A_i$ 和 $A_j$，都有
那么这种分类方案是好的。试给出一种好的分类方案并给出对应的 $Z$。
$2\leqslant N\leqslant 10^5$，$1\leqslant A_i\leqslant 10^9$。
$\texttt{1s/256MB}$。
众所周知，一个数模 $3$ 等于它的 $10$ 进制数位和模 $3$。根据这一条性质，我们能够很容易地得出
于是限制条件可以整理为
$0,1,2$ 平方之后分别变为 $0,1,1$。那么相当于将 $N$ 个 $0$ 或 $1$ 分成两类，并且找到一个数使得它不能通过从两类中分别选出一个数相加得到。不难发现，$0$ 比较多时可以取 $2$，$1$ 比较多时可以取 $0$。
C. Circular Mirror
一个圆上排列着 $N$ 个标记点，顺时针标记为 $1,2,\dots,N$。对于 $1\leqslant i\lt N$，$i$ 号点到 $i+1$ 号点之间的弧长为 $D_i$；$N$ 号点到 $1$ 号点之间的弧长为 $D_N$。
现在需要用 $1\sim M$ 的 $M$ 种颜色给每个标记点上色，且不能出现构成直角三角形的三个标记点颜色均相同的情况。求方案数，对 $998244353$ 取模。
$1\leqslant N\leqslant 3\times 10^5$，$2\leqslant M\leqslant 3\times 10^5$。
$\texttt{1s/256MB}$。
以下仅考虑 $N\gt 2$。
考虑直径穿过的一对标记点，如果这两个标记点颜色相同，那么用于这两个标记点的颜色就不能用于其他标记点；如果这两个标记点颜色不同，那么并没有什么其他限制。
设一共有 $K$ 对标记点被直径穿过。考虑枚举有 $i$ 对标记点颜色相同，可以很容易地得到答案为