2024“钉耙编程”中国大学生算法设计超级联赛（5）

我草真唐氏了啊，红温下机。。。

你说的对，但是我在世末农庄里找到了一块数表上面有树论一和树论二我只能用心感受三同时开关灯之后有猫咪军团在猫咪们狂欢它们在玩猫罐头游戏送了我一个Array-Gift里面有一个捆绑魔方但我想吃串串，但这就是飞行棋。

Problems	AC
7481. 数表（二）
7482. Array-Gift	⊕
7483. 捆绑魔方	大模拟，弃疗
7484. 树论（一）	⊕
7485. 树论（二）	⊕
7486. 猫罐头游戏	○
7487. 猫咪军团
7488. 猫咪们狂欢	⊕
7489. 用心感受（三）	杜教筛 弃疗
7490. 世末农庄	待补
7491. 开关灯	○
7492. 串串	sam 弃疗
7493. 飞行棋	○

Code Repo

1002 Array-Gift

红温罪魁祸首。操作肯定就是 n, n - 1, n + 1 三种。

写代码的时候对于 n 那种情况，枚举 ai mod aj，忘记判断 aj mod x 也要等于 0 了，糖丸了。。。。。。。。。。。。

1004 树论（一）

树，LCA，猜结论，数据结构

Fun Fact: std 的 LCA 写假了，但是数据满足儿子节点编号大于父亲，所以 ans 是对的

赛时不会做，以为又是什么 DSU on Tree / 线段树合并。。。不会。

看起来可能是个经典 trick 了，（至少看起来就很典的样子

$$
\sum_{i=1}^n \sum_{j=1}^n[\operatorname{lcm}(i, j) \leq n]=O\left(n \log ^2 n\right)
$$

也就是说，这个点对数量其实是有限的，n = 1e5 的时候大概是 2e6 对。

这时候就醍醐灌顶了。。。。。。。。。。。

你把这些点对预处理出来，按照 lcm 排序。然后把询问离线下来。用双指针把 点对的贡献打到 lca 上面。单点修改区间查询，树状数组做完了。

1005 树论（二）

树，数据结构，并查集，数论，调和级数

感觉很秒的一个题

赛时一直在想删边分成两个点集到底怎么搞。其实这就相当于，对于两个点，把他们的 gcd 赋给路径上的边。

求最大就是每条边把所有能赋给他的值里面取 max。暴力的想法就是枚举一个 d，然后把 d 的倍数这些点取出来，建个虚树，然后路径赋值 max 对吧。那你想，你可以改变枚举顺序，从大到小枚举 d，这样一条边只会被赋值 1 次。对于那些已经赋值过的边，我们就不用管了，我们每次就是在一个集合里面找一些边，然后赋值，然后扔到另外一个不用管的集合里面，这个过程是可以用并查集实现的！

1006 猫罐头游戏

最终的局面必然是 1 1 1。

直觉会发现这是个和奇偶性有关的游戏。

接下来用 0 表示偶数，1 表示奇数。

一个 1 只能被分成 1 和 0，一个 0 可以被分成 1 和 1 or 0 和 0 （除非这个 0 是 2 的话只能分成 1 1）

0 1 1 或者 1 0 0 都可以转移到 1 1 1，但是 1 1 1 只能转移到 1 1 0。

所以 1 1 1 是个必败态。0 1 1 和 1 1 0 都是必胜态。

那么 0 0 0 呢？0 0 0 只能转移到 0 0 0 或者 0 1 1。但是 0 1 1 必胜，所以双方会一直转移到 0 0 0，直到转移不下去，必须转移到 0 1 1 了（也就是出现 2 了）。

1008 猫咪们狂欢

网络流

哈哈，又是不会 Flow 的一天。警钟敲烂

首先 Flow 的内容忘的差不多了。之前学的时候也没做什么题让大脑 over-fit 到 Flow。

这是个 最大权闭合子图 模型，详见 P1361 小M的作物。

这个题相当于是说，给你 n 个物品，有 m 个 rule (u_i, v_i)。对于一个 rule，如果你将 u 和 v 同时放入第一个集合可以获得 w1 的价值，同时放入第二个集合则可以获得 w2 的价值。求最大价值。

我们要做的就是划分这 n 个点成两个集合

我们这样建图：

• 对于第 i 个限制 $(u_i, v_i)$，建立虚拟点 $i_1$ $i_2$ 分别代表放入第一/第二个集合
• $S$ 向 $i_1$ 连边，容量为 $w_1$；$i_2$ 向 $T$ 连边，容量为 $w_2$
• $i_1$ 向 $u_i$, $v_i$ 连边，容量 $inf$；$u_i$, $v_i$ 向 $i_2$ 连边，容量 $inf$

在这个图上面跑最小割，容量为 inf 的边不会被割掉。如果 (S, i1) 被 cut 了，相当于放到第一个集合里面。如果 (i2, T) 被 cut 了，相当于放到第二个集合里面。

1011 开关灯

打表。证明详见题解

1013 飞行棋

当你在 0 的时候，直接到终点的概率是 $\frac{1}{n}$，否则，你会有 $\frac{n - 1}{n}$ 的概率进入 [1, n - 1] 这个区间。

进入这个区间以后，每花费 1 代价，你要么是直接进入终点 $\frac{1}{n}$，要么是 roll 到 n 了，用赠送的机会进入终点 $\frac{1}{n} \times \frac{1}{n - 1}$。$\frac{1}{n} + \frac{1}{n} \times \frac{1}{n - 1} = \frac{1}{n - 1}$。不然的话其实你还是必然留在这个区间里面。那么这里期望花费的代价就是 n - 1。

所以答案就是

$$
\frac{1}{n} \times 1 + \frac{n - 1}{n} \times (1 + (n - 1)) = \frac{1}{n} + n - 1
$$