AtCoder Regular Contest 161

【题解】AtCoder Regular Contest 161

评价：感觉这场题目质量不咋地啊，都是一些乱搞题

A.Make M

题目描述：

$N$ 是一个正奇数。我们称一个长度为 $N$ 的序列 $S$ 是 M 型序列，当前仅当对于所有的 $i=2,4,6,\dots,N-1$（即偶数位），都有 $S_{i-1}<S_{i}$ 且 $S_{i}>S_{i+1}$。

现在给定你一个长度为 $N$ 的序列 $A$，请你判断能否通过将 $A$ 序列里的元素打乱位置使其变为一个 M 型序列。

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

题目分析：

我们就是考虑让偶数位尽可能大，而奇数位尽可能小。
所以就是排序之后，让较大的一些认为放到偶数位，让较小的一些认为放到奇数位。
并且要让放到偶数位上尽可能小的，周围放的是奇数位上尽可能小的。

代码：

B.Exactly Three Bits

题目描述：

对于一个正整数 $X$，定义 $f(X)$ 为 $X$ 在二进制表示下 $1$ 的个数，比如，因为 $6=110_{(2)}$，$11=1101_{(2)}$，$16=10000_{(2)}$，所以 $f(6)=2$，$f(11)=3$，$f(16)=1$。

现在给定你一个正整数 $N$，问是否存在一个小于等于 $N$ 的正整数 $X$，满足 $f(X)=3$。如果存在，请输出满足条件的最大的 $X$，否则输出 -1。

本题有多组数据。
$1 \le N \le 10^{18}$

题目分析：

可以直接枚举最高位和次高位，然后判断是简单的。

代码：

C.Dyed by Majority (Odd Tree)

题目描述：

给定一棵 $n$ 个节点的树，满足每个点的度数为奇数。你需要把每个点染成黑色或者白色，然后所有点同时变成其相邻点颜色的众数，求一个染色方案使得变化后的颜色为给定序列，或者报告无解。
$2 \le n \le 2\times 10^5$

题目分析：

考虑我们可以根据叶子节点变成什么直接推得其父亲节点是什么。
也就是说我们其实可以从下到上一层层确定节点的颜色。
如果 $u$ 的某一个儿子 $v$ 没有被确定颜色，那么也就是意味着无论这个点放什么在 $v$ 的子树内都是合法的，我们就可以贪心地将 $v$ 的颜色认为是 $u$ 变成的颜色。
有了这个过程就很好做了。

代码：

D.Everywhere is Sparser than Whole (Construction)

题目描述：

我们将非空简单无向图的密度定义为$\displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}$。

给你正整数 $N$ 和 $D$。请判断是否存在一个有 $N$ 个顶点和 $DN$ 条边的简单无向图 $G$ ，它满足以下条件。如果存在，请找出一个这样的图。

条件： 让 $V$ 是 $G$ 的顶点集。对于$V$的任何非空的真子集$X$，由$X$诱导的$G$子图的密度严格小于$D$。

什么是诱导子图？

对于图$G$的顶点子集$X$，$X$对$G$的诱导子图是顶点集为$X$且边集包含连接$X$中两个顶点的$G$的所有边的图。在上述条件中，请注意我们只考虑既不为空也不为全集的顶点子集。

题目分析：

首先就是怎么判断无解，如果 $nd > \frac{n(n-1)}{2}$ 则无解，因为边数完全不够。
否则的话考虑贪心地构造，也就是让这些点连的边尽可能平衡，从每一个点向其后 $d$ 个点连边，可以发现这样构造出来的图就是合法的。

代码：

E.Not Dyed by Majority (Cubic Graph)

题目描述：

给定一个 $n$ 点 $\dfrac32n$ 边的简单无向图，其中 $n$ 为偶数，且每个点的度数恰好为 $3$。

将每个点染上黑与白两种颜色后，进行以下操作：

• 将每个点的颜色变为其连接的点中颜色的众数。

请构造一个所有节点的颜色序列，使得无论原图如何染色，在经过一次操作后都不可能变为该颜色序列。多组数据。
$4 \le n\le 5 \times 10^4$

题目分析：

推荐做过 C 题之后再来做这个题。
会发现 C 题就已经不好做了，这个题估计根本不可做，所以大胆猜结论随机一个颜色序列大概率不合法。（这个结论也可以通过打表来证明）
考虑给定了一个颜色序列如何判断时候合法，因为每个点度数为 $3$，所以其实就是相当于：若 $x$ 的颜色为 $A$，则 $y,z$ 的颜色必然为 $B$，就是一个 2-sat 问题。