Contest Info

date: 2019.03.25 19:08-24:08

practice link

Solutions

A. Array

题目大意：给你一个数组 \(a_1,a_2,\dots, a_n\)，让你至多将一个数字 \(a_x\) 变为 \(y\)，假设变化后的数组为 \(b_1,b_2,\dots, b_n\)。最小化 \(|a_x-y|+\sum\limits_{k=1}^nk\cdot c_k\)，其中 \(c_k\) 表示前 \(k\) 个位置的不同数种数。

题解：每种数第一次出现的位置会做贡献。枚举这些位置，考虑它变成前面某一种或者后面某一种数的贡献，用树状数组维护前缀最小值即可。

C. Cut the Plane

题目大意：平面上有 \(n\) 个点，任意三点不共线。要求你用恰 \(\lceil\frac{n}{2}\rceil\) 条直线分割这些点，使得任意两点不在同一个区域内，且每条直线不过任何一个点。每条直线要求用它上面的两个整点表示。

题解：首先用一条直线将这 \(n\) 个点分成均匀的两部分，方法如下：

以左下角的点为极点进行极角排序，如图 \(1\)（\(A,B,C,D,E\) 是原有的点），考虑用一条直线将极点 \(A\) 和极角序大的 \(B,C\) 分为一边，极角序小的 \(D,E\) 分为一边。

我们定义 \(C\) 为“中间点”，将 \(AC\) 延长一倍至 \(F\)，再以 \(F\) 为极点，找出除 \(A,C\) 外与 \(FA\) 夹角最小的点。若该点在 \(DE\) 一侧（如图 \(1\) 的 \(D\)），那么将 \(D\) 反向延长 \(FC\) 至 \(G\)，\(FG\) 即为所求。若该点在 \(BC\) 一侧（如图 \(2\) 的 \(B\)），那么将 \(B\) 延长 \(CF\) 至 \(G\)，\(FG\) 即为所求。

之后不妨设这条直线为 \(x\) 轴。每次我们分别找出上下两侧最左（最右也一样）的各一个点，使得它们连线的左（右）侧没有任何其它的点。这样的两个点只需要求一个凸包，凸包上跨越直线的边即为所求。之后再画一条直线将这两个点和其它点分开即可。为了画出不经过任何点的“整”直线，需要利用类似上一段的技巧。

D. Edges Counting

题目大意：定义一个简单无向图是好的，当且仅当它的每个连通块至多只有一个环。求所有带标号的 \(n\) 个点的好图的环的大小之和。

题解：先求 \(n\) 个点的连通好图的数量，之后就可以用一个简单的 \(\mathcal{O}(n^{2})\) dp 得到答案。

首先没有环的方案有 \(n^{n-2}\) 种。假设我们已经知道环的大小，设为 \(k\)，那么我们把这个环删去，再将环上的每个点和一个新增的 \(0\) 号点连边，就可以得到一棵大小为 \(n+1\) 的树，其中 \(0\) 号点的度为 \(k\)。这个方案很容易用 Prüfer 序列计算。

F. Fighting Against Monsters

题目大意：一个人和三只怪战斗，设怪为 \(A,B,C\)。每只怪有一个血量和一个攻击力，其中 \(hp_{A},hp_{B}\le100,hp_{C}\le10^{18}\)。第 \(i\) 回合，每只活着的怪会给人造成它攻击力的伤害，然后这个人可以选一只活着的怪，给它造成 \(i\) 的伤害。问最优策略下这个人最少受到多少点伤害。

题解：注意到第 \(100\) 回合后，\(A,B\) 都会被秒杀，容易证明此时只要开始攻击 \(C\)，就会一直把它打死，否则不会更优。

因此我们可以对前 \(100\) 回合 dp，后面枚举 \(A,B,C\) 被打死的顺序即可。

I. Counting Polygons

题目大意：定义一个长度为 \(m\) 的序列合法，当且仅当这个序列是某个周长为 \(n\) 的凸多边形的边长序列，两个合法的序列同构，当且仅当它们可以被表示成同一个凸多边形（可以旋转或翻转）的边长序列。问不同构的合法序列有多少个。

题解：合法当且仅当每条边的长度 \(\le\lfloor\frac{n-1}{2}\rfloor\)。使用 burnside 引理加容斥计数即可，需要注意各种 case。

时间复杂度 \(\mathcal{O}(\sigma(m))\)。

K. Three Dimensions

题目大意：给出 \(m_{x_{a}},m_{x_{b}},m_{y_{a}},m_{y_{b}},m_{z_{a}},m_{z_{b}}\)，然后有 \(x_{a}\in[0,m_{x_{a}}]\cap\mathbb{Z}\)，\(x_{b},y_{a},y_{b},z_{a},z_{b}\) 也同理。

求所有的 \(\max\{|x_{a}-x_{b}|,|y_{a}-y_{b}|,|z_{a}-z_{b}|\}\oplus x_{a}\oplus x_{b}\oplus y_{a}\oplus y_{b}\oplus z_{a}\oplus z_{b}\) 的和。

题解：数位 \(dp\)。我们只需要记录如下的状态：

• \(x_{a}-x_{b},y_{a}-y_{b},z_{a}-z_{b}\) 分别的符号，正、零或负
• \(|x_{a}-x_{b}|,|y_{a}-y_{b}|,|z_{a}-z_{b}|\) 分别是否是最大值
• \(|x_{a}-x_{b}|,|y_{a}-y_{b}|,|z_{a}-z_{b}|\) 在计算时分别是否要被下一位借位
• \(x_{a},x_{b},y_{a},y_{b},z_{a},z_{b}\) 分别和 \(m_{?}\) 相等还是已经小于 \(m_{?}\)

这样就可以从高位向低位 \(dp\) 了，转移不难，不过不是很好写。