526互联

Codeforces Global Round 14

发布时间 2023-07-09 21:58:37作者: Gemini7X

这场貌似很典很好啊。

A. Phoenix and Gold

给定一个长度为 $ n $ 的数组 $ w $ 和一个数 $ x $，数组中的数各不相同，要求重新排列这个数组，使得对于每一个 $ i $ $ (1 \le i \le n) $，都有 $ \sum\limits_{j = 1}^{i}w_j \ne x $。

从小到大排序，如果存在 \(i\) 使得数列不满足条件那这样的 \(i\) 一定只有一个，如果 \(i\) 不在最后，直接和最大值交换位置即可。否则显然无解。

B. Phoenix and Puzzle

输入一个数 $ n (1 \le n \le 10^9) $，求能否使用 $ n $ 个全等的等腰直角三角形来拼成一个正方形。要求每个三角形都必须使用。

好像除了样例给出的两种拼法外别无他法，于是只用判断除以 \(2\) 或者 \(4\) 是否是完全平方数即可。

C. Phoenix and Towers

凤凰菲克斯有 $ n $ 个方块，分别高 $ h_1,h2,\dots,h_n $，所有 $ h_i $ 都不超过 $ x $ 。他计划将 $ n $ 个方块堆叠成 $ m $ 座塔。为了让塔看起来更漂亮，没有两座塔的高度差可以超过 $ x $ 。

请帮助菲克斯建造 $ m $ 座漂亮的塔，每个塔必须至少由一个方块构成，并且必须使用所有方块。

一个很自然的想法是小的和大的匹配去平衡这个高度。试一下发现确实可以。那么容易得出下面的做法：

给所有方块排序，取前 \(2m\) 个，第 \(i\) 小和第 \(2m-i+1\) 小匹配。然后我们给 \(m\) 个塔全部减去最小值，变成新的方块，其还满足高度 \(\le x\)。再做刚才的事情，复杂度线性对数。直到不足 \(2m\) 个停止这个过程。

一个等价的实现，维护 \(m\) 个塔，每次取出 \(m\) 个块，然后倒着加进去。

D. Phoenix and Socks

Phoenix 有 \(n\) 只袜子（保证 \(n\) 为偶数），其中前 \(l\) 只左袜子，后面 \(r\) 只右袜子，\(l+r=n\)。每只袜子有颜色 \(c_i\) （\(1 \le c_i \le n\)） 。

现在你有三个操作，每个操作代价为 \(1\)：

1.将某只袜子颜色换为 \(c'\)。

2.将左袜子变为右袜子

3.将右袜子变为左袜子

求使所有袜子匹配成 \(\frac n2\) 对袜子（即，颜色相同，且左右袜子各一）的代价。\(1\le n\le 2\times 10^5\)。

注意没双袜子不需要左前右后。

先把每种颜色的左右袜子配对。思考只有颜色不同，类型相同时需要两步，尽量不要用这种。于是优先匹配颜色不同，类型不同的袜子。而颜色相同类型相同的袜子也可以只要一步，所以优先把不同颜色袜子都搞成偶数最好。

E. Phoenix and Computers

给定 \(n\)，\(M\)。你有 \(n\) 台电脑排成一排，你需要依次开启所有电脑。

你可以手动开启一台电脑。在任意时刻，若电脑 \(i-1\) 与电脑 \(i+1\) 都已经开启 \((1<i<n)\)，电脑 \(i\) 将立刻被自动开启。你不能再开启已经开启的电脑。

求你有多少种开启电脑的方案。两个方案不同当且仅当你手动开启的电脑的集合不同，或是手动开启电脑的顺序不同。答案对 \(M\) 取模。

先思考什么样的集合合法？首先 \(1\) 和 \(n\) 必须手动打开，两个手动打开的电脑之间不能有超过 \(1\) 台没有打开的电脑。思考对于一个连续段的方案数，根据样例的提示，只能是手动打开中间的一个，然后往两边扩展。

直接算似乎没什么办法，还是得递推，设左边需要 \(i\) 步，右边需要 \(j\) 的方案数是 \(f_{i,j}\)，似乎有很简单的递推式 \(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)。而边界条件是 \(f_{i,0}=f_{0,i}=1\)。可以格路计数但是这题不需要。

然后长度为 \(n\) 的连续段就可以 \(O(n)\) 计算了。考虑对整个序列 dp，需要记录已经放了多少个，然后在枚举这一步放了多少个即可复杂度 \(O(n^3)\)。

F. Phoenix and Earthquake

给定一张 \(n\) 个点 \(m\) 条边的无向连通图和正整数 \(x\)，点有非负权值 \(a_i\)。

如果一条边 \((u,v)\) 满足 \(a_u+a_v \ge x\)，可以将 \(u,v\) 缩起来，新点的点权为 \(a_u+a_v-x\)。

判断这张图是否可以缩成一个点。如果是，还要输出每次缩的是哪条边。

\(2 \le n \le 3 \cdot 10^5,n - 1 \le m \le 3 \cdot 10^5,1 \le x \le 10^9,0 \le a_i \le 10^9\)

靠又忘记了这种题怎么做了。

先找找反例，合并至少发生 \(n-1\) 次，所以如果 \(\sum a_i<(n-1)x\)，那么一定不行。看到 \(n-1\)，想到树的情况。或者看到一张图就应该想到合并一棵生成树即可。

然后，这不是和 NOI2020 制作菜品 一模一样吗？

G. Phoenix and Odometers

给定一张 \(n\) 个点 \(m\) 条边的有向图，有边权，进行 \(q\) 次询问（\(n,m,q\le 2\times 10^5\)，边权为不超过 \(10^9\) 的正整数）。

每次询问给定三个参数 \(v,s,t(0\le s<t\le 10^9)\)，你需要回答是否存在一条起点终点均为 \(v\) 的路径，满足 \(\text{路径长}+s\equiv 0\pmod t\)。

就是对 scc 进行处理，你可以走若干个环，根据 bezout 定理，就是求所有环和 \(t\) 的 \(\gcd\) 是不是整除 \(s'\)。而在 scc 中环长有一个经典结论就是你只用处理横叉和返祖边，理由是辗转相见。