2024 ICPC Asia Pacific Championship 部分题解

感觉为了方便讲课的时候找题是该记录一下题解了。

比赛链接：2024 ICPC Asia Pacific Championship - Online Mirror

B. Attraction Score

题意

给定一张 $n$ 个点 $m$ 条边的无向平面图，边有边权。你要选出一个点集，点集的价值如下计算：

• 对于每一对点，如果它们之间有边相连，那么价值加上这条边的边权；
• 记没有边相连的点对的数量为 $x$，那么价值减去 $10^6 x^2$。

选出一个点集使得价值最大。

$n\leq 10^5, m\leq 3 \times 10^5$。边权 $w_i\leq 10^6$。6s。

题解

首先注意到，缺少的边会有很大的惩罚；而平面图的边数被 $3n-6$ 限制住，因此点数不可能很大。

另一方面，我们知道，平面图最小度数一定 $\leq 5$。从而每次枚举图中度数最小的点，处理与这个点相关的形状，然后删除这个点，可以确保复杂度。

下面我们分析各种可能的图的形态：

• 1 个点：价值为 0。
• 2 个点：一定有 1 条边。
• 3 个点：一定有 3 条边（否则去掉那个度数为 1 的点，减少 1 条边，减少 1 份惩罚，更优）。 确定中心点后，枚举从其邻居中选出 2 个点的方案，检查那两个点之间是否有边。从而可以找到所有三角形。
• 4 个点：
  • 有 6 条边（$C_4$）：确定中心点后，枚举 3 个邻居。
  • 有 5 条边：其形态相当于两个有公共边的三角形；在枚举三角形的时候，记录每条边对应了哪些三角形，之后枚举每条边，取权值最大和次大的与之关联的三角形。
  • 若只有 4 条边，去掉度数为 2 的点，减少 2 条边，减少 3 份惩罚，更优。
• 5 个点：
  • 有 9 条边：其形态相当于两个有公共三角形的 $C_4$。枚举所有 $C_4$ 的时候，记录每个三角形对应了哪些 $C_4$。之后枚举每个三角形，取权值最大和次大（其实本来就最多有两个）的与之关联的 $C_4$。
  • 若只有 8 条边，去掉度数为 3 的点，减少 3 条边，减少 3 份惩罚，更优。
• 若 6 个点，即使有 12 条边，也可以去掉度数为 4 的点，减少 4 条边，减少 5 份惩罚，更优。
• 若 7 个点，即使有 15 条边，权值也为负数。点数不可能更多。

通过上述方法枚举所有可能的图形态，容易写出在 $O(n \log n)$ 的代码（还有很多 $5\choose 3$ 之类的常数）。

C. Bit Counting Sequence

题意

给定一个序列 $a_{0..n-1}$，求最小的 $x$，使得 $a_i = \text{popcount}(x×i)$ 对所有 $i$ 成立。$n\leq 3 \times 10^5$，$a_i\leq 60$。

题解

找到其中 $a_i$ 下降最剧烈的一个位置，这一次变化一定是 $111\cdots 101\cdots 111$ 变为 $111\cdots 100\cdots 000$。以此为基础推出 $x$ 并逐个验证即可。

E. Duplicates

题意

给定一个 $n \times n$，值域为 $1\sim n$ 的网格。改动尽可能少的数，使得每一行每一列的数都不要各不相同。$n\leq 100$。

题解

先找到所有数互不相同的行、列。不妨设行比列少，分别有 $r$ 行和 $c$ 列。

• 首先对于前 $r$ 个行、列的交点（$r$ 个），每个数换成一个不同的数即可。
• 如果剩 0 列，那么结束。
• 如果剩 1 列 $j$，那么找到某一行 $k$，第 $k$ 行存在一个数与 $a_{k,j}$ 不同，把 $a_{k,j}$ 换成那个数即可。这样的数一定存在，否则每一列都与第 $j$ 列相同了。
• 如果剩多列，则把这些列的第一行都换成一个一致的、与之前的数不同的数即可。

F. Forming Groups

题意

给定一个序列 $a_{1..n}$，你可以把 $a_1$ 插入到后面的任意位置，然后选择一个 $k|n$，把序列按照下标模 $k$ 分成 $\frac{n}{k}$ 组。每一组的权值为这一组的元素之和，最小化【最大权值除以最小权值】。$n\leq 10^6$。5s。

题解

首先，若 $k_1|k_2$，则 $k_1$ 一定不劣于 $k_2$。因为将每组进一步细分成 $x$ 组时，原本最大的一组细分出的最大组一定大于等于原权值的 $1/x$，而最小的一组细分出的最小组一定小于等于原权值的 $1/x$，从而比值不会变小。从而 $k$ 只需要枚举 $n$ 的质因子即可。

直接枚举 $a_1$ 插入的位置，每次 $a_1$ 后移一位只会影响两组，从而用 set 维护每一组的权值即可。