XIX Open Cup named after E.V. Pankratiev. Grand Prix of China, Division 1

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\) 分为一边。

图 1

\(1\)

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

图 2

\(2\)

之后不妨设这条直线为 \(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\) 了,转移不难,不过不是很好写。