2018年东南大学C++程序设计竞赛暨“第零届”东南大学程序设计竞赛测试赛（冬季）题解

A：简单打印

直接输出即可。

B：丢丢陈和陈丢丢下棋

比较 $n\le m$ 时一定会赢，否则会输。

C：三次方程求解

由题意知方程可以分解成 $k(x-a)(x-b)(x-c)$ 的形式，$a,b,c$一定不会超过原方程的系数，直接枚举答案即可。

D：丢丢陈打嗝

如果存在答案，答案一定不会超过$\max(a,c)+b*d$，直接模拟过程即可。

E：丢丢陈矩阵

首先枚举交换的两列（或者不交换），再判断每一行是否可以通过一次交换满足条件，如果不行可以证明这种交换列的方法一定不行。时间复杂度 $\Theta(Tn^4)$。

F：丢丢陈周游世界

首先先把边权为 $0$ 的边加入，然后原图还剩下 $k = \lceil n/2\rceil$ 个联通块。不难得到答案的下界是 $k-1$。

下面给出一种仅需 $(k-1)$ 条边权为 $1$ 边的方法即可。

$2\longleftrightarrow n，3\longleftrightarrow (n-1),\ldots ,k\longleftrightarrow (n+2-k)$ 满足条件。

G：丢丢陈的生活计划

$F[i][0],F[i][1],F[i][2]$ 分别表示考虑了前 $i$ 天第 $i$ 天休息，运动，做题的最小休息天数。转移DP即可。时间复杂度 $\Theta(Tn)$。

H：丢丢陈的数列

取模运算并不具有交换律，所以我们只能先计算${a_i}^7\ mod\ Q$,然而计算过程会出现 long long 溢出的情况，可以使用 __int128，或者用大数乘法解决。

I：三色岛屿

现在仅考虑两种颜色之间，一个点如果连了两个其他颜色的点，肯定不满足题意，反之满足则题意。所以现在原问题分割成了三个独立的相同的子问题：有多少种在 $n$ 个白点与 $m$ 个黑点间连边的方式使得，任意每个点要么没有临边，要么仅与一个异色点相连。即答案为 $F[n][m],F[n][m] = (F[n-1][m-1]*m+F[n-1][m])$ 。

现在原问题的答案即为 $F[a][b]*F[b][c]*F[c][a]$。

补充：@thd 指出了另一种更快的 $F[n][m]$ 计算方法，考虑枚举黑、白两个点集之间连接了 $i$ 条边，则方案数为 $\sum_{i=0}^{\min\{n,m\}}{\binom ni\binom mi i!}$。

J：LCL的取钱计划

记 $F[i][j][k]$ 为考虑了 $i$ 个女朋友，前 $j$ 天，当前已经连续 $k$ 天有女朋友的最大收益。

转移时枚举一段连续的区间，可以通过区间长度和k计算出最多可以选择比赛的场次和选择范围，因为 $a[i]$ 都是正数我们可以当然应该选取尽量多的比赛。

我们可以预处理 $cost[l][r][k]$ 表示从区间 $[l,r]$ 中选取 $k$ 个数的最大值。

这样状态数 $\Theta(nXY)$，决策数 $\Theta(n)$，决策时间 $\Theta(1)$。时间复杂度 $\Theta(n^2XY)$。

K：完美小姐姐集

构造题，首先我们要考虑清楚一个问题，任意两个集合公有元素只有一个，那么可以看为从 $k$ 个集合中选 $2$ 个集合得到一个共有元素，那么一共有 $k(k-1)/2$ 种选择方法，而由于每个元素刚好属于两个集合，所以每种选法得到的元素应该恰好都不同，所以 $n = k(k-1)/2$，满足时有解否则无解。构造方法如下：

$k=6$时，可正好保证要求。

按照如上构造方式即可得到最终答案。

东南大学 CPC 集训队 “2018 年东南大学 C++ 程序设计竞赛” 命题组