A-用水填坑

10分

边界不能存水, 那么一共有$(n-1)\times(m-1)$个位置能存水.

枚举每个位置放多少水, 判断是否合法然后取最优方案.最多有$4^{5}$种情况.

20分

不存在两个连续的块能存水, 那么只需要在10分的基础上枚举每个块和它四周的块能不能同时存水就好了.

95分

大概是发现每一层都是独立的, 因为高度不超过100, 所以将其分为若干高度为1的层, 每层独立处理, 看看每一层能存多少水, 再累加起来就好了.可以直接搜索.复杂度不超过$O(nmh)$.

100分

这大概是个贪心的做法.

一开始所有未在边界点的最终高度都是不确定的.策略是用已经确定了高度的最低的点来更新其它未确定点的高度, 如果它相邻的点比这个点高度低, 显然可以填到一样高, 因为这样做能保证这个被更新的点一定是被它相邻的高度最低的已确定高度的点更新到.

那么用堆来维护最低的确定高度的点, 一开始堆内只有边界上的点.

每个点只能进一次堆被更新一次高度.复杂度$O(nm\log_2 n)$.

这个题总体来说比较简单, 95分可以说是非常容易拿到的.

B-死宅选点

设$d_i$表示$k+k^2+k^3+\cdots+k^i$, 那么若点u与点v的路径上有$i$条边, 这条路径的厌恶度就是$d_i$.

30分

假设选择一个位于中点左边的点$u$, 这个点左边有$a$个点, 右边有$b$个点.则***生的厌恶度为$\sum_{i=1}^ad_i+\sum_{i=1}^bd_i$.

注意到如果选择$u$右边的那个点作为答案, 厌恶度变为$\sum_{i=1}^{a+1}d_i+\sum_{i=1}^{b-1}d_i = \sum_{i=1}^ad_i+\sum_{i=1}^bd_i - d_{b} + d_{a+1}$.发现厌恶度变小了.因此可以推断, 选择更靠右的点(不超过中点)是更优的.同理, 选择右边的点也是如此.因此, 当图为链的形态时, 选择中点是最优的.

50分

$n\le 500, k = 2$, 可以以每个点为树根遍历一遍树, 得到每个点作为根时的厌恶度进行比较.

因为树是随机生成的, 利用随机生成的树期望最高树高为$\sqrt{N}$, 平均树高为$\log_2 N$, $\sqrt{500}<23$, 那么产生的最长路径长度大概在$50$以内\footnote{数据中有两个点最长路径长度达到了63, 但真的是随机数据, 嘻嘻!}, 所以答案是可以用一个128位长整数(C++中的\li\li int128)表示的, 用long long(\li int64)分数会少一点吧.

70分

$k=1$, 因为1的任意次幂都为1, 所以一条路径的厌恶度就是路径上边的个数.

设$f(u)$为$u$到其它所有点的厌恶度总和.容易得到

$$ f(v)=f(u)-\text{Size}_v+n-\text{Size}_v $$

其中$\text{Size}_v$表示$v$这棵子树的大小.

随便选一个点作为树根, 遍历一遍树就得到了树根的答案.然后再遍历一遍树, 得到其它点的答案.

100分

发现难点在于没法对$k ^ 1, k ^ 2, \cdots$直接进行运算.首先$d_i = k+k^2+\cdots + k^i$可以看成是一个公比为$k$首项为$k$的等比级数.类比$2^0+\cdots+2^i=2^i-1$的常识再应用等比数列求和公式.我们可以得到$d_i=\frac{k^{i+1}-k}{k-1}$.

因为分子上的$-k$和分母上的$k-1$是每一项$d$都有的, 本题也无需求出具体的值.因此可以认为$d_i$与$k^{i+1}$相等.

设$p(u,h)$表示树上与$u$距离$h$点的个数.

$d(i,j)$表示$i$的子树中与$i$距离为$j$的点的个数, $u(i,j)$表示不在$u$的子树中与$i$距离为$j$的点的个数.

那么$$d(i,j)=\sum_{v\in \text{son}_i}d(v,j-1)$$

$$u(i,j)=\sum_{i\in \text{son}_f}u(f,j-1)+d(f,j-1)-d(i, j-2)$$

那么点$u$与其它点的总厌恶度就是$\sum_{h=1}p(u,h)k^{h+1}$.

其实可以将$k^i$看成是一个$k$进制数第$i$位上的一个"1".模拟进位, 即$p(u,h)k^{h+1}=(p(u,h) \bmod k) k^{h+1} + \frac{p(u,h)}{k}k^{h+2}$, 当然到最后一位就不用再进位了.

那么这样比较两个$k$进制数的大小最多需要最大路径长度次($\sqrt{N}$).加上前面求$p(u,h)$的复杂度大概是$O(n\sqrt{N})$.总复杂度为$O(n\sqrt{N})$.

C-随机采矿

10分

