Cards

发布时间 2023-09-08 09:44:07作者: 是002呀

分析

本题主要考察思维和简单的数学能力。
根据题意我们要尽可能的使得 0 连续,2 分散
因为 $12+12>(1+1)^2$,反之同理。所以我们尽可能使得最后的形式是 2020...00...002 即是用 0,将 2 分割开来。

首先我们从让一整段 02 分割成两段的情况开始讨论。此时有一整段 0 长度为 $n$ ,两段 2 长度可能都为 $m\div2$ ,或者一段 $m\div2$ 另一段为 $m\div2+1$ ,将 $n, m$ 的分段情况找出来之后就可以按照题目给的算法算出一个一个 $cnt$ 值。

然后我们再将情况拓展开,假设现在所有的 0 被分割成了 $i$ 段,那么此时所有的 2 就被分割成了 $i+1$ 段,这 $i$ 段的 0 中会有 $(i-1)$ 段的长度为 $1$ ,因为拿去用于分割 2,剩下的一段就是我们保证的最长连续的 0,长度为 $n-(i-1)$

此时的 2 被分成 $i+1$ 段,如果能整除,那么每段的长度就为 $m\div(i+1)$ ,如果无法整除呢,我们令 $m=x\times(i+1)+y$ ,其中 $x=m\div(i+1)$ ,$y=m\bmod(i+1)$,我们假设有 $p$ 段的长度为 $x$ , $q$ 段的长度为 $x+1$ 用一个简单的待定系数法就可以算出 $q=m\bmod(i+1)$,$p=(i+1)- m \bmod (i+1) $;

这样我们就把可以把这种情况下的 $cnt$ 值算出来,现在由于 0 最多只有 $n$ 个所以最多只能被分成 $n$ 段,那么我们就枚举 $i$ 从 $1$ 到 $n$ ,把每种情况下的 $cnt$ 算出来找到最大的,并把当前的分段情况记录下来用于之后的输出就可以了