10.25 闲话

日寄

上午考模拟赛，wangk：“这次的难度已经不能再简单了。”

但这不影响我切不了 T2，做不出 T4。

下午随了几道性质题，发现最近特别爱做性质题，这不好，太久处于舒适圈容易懈怠，明天开始做大模拟。

今天不推歌。

口题解

CF938D Buy a Ticket

建图的时候就可以把边权记为二倍。把所有点按票价排序，影响顺序一定是票价小的点会影响票价大的，故按票价从小到大尝试向周围拓展，其过程类似最短路。

AT_abc295_g Minimum Reachable City

题意为在一棵祖先编号严格小于后代的树上给出若干返祖边，询问点能到达的最浅祖先。将返祖边拆分，视为若干条子结点向父结点的连边，用并查集维护每个点向上能到达的最浅点即可。

CF74C Chessboard Billiard

虽然是一个绿题，但有一个相当牛*的性质。

从一个正方形出发考虑，一个正方形中能放置的球数等于其边长，将每个球的轨迹染色，发现正方形上下两边缘颜色序列正好相反，左右两边缘也相反。于是可以复制一个正方形，将其上下颠倒，并用其上边缘重合已有正方形的下边缘，得到一个矩形，以此类推，发现一个长 \((n-1)x+1\)，宽 \(n\) 的矩形，可以放置的球数和边长为 \(n\) 的正方形相同。同理拓展左右边缘，得到结论：

一个长 \((n-1)x+1\)，宽 \((n-1)y+1\) 的矩形，可以放置的球数和边长为 \(n\) 的正方形相同。

那么对于一个长为 \(n\)，宽为 \(m\) 的矩形，其可以放置的球数即 \(\gcd(n-1,m-1)+1\)。