$m=n+1$.注意到$\frac{1}{T}\lfloor\frac{T}{1}\rfloor$在$T$为任意可能值时都为1.所以第$0$个时刻一定会制造一个SCV.以后就不会再制造了.

20分

$m=n+2$, 又因为第一个SCV在第0时刻被制造.所以只需要考虑第二个在什么时候制造即可.

设第二个SCV被制造时刻的期望值为$E$.

$$

E = \sum_{i = 1} ^ {T - 1} i\cdot \frac{1}{T}\lfloor\frac{T}{i + 1}\rfloor\prod_{j = 1} ^ {i - 1}\left(1 - \frac{1}{T}\lfloor\frac{T}{j + 1}\rfloor\right)

$$

其实这个做法只是为您提供了一个可能的思路.

50分1

这个做法不是我想的（另一位）, 设$g(i,j)$到第$i$个时间(第$i-1$个时刻到第$i$个时刻)有$j$只工作的(不算正在制造的)SCV的期望收益, 逆推得到:

$$
f(i,j)=
\begin{cases}
f(i+1, j) + kj&, j = m; \
\frac{1}{T}\lfloor\frac{T}{i}\rfloor\cdot(f(i+1, j + 1) + kj)+\left(1-\frac{1}{T}\lfloor\frac{T}{i}\rfloor\right)\cdot(f(i + 1, j) + kj)&, j< m
\end{cases}

$$

然而这个做法我并没有想到如何优化到更高的分数.

50分2

设$f(i,j)$表示第$i$时刻拥有$j$只SCV的概率.那么
$$
f(i,j)=

\begin{cases}

0&,\text{others}\

1&,i=0\text{ and }j = n\

\left( 1-\frac{1}{T}\lfloor\frac{T}{i}\rfloor\right) f(i-1,j)+\frac{1}{T}\lfloor\frac{T}{i}\rfloor f(i-1,j-1)&,i>0\text{ and }j\ge n\

\end{cases}

$$

设$E(t)$为$t-1$到$t$时刻的期望收益(没减去制造SCV时间的收益)

$$E(t)=k\sum_{p=n}^mf(t,p)p$$

减去制造SCV时间的收益

$$

R = \sum_{t = 1} ^ TE(t)-\sum_{p=n}^mf(T,p)\cdot k(p-n)

$$

总复杂度为$O(nm)$, 可以通过$50%$的数据.

100分

发现每次转移实质上都是一次线性变换.

可以把$f(t, i), i = n, n + 1, \cdots, m$依次填入一个$m-n+1\times 1$的矩阵中, 设为$A_t$

$$

A_t=

\begin{pmatrix}

f(t,n)\f(t,n+1)\\vdots \f(t,m)

\end{pmatrix}

$$

特别的

$$

A_0=\begin{pmatrix}

1\ 0 \ \vdots\ 0

\end{pmatrix}

$$

就可以将依次转移表示成一次矩阵乘法了.

$$

A_{t+1}=B_tA_t,

A_{T}=\prod_{i=1}^T B_iA_0

$$

发现$\lfloor \frac{T}{i}\rfloor$最多有$2\sqrt{N}$种值, 即$B_i$有$2\sqrt{N}$中可能.

那么进行数论分块.对于$\lfloor \frac{T}{i}\rfloor$的一个可能的值求出当这时的转移矩阵.矩阵快速幂即可.

首先为了方便, 将$E(t)$同样表示成矩阵乘法的结果的形式.

$$

D=

\begin{pmatrix}

n&n+1&\cdots&m

\end{pmatrix}

$$

$$

E(t)=kDA_t

$$

发现要求$E(t)$需先求出$A_t$, 但是在求$A$的时候并不是将所有的$A_i,i=1,\cdots, T$全部算出来的.

不过依然可以利用一点小技巧求出期望.

依然是利用之前的数论分块的结果.

如果$\lfloor \frac{T}{l}\rfloor ,\cdots,\lfloor \frac{T}{r}\rfloor $的结果相同,设此时的转移矩阵为$C$, 那么

$$

\begin{aligned}

A_{l}&=CA_{l-1}, \

A_{l+1}&=C^2A_{l-1},\

\cdots\

A_r&=C^{r-l+1}A_{l-1}

\end{aligned}

$$

$$

kD\sum_{i=l}^rA_i=kDA_{l-1}(C+C^2+\cdots+C^{r-l+1})

$$

发现这是一个矩阵等比级数的形式.一般有两种求等比级数的方法:

• 等比数列求和公式: 有除法, 需要用到逆矩阵, 可能不存在逆矩阵(广义逆矩阵可能可以?), 不建议用;

• 分治: $C+C^2+\cdots+C^n = C+C^2+\cdots+C^{n/2}+C^{n/2}(C+C^2+\cdots+C^{n/2})$, 根据$n$的奇偶性进行讨论.复杂度是$O(m^3\log_2T)$.

这个做法复杂度$O(m^3\sqrt{T}\log^{2}_2T)$