CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Codeforces Round #639 (Div. 1) (Unrated) ======

====== [A] Hilbert's Hotel======

===== 题意 =====

给一个映射：$k\to k+a_{k\bmod n}, \forall k\in \mathbb{Z}$。

问这个映射是否是 $\mathbb{Z}\to\mathbb{Z}$ 的一一映射。

$1\le n\le 2\cdot 10^5$，$|a_i|\le 10^9$。

多组数据。

===== 解法 =====

其实这个就很简单，你考虑把 $0$ 到 $n-1$ 的数加上对应的 $a_i$，然后把它们模 $n$，看看模完的余数是不是恰好 $0$ 到 $n-1$ 都有就行了。

为什么模完之后有数字没有就不是一一映射？

考虑原来有 $n$ 个数，变换（加上模掉）之后如果 $0$ 到 $n-1$ 之间有不存在的，那么变换后数少于 $n$ 个，根据抽屉原理必有两个的余数撞了车。

不妨设这两个原来分别为 $x, y$，这里 $x, y\in [0, n-1]$。

撞车的意思就是说 $x+a_x\equiv y+a_y\pmod{n}$

也就是说 $\exists k\in \mathbb{Z}, \quad x+a_x+kn=y+a_y$。

那么你可能会说其实 $x+a_x\neq y+a_y$ 是可能的，为什么不是一一映射呢？

要注意我们的定义域是 $\mathbb{Z}$，如果说 $\exists k\in \mathbb{Z}, \quad x+a_x+kn=y+a_y$，那么我令 $z=x+kn$，就有：

$y+a_y=(x+kn)+a_x=z+a_{z\bmod n}$

那么就是存在一个 $z$，他和 $y$ 经过加上 $a_i$ 的变换之后变换到了恰好同一个位置上，那么就不是一一映射了。

可能到这里你以为这个题就做完了（其实第一行就可以做完了），但其实我们没有证明这个判据的充分性。为什么取出 $0$ 到 $n-1$ 执行操作并取模之后，结果依旧是 $n$ 个互异的数时，原映射一定是一一映射呢？

其实这很简单。

我们考虑将 $\mathbb{Z}$ 中的元素按照模 $n$ 的余数划分成 $n$ 个等价类，分别叫做 $\mathbb{Z}_0, \mathbb{Z}_1,\ldots, \mathbb{Z}_{n-1}$。

然后我们考虑在同一个等价类内的元素，比如考虑 $\mathbb{Z}_i$。

这里面的元素有：$\{\ldots, -2n+i, -n+i, i, n+i, 2n+i, \ldots\}$

根据变换规则我们把它们套进那个映射之后，这些元素会被映射到：

$\{\ldots, -2n+i+a_i, -n+i+a_i, i+a_i, n+i+a_i, 2n+i+a_i, \ldots\}$

可以看出整个类里的元素的偏移量相等，都是 $a_i$。

那么这些元素模 $n$ 的余数依旧全部相等，且等于 $(i+a_i)\bmod n$。

那么如果对所有的 $i\in [0, n-1]$，$(i+a_i)\bmod n$ 互异，就可以保证原映射是一个一一映射。

====== [B] Monopole Magnets ======

这个题当时场上想了快一个小时。感觉状态好差啊，不会做结论题，难受。

===== 题意 =====

给无限个单极磁铁和一张地图，你每步操作可以选一对异名磁铁，如果它俩在同一行或者同一列，那么 N 向 S 移动一格。如果两者重叠什么都不会发生。

地图上的格子有黑白之分。你的任务就是在地图上放置 N 磁铁和 S 磁铁，构成初始状态，使其满足：

  * 所有黑色的格子，经过某些恰当操作后，都能有一块 N 磁铁在其中；
  * 所有白色的格子，无论经过怎样的操作，都不可能有 N 磁铁在其中。
  * 每行每列均至少有一个 S 磁铁。

求出你所需要的 N 磁铁的最少数量。

无解输出 -1。

$1\le n, m\le 1000$

===== 解法 =====

这个题是个结论题。首先给出结论：

如果同一行或者同一列上有两段连续的黑格子，中间由白格子隔开，那么无解；

如果有全白的行，却无全白的列，或者有全白的列，却无全白的行，那么无解。

