526互联

【题解】AtCoder Regular Contest 161

发布时间 2023-09-08 17:30:19作者: linyihdfj

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

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 问题。