【题解】2019年湘潭大学新生趣味程序设计竞赛

A、 15 and 20

$f\left( n\right) =f\left( n+1\right) +f\left( n-1\right)$ ，已知 $图片说明$ , 求 $图片说明$ 。
手工枚举一下，可以发现循环节长为 $图片说明$ 。
$x, y, y - x, -x, -y, x - y$

$图片说明$ 个奇数， $图片说明$ 分成两个集合，使得集合累加和的差值最小
结论： $图片说明$ , 差值为 $图片说明$ ；其他，差值为 $图片说明$ 。
证明：
- 连续四个奇数为 $图片说明$ 分成两组 $图片说明$ , 差值为 $图片说明$ 。所以，当 $图片说明$ ，结果为 $图片说明$ 。
- 当 $图片说明$ 时，我们把 $图片说明$ 以外的所有数按连续 $图片说明$ 个进行分组，差值为 $图片说明$ ，然后把 $图片说明$ 随便给某个集合，差值为 $图片说明$ 。由于 $图片说明$ 是奇数，所有奇数个奇数的和为奇数，所以分成两组，差值最小为 $图片说明$ 。所以，之前的构造为一个最小差值分组。
- 当 $图片说明$ 时，结果显然为 $图片说明$ 。其他 $图片说明$ 时，最小的 $图片说明$ 个数分为 $\{1,3,5,9\}$ 和 $\{7,11\}$ , 差值为 $图片说明$ 。显然最后结果为 $图片说明$ 。
- 当 $图片说明$ 时，采用类似于第 $图片说明$ 步的构造和利用奇偶性，得到最小值为 $图片说明$ 。

$图片说明$ 个订单，求完成时间的最小累加和
最优安排是按订单数从小到大安排生成
反证
- 假设一个最优安排中，存在 $i<j$ , 但是 $图片说明$ 。我们交换 $a_i$ 和 $a_j$ 的位置，得到一个新的安排。
- 显然对于 $图片说明$ 或者 $图片说明$ 的订单，这种交换没有影响。
- 对于 $i <k <j$ 的订单，显然，其完成时间是小于或等于原有安排的。
- 矛盾

构造一个长度为 $图片说明$ 的字符串，要求其中最长回文子串的长度处于 $[y, x]$ 之间，且出现各种字符的次数不超过给定的限制。
做法很多
- 先构造一个类似于 $^{\prime \prime} \mathrm{ab} \ldots \mathrm{ba}^{\prime \prime}$ 的回文串，长度为 $x$ 。然后取其他字符填充成 $^{\prime \prime} a b \dots b a c d^{\prime \prime}$ 的形式，然后再用这个子串按顺序填充成 $len$ 长的字符串（雷智凯）
- 先利用无限制字符，构造一个类似于 $^{\prime \prime} a \dots a^{\prime \prime}$ 的串，然后随机产生后面的字符，要求随机出来的字符不超过限制，且不等于前 $1$ 和前 $2$ 个字符。（谢勇）

给一个整数 $A$ ，求另外两个整数 $B$ 和 $C$ ，使其构成直角三角形
构造的方法也很多
- $图片说明$
- 不妨设 $b-c=1, \quad a^{2}=2 c+1$ ,所以 $图片说明$ 必须为奇数,解得 $b=\frac{a^{2}+1}{2}, c=\frac{a^{2}-1}{2}$
- 不妨设 $图片说明$ ,所以 $图片说明$ 必须为偶数,解得 $图片说明$

交换一个串的两个字符以后，使得串不含 $^{\prime \prime} \mathrm{BAD}^{\prime \prime}$ 这个子串
构造方法也很多
- 统计 $BAD$ 的数量 $n$ ，显然每次交换最多破坏两个 $BAD$ 子串，所以当 $n>2$ 时无解
- 如果 $n = 2$ , 交换成 $...AAD...BBD...$
- 如果 $n = 1$ , 交换成 $...ABD...$
- 否则，随机交换两个字符，验证一下。