====== 2020牛客暑期多校第七场 ======

====== 比赛地址 ======

[[https://ac.nowcoder.com/acm/contest/5672#question|牛客OJ]]

Pro: 4/6/11

Rank: 119/1090

====== [A] Social Distancing ======

===== 题意 =====

在半径为$r$的圆形区域内(含边界)放置$n$个人,要求每个人都必须在整点上,且要使$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(i,j)$最小.$d(i,j)$表示两个人间的欧氏距离.求这个最小值.

===== 题解 =====

遗传算法乱搞打表题.

其实容易猜到一个结论,那就是所有的人一定会站在边界的整点上.在此基础上乱搞的时候会少很多状态.

====== [B] Mask Allocation ======

===== 题意 =====

有$n\times m$个口罩,要求把它们分成尽可能少的$k$箱,同时这$k$箱可以分成$n$组,每组共有$m$个口罩,或者是$m$组,每组共有$n$个口罩.输出方案.

===== 题解 =====

不妨设$n>m$.先把所有的口罩分成$m$箱,每一箱$n$个.然后将每一箱拆分成很多小箱,每一小箱有$m$个,这样最后会余下$m$箱,每箱$n\%m$个口罩,然后将$m$看做$n$,$n\%m$看做$m$,用类似辗转相除的方法继续划分,直到最后余数为0.

====== [C] A National Pandemic ======

===== 题意 =====

给一棵树,每个点有一个权值,初始时都是0.有三种操作:

  - 给出$x$和$w$,对于任意一个点$y$,其权值增加$w-dis(x,y)$
  - 调整$x$的权值,如果其大于0,则将其修改为0
  - 查询$x$的权值

===== 题解 =====

对式子做一下变形,$w-dis(x,y)=w-dep(x)-dep(y)+2*dep(lca)$.其中$w-dep(x)$是每个点共有的增量,可以用一个变量记录.$-dep(y)$可以用操作1的次数来代替.

开一个线段树来维护最后一部分的增量.$+2*dep(lca)$可以转化为将点$x$到根的路径上的所有点的增量$+2$,然后每个点的增量可以通过查询其到根路径上所有点的增量和来完成.

对于2操作,设置一个偏移量即可.

====== [D] Fake News ======

===== 题意 =====

判断$\frac{n(n+1)(2n+1)}{6}$是不是完全平方数.

===== 题解 =====

只有在$n=1,24$的时候才是完全平方数.证明很繁琐,见[[https://www.zhihu.com/question/363661682|这里]]


====== [H] Dividing ======

===== 题意 =====

给出合法元组的定义:

  - $(1,k)$是合法元组
  - 若$(n,k)$是合法元组,则$(n+k,k)$是合法元组
  - 若$(n,k)$是合法元组,则$(nk,k)$是合法元组

给出$n,k$,求有多少对$1 \leq x \leq n,1 \leq y \leq k$,$(x,y)$是合法元组.

===== 题解 =====

不难发现,当且仅当$x\%y=0/1$时才是合法元组.然后数论分块算就行了.

注意特判的时候也要取模......


====== [I] Valuable Forests ======

===== 题意 =====

定义由$n$个带标号的点构成的森林的价值为,每个点的度数的平方和的总和.

求由$n$个点构成的所有森林的价值总和.

===== 题解 =====

很不错的一个树学题.

解题的核心是Prufer数列.**Prufer数列告诉我们,每个带标号的无根树和一个长度为$n-2$的Prufer序列一一对应.**

定义$f[n]$表示,由$n$个点构成的森林有多少种.为了避免计数重复,可以单独考虑最后一个点所在的树的大小,假如从前$n-1$个点取出了$i$个点与最后一个点构成了一棵树的话,不难得到如下递推式:

$$f[n]=\sum_{i=0}^{n}C_{n-1}^{i}p[i+1]f[n-1-i]$$

其中$p[n]=n^{n-2}$,也就是$n$个点构成的无根树的种类数.

再设$s[n]$表示由$n$个点构成的所有树的价值总和.因为节点是带标号的,可以一个个单独计算,有如下式子:

$$s[n]=\sum_{1}^{n}\sum_{d=1}^{n-1}d^{2}C_{n-2}^{d-1}(n-1)^{n-2-(d-1)}$$

至此就可以递推计算答案了.

设$ans[n]$表示题目中要求的答案,则有:

$$ans[n]=\sum_{i=0}^{n-1}(s[i+1]\times f[n-i-1]+ans[n-i-1]p[i+1])$$

也就是将最后组出来的树单独算贡献,再和前面的森林的贡献加到一起.

====== 总结 ======

需要多做题,对知识点的运用不够熟练.(<del>说的就是Prufer数列</del>)