AtCoder Beginner Contest 178 题解

AC Codes

A – Not

B – Product Max

C – Ubiquity

询问有多少大小为 $N$ 的数列 $A$ 满足以下条件：

任意一个 $A_i\in[0,9]$ 。

至少存在一个 $8$ 和一个 $9$ 。

$N\leq 2\times 10^5$ 。

简单容斥原理，答案就是 $全集-至少存在一个 8 的-至少存在一个 9 的+至少存在一个8和一个9的$ 。

D – Redistribution

给定一个正整数 $S$ ，询问有多少个数列 $A$ 满足任意一项 $A_i\geq 3$ 并且数列之和等于 $S$ 。

$S\leq 2000$ 。

从多项式角度考虑，答案显然为 $[x^S]\sum_{i=0}^{\infty}f^i$ ，其中 $f=x^3+x^4+\cdots=\sum_{j=3}^{\infty}x^j$ 。

很显然可以进行以下变换：

\begin{aligned} [x^S]\sum_{i=0}^{\infty}f^i &=\frac{1}{1-f}\\ &=\frac{1}{1-\frac{x^3}{1-x}}\\ &=\frac{1-x-x^3}{1-x} \end{aligned}

因此，答案为 $[x^S]\frac{1-x-x^3}{1-x}$ 。

~~当然也可以dp，很简单。~~

E – Dist Max

二维平面上有 $N$ 个点，求任意两点间最大的曼哈顿距离。

$N\leq 2\times 10^5$ 。

注意到到某个点 $(x_0,y_0)$ 曼哈顿距离为 $d$ 的点构成一个旋转了 $45^\circ$ 的正方形（四个顶点为 $(x_0+d,y_0),(x_0,y_0+d),(x_0-d,y_0),(x_0,y_0-d)$ ）。

因此我们只需要考虑所有点中被 $y=x+m$ 和 $y=-x+m$ 这两条直线“夹住”的长方形空间，最远的曼哈顿距离一定出现在长方形的对边上。因此求出这两种对边的距离取最大值即可。

F – Contrast

给定两个大小为 $N$ 的数组 $A,B$ ，询问能否重排数列 $B$ ，是的对于任意的 $i(i\in [1,N])$ 均满足 $A_i\neq B_i$ 。

$N\leq 2\times 10^5$ 。

本质上是一个二分图匹配问题，但是由于边集很大所以不可能直接建图，因此我们需要通过这个图的一些特殊性质入手。

这个图的特点在于“同色”的点不能建边，因此我们可以将所有点分为三类：

只存在于数组 $A$ 的点；
只存在于数组 $B$ 的点；
既存在于数组 $A$ 又存在于数组 $B$ 的点。

显然前两类点可以视为通配符，可以任意匹配，因此本题的重点在于第三类点。

让我们先考虑一下本题如何判断是否有解，通过样例，我们不难猜出如果存在一组完美匹配，那么必须满足对于任意一种颜色 $i$ 均满足 $cnta_i+cntb_i\leq N$ ，也就是说左半部（$cnta$）和右半部（$cntb$）里的出现总次数不超过 $n$ 则一定存在完美匹配。这个猜想可以通过Hall’s Theorem证明。

因此，我们的构造一定要始终满足 $\forall i\in[1,N],cnta_i+cntb_i\leq N$ ，很自然地会想到如果每次取出第三类点中 $cnta_i+cntb_i$ 最大的两种颜色，然后两两匹配，是不是就可以了？答案是对的，因为这样的构造可以让出现次数最大的两种颜色匹配，那么这两种颜色的数量和总量（$N$）都会减少 $1$ ，从而令剩下的图仍然满足 $\forall i\in[1,N],cnta_i+cntb_i\leq N$ 这一条件。

这里有一个小问题，万一出现次数第三大的点 $u$ 满足 $cnta_u+cntb_u=N$ 怎么办？不过通过反证法即可发现不存在此类情况：

如果第三大的点出现次数 $=N$ ，那么前三大的点出现总数就 $\geq 3N$ ，而二分图总共点数为 $2N$ ，显然不成立。

最后，剩下的第一类和第二类点随意匹配即可。