简单题不写了。

USACO24JAN Cowlendar S

有点意思，不会做。

直接枚举的话是 $O(nV)$ 的，考虑把枚举 $L$ 的次数。

但是，如果我们可以找到一个 $L$ 使两个不同的数模数一样且不希望模数数量增加，那么就只能找其因子。

考虑去重，找最大的四个数然后根据鸽巢原理，至少有两个数 $a_i,a_j$ 在模 $L$ 意义下是一样的。

所以找到这个 $a_i,a_j$ 然后就得到了 $L\mid abs(a_i-a_j)$。

枚举其因子就行了，时间复杂度为 $O(n\sqrt V\log \sqrt V)$。

USACO24DEC Deforestation S

一个比较有用的 trick。

容易得到差分约束：

$\begin{aligned} \left\{\begin{matrix} s_i\le s_{i-1}\le s_i+1\\ s_{r_i}-s_{l_i-1}\ge d_i\end{matrix}\right. \end{aligned}$

那么就有：

$i\xleftarrow{0} i-1,i-1\xleftarrow{1}i$

$l_i-1\xleftarrow{-d_i} r_i$

但是这样写 spfa 会被曹飞，考虑进行简单的转化，具体的对空位进行考虑得到：

$s_{r_i}-s_{l_i-1}\le r_i-l_i+1-d_i$

那么就是：

$r_i\xleftarrow{r_i-l_i+1-d_i}l_i-1$

于是写 dij 就行了，顺手学习了一下怎么卡 spfa。

POI 2012 HUR-Warehouse Store

贪心全部忘了。

能服务就使劲服务。

否则如果把以前服务的最亏的人拿出来跟现在换更优，那么就换。

国家集训队 种树

感觉可以 DP，考虑贪心。

显然会遇到直接贪然后两边加一起更优的情况，那么我们把一个位置出队之后把 $v_{i-1}+v_{i+1}-v_i$ 放进去，这样如果选了就相当于反悔了。

把前后曹飞，哪个双向链表搞一下就行了。

AGC018 f 两棵树

很神秘一个题目，以前写了现在忘了。

首先因为所有的节点的子树中权值的和都是 $1,-1$ 那么，有如果两棵树中节点的儿子（不是子树大小）数量不一样，那么显然是无解的。

因为一个 $1,-1$ 都会改变和的奇偶性，所以要上面的条件是必要的。

换而言之，如果我们确定了叶子节点，那么整棵树的 $X$ 就都确定了。

看到度的奇偶性，有一个天才的想法就是去考虑欧拉回路。

那么把奇数的点对应连起来，这样就我就有一个所有点的度数都是偶数的图了。

如果一条后连的边的从左向右的，那么把权值赋值成 $1$，反之为 $-1$。

那么跑出一个欧拉回路，把回路拆爆成一堆环，有三类：

• 某个节点往儿子走，然后从儿子或自己的横叉边回来；
• 某个节点往儿子走，然后从父亲回来；
• 某个节点往横叉边/父亲走，然后从父亲/横叉边回来。

因为后面两种都要经过父亲到自己的边，所以只能存在一条。

因为第一种，在自己的子树里既有 $1$ 也有 $-1$，所以是没有贡献产生的。

对于后面两种，都会吃到一个在子树里的贡献，所以这个子树的和就是 $1$ 或者 $-1$ 了。

于是做完了。

【UR 2】跳蚤公路

类似于地铁，因为所有的路径都可以写成 $kx+b$ 的形式，所以我们二分得到一个 $x$。

如果不存在负环，那么很好我们直接继续。

否则随便找出一个负环，计算这个负环的 $k$ 的值，然后按照 $k$ 的关系继续限制 $x$。

https://www.luogu.com.cn/article/cfuugfja