P12404 「CZOI-R3」可爱棉羊 题解

本次比赛难度为入门至提高+/省选。

但是没有入门。

首先考虑最小值，如果只有一只羊感染，那么它传染边上任何一个位置，然后两只羊互相传染就行了，最小值是 $2$ 只。如果有更多的羊感染，它们只要紧挨着排列，每一只都传染给边上已经感染的，最小值是 $x$ 只。于是有：

$ans_{\min}=\max\{2,x\}$

然后是最大值，先从一只羊开始扩展（这是不让羊挨在一起总是不劣的），如下：

$T$	传染情况
$0$	$\green{X}$
$1$	$\green{X}\red{X}$
$2$	$\red{X}\green{XX}\red{X}$
$3$	$\red{X}\green{XXXX}\red{X}$
$\cdots$	$\cdots$

感染总数是 $2T$。

把每 $2T$ 只当一个块，共有 $x$ 个块，注意不要超过 $n$，于是有：

$ans_{\max}=\min\{n,2Tx\}$

结论都放了，代码不用了吧。