[2024 AtCoder 比赛历程]

2024.1.20 ABC 337-G

题目大意：给定一棵树，对于树上的每个点$u$，定义 $f[u]$ 表示满足点 $w$ 在点 $u$ 到点 $v$ 的路径中，且 $w>v$ 的点对 $(w,v)$ 的数量。 $u$ 可以等于 $w$ 。

解法：比赛时先考虑将一个点钦定为 $w$ 时，该点对其他点的贡献。发现对于一个点，它可以通过它的一个子树内比它要小的点，贡献到除这棵子树以外的所有点（子树包含“向上”的）。于是思考如何快速计算以某个点为根的子树中，有多少个点的编号小于某个点。比赛时想到用个可持久化线段树……但当然打不出来，赛后经过 lym 的启发，发现只用普通的树状数组就行了。我们只需要将树上的点从小到大加入，同时贡献。这样就避免了会统计到不该统计的点的问题。

2024.1.28 ABC 338-D

题目大意：给定一个长度为 $n$ 的环，以及一个长度为 $m$ 的序列，现在需要在这个环上断掉一条边，问在最佳情况下，顺次走完(可以重复)序列中每一个点所需经过的最小边数。

解法：比赛中的做法不知道为什么一直炸，炸的还挺离谱。考虑枚举断掉的边然后计算贡献。对于序列中相邻的两个数，设小的为 $a$ ,大的为 $b$ 。若断掉的边在 $a$ 至 $b$ 的路径上，则贡献为 $n-(b-a)$ ；反之则在 $b$ 至 $a$ 的路径上的贡献加上 $b-a$ (表示选另外的一条路)。然后用差分做就可以了。

2024.1.28 ABC 338-F

题目大意：给定一张 $n$ 个点、 $m$ 条边的有向图(n<=20)，每条有向边有一个权值 $w[i]$ ($-10^{6}\le w[i]\le 10^{6}$),问从任意一个点出发，经过所有点的最小的边权和，点和边可以重复经过。

解法：考虑最终的答案是由若干条从点 $x$ 到点 $y$ 的最短路径构成的。所以先处理出每两个点直接的最短路，然后进行转移。

注意事项：在有负边权的图中判断无解，需要考虑有可能一个点沿着一些负边移动的情况

不要乱用short

ARC 148-D

这题显然不是在比赛的时候做的。WC的时候题目选讲中的题目，但是是很好的博弈论。

题目大意：给定 $2n$ 个数，$A$ 和 $B$ 轮流取数，取完后计算 $A$ 取的数的和与 $B$ 取的数的和在$\mod m$ 意义下是否相等，如果不相等，则 $A$ 获胜；否则 $B$ 获胜。

解法：考虑最后只剩两个数的情况，发现只有最后的两个数$a$、$b$ 满足$a-b=b-a(\mod m)$ 时，$A$ 无论取哪个数的结果都是一样的。所以我们可以把满足 $a=b$ 或 $a=b+m/2(\mod m)$ 两两配对。接着我们发现，对于 $a=b+m/2(\mod m)$ 的数对，需要满足其有偶数个，$B$ 才能获胜。所以我们总结一下 $B$ 获胜的条件：需要有若干个满足 $a=b$ 的数对和偶数个满足 $a=b+m/2(\mod m)$ 的数对。