AtCoder Beginner Contest 243 题解

A,B题过水已隐藏

C题 Collision 2

给定 \(n\) 个动点，每个点有向左或向右运动方向和初始坐标 \((x_i,y_i)\) ，问是否存在相撞的点？

\(n\le2e5,0 \le x_i,y_i\le1e9\)

注意到只会左右运动，也即只有相同纵坐标的点可能相撞，于是按 \(y\) 为第一关键字，\(x\) 为第二关键字排序，如果当前的点是向左，那么记录一下，如果后面出现了向右的点匹配就有解，一直找不到则无解。

D题 Moves on Binary Tree

一棵无限大的二叉树，根节点是 \(1\) ，点 \(i\) 的左儿子和右儿子是 \(2i\) 和 \(2i+1\) ，开始在节点 \(X\) ，给定一个长为 \(n\) 操作字符串，有回到父亲，去左儿子，去右儿子三种操作，求最后所在节点编号。

\(1\le n\le 1e6\) ，保证最后的答案在 \(1e18\) 之内。

开始看错范围 \(TLE\) 了一发，暴力做的话，答案显然是指数级增长的，考虑当前数字的二进制状态，如果向左走就是加上一个 \(0\) ，向右就是加上一个 \(1\) ，向上就是减少一位，最后把二进制转成十进制，于是线性复杂度解决问题。

E题 Edge Deletion

给定一个 \(n\) 个点，\(m\) 条边的简单无向图，在不影响任意两个点的最短路长度的情况下删去最多的边，求这个边数

\(2\le n\le 300\)

我开始的想法是建出最短路径树，不过并不是很可做？

对每条边分别考虑，假设当前边连接 \((s,t)\) ，长度是 \(w\) ，如果存在另一条不同的 \(s\) 到 \(t\) 的路径，且该路径长度 \(\le w\)，那么这条边删去，对当前的最短路长度无影响，对于其他点，由于这条边并不是 \((s,t)\) 间的最短路，所以其他需要经过 \(s\) 或 \(t\) 的最短路也不会经过这条边，所以对任意两点的最短路长度均无影响，可以删去，于是只需要 \(floyd\) 求出全源最短路，然后对于每条边，枚举除了边的端点以外的其他点，看是否存在这样一条其他路径即可。

F题 Lottery

还不会 \(/qd\) ，是个概率 \(DP\) ，但感觉是个很普适的模型？

G题 Sqrt

给定一个数 \(X\) ，可以在 $[1,\lfloor { \sqrt{X} }\rfloor ] $ 中选择一个数接在当前数的后面，依此类推进行无限次，求最后能得到多少种不同的数列。

\(1\le X\le9e18\)

你发现最后肯定开平方开到 \(1\) 去。

显然的做法，设 \(f_i\) 是数字 \(i\) 能形成的不同数列个数，那么 \(f_i=\sum_{j=1}^{\lfloor { \sqrt{X} }\rfloor}{f_j}\) 。

\(O(\sqrt{X})\) 的做法，肯定超时。

注意一个性质，\(\sqrt{1},\sqrt{2},...,\sqrt{X}\) （都要下取整）中，只会有大约 \(X^\frac{1}{4}\) 种不同的数。

也就是说，之前的暴力 \(DP\) ，计算了很多重复状态，那么直接枚举 \(X\) 的子二代（就是把X需要的\(\sqrt{1},\sqrt{2},...,\sqrt{X}\) ，再用暴力 \(DP\) 拆一次得到的那些数），考虑当前枚举到 \(i\) ,那么在子一代中，\([i^2,/sqrt{X}]\) 这些数字都会包含 \(i\) 的计算项，于是 \(i\) 对应的方案 \(f_i\) 对总答案贡献 \(\sqrt{x}-i^2+1\) 次。

方程显然，只需要枚举到 \(X^\frac{1}{4}\) 即可，可以通过。

EX题 Builder Takahashi (Enhanced version)

还不会，是个 \(min-max\) 容斥。