目录
Contest Info
| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 2/6 | O | O | - | - | - | - |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Almost Equal
题意：
构造一个排列，使得它形成一个环，并且任意相邻三个数的和的相差不超过\(1\)。
思路：
我们发现任意相邻三个数的和相差不超过\(1\)，假设和为\(?\)，列出式子如下：
\[
\begin{eqnarray*}
a_1 + a_2 + a_3 &=& ? \\
a_2 + a_3 + a_4 &=& ? \\
\cdots \\
a_{n - 2} + a_{n - 1} + a_n &=& ? \\
a_n + a_1 + a_2 &=& ?
\end{eqnarray*}
\]
那么有：
\[
\begin{eqnarray*}
|a_1 - a_4| &\leq& 1 \\
|a_2 - a_5| &\leq& 1 \\
|a_3 - a_6| &\leq& 1 \\
|a_4 - a_7| &\leq& 1 \\
\end{eqnarray*}
\]
那么显然有\(a_1, a_4\)是相邻两个数，\(a_2, a_5\)是相邻两个数，\(a_3, a_6\)相邻两个数。
那么这样分配就好了，然后发现\(n\)是偶数的时候不可以的。
B. Shortest Cycle
题意：
有\(n\)个点，任意两点\((i, j)\)如果\(i \& j \neq 0\)的话，那么\((i, j)\)之间有一条边。
现在要找一个最小的环。
思路：
考虑每一位，那么这一位为\(1\)的数会形成一个强连通分量，如果这一位为\(1\)的点的个数大于等于\(3\)，那么肯定有一个大小为\(3\)的环。
否则直接暴力\(DFS\)找环即可。