Codeforces Round #580 (Div. 1)

目录

Contest Info


Practice Link

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\)找环即可。

上一篇:580【毕设课设】基于单片机温湿度检测显示报警控制系统设计


下一篇:Android(java方法)上实现mp4的分割和拼接 (二)