否则答案是地图中黑格子的连通分量个数。这里连通是四个方向上的连通。

至于证明，这里先摸了，有时间来补，今晚还有 ddl，我人没了，摸了摸了。

====== [C] Quantifier Question ======

这个题啊，非常鬼鬼。最近离散题莫名多？场上写完交了，然后没注意细节，同时 queue 巨长无比，被 pretest 叉爆了，难受啊。

===== 题意 =====

给一个不确定的合式公式：

$Q_1x_1Q_2x_2\ldots Q_nx_n((x_{j_1}<x_{k_1})\land (x_{j_2}<x_{k_2})\land\cdots\land (x_{j_m}<x_{k_m}))$

其中 $Q_i$ 是全称量词或特称量词。

给定解释 $D$ 如下：

  * $D^I=\mathbb{R}$
  * $a<b:=\begin{cases}0, &\mathrm{if}\; a\; \mathrm{is\;greater\;than\;or\;equal\;to}\; b\\1, &\mathrm{if}\; a\; \mathrm{is\;smaller\;than}\; b \end{cases}$

题目输入 $n, m, \{j_m\}, \{k_m\}$，问若该公式在解释 $D$ 下为真，则 $Q_1, \ldots, Q_n$ 之中至多能有多少个是全称量词。

$2\le n\le 10^5, 1\le m\le 10^5$。

===== 解法 =====

这个题我们直接把 $x_{j_i}<x_{k_i}$ 建模成图里的一条有向边，先判环，如果有环那么无解。

接下来，我们直接贪心地由外到内设置全称量词即可。

一个量词被设置之后，其对应的变元在图中递归前驱可遍历到的所有结点对应的变元对应的量词均只能为特称量词。

这个东西我们直接打个标记就行了。

这边有点教训，回头再来总结。

====== [D] Résumé Review ======

这个题我场上一眼看出来怎么做了，然后没时间写了，很 GG。当时网络波动和评测障碍特别大，也不怎么想打了，就扔了，回头补。

===== 题意 =====

大致就是给定数列 $\{a_n\}$，给定 $\displaystyle K=\sum_{i=1}^{n}b_i$，限制 $0\le b_i\le a_i, b_i\in \mathbb{N}$，要求最大化：

$$\displaystyle \sum_{i=1}^{n}b_i(a_i-b_i^2)$$

===== 做法 =====

这个题看一下曲线就知道每个 $f(i, b_i)=b_i(a_i-b_i^2)$ 是个随着 $b_i$ 递增先升后降的量。

然后再一看，是个三次函数，有凹凸性。（$\cfrac{\mathrm{d} f(i, b_i)}{\mathrm{d} b_i}=a_i-3b_i^2$，$b_i>0$ 时单调减）

考虑我们首先把 $b_i$ 都取为 $0$，发现这时候结果是 $0$。

然后考虑贪心的把 $b_i$ 往上涨，涨到 $\sum b_i=K$。

我们每步可以选取使得 $(b_i+1)(a_i-(b_i+1)^2)-b_i(a_i-b_i^2)$ 最大的 $b_i$ 进行 ''%%++b_i%%''。

然后我们发现这时候凸性可以派上用场了。

凸函数在数轴上一段连续的整点处的取值序列，依旧具有凸性。

考虑 $f(i, j)=j(a_i-j^2)$，也就是说 $\{f(i, j)\}$ 对 $j$ 依旧具有凸性。

那么如果我们用 $\Delta f(i, j)$ 表示 $\{f(i, j)\}$ 的一阶差分序列中的元素，会发现 $\{\Delta f(i, j)\}$ 具有单调性。

那么这边就吻合上了，我们贪心的时候需要每步对所有 $i$ 选取最小的 $\Delta f(i, b_i)$，执行 ''%%++b_i%%''。

那么显然我们每步取出的 $\Delta f(i, b_i)$，随着执行过程，也是有单调递减的。

那么到这做法就很显然了，我们直接二分这个值，对每个 $i$ 再次二分这个值的位置，加速贪心过程。

====== [E] Train Tracks ======
====== [F] Piet's Palette ======

还没看，摸了。
CVBB ACM Team

用户工具

站点工具

页面工具
