CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
======2020牛客暑期多校第七场======
[[https://ac.nowcoder.com/acm/contest/5672|比赛链接]]
=====A.=====
**upsolved by** 
====题意====

====题解====

=====B.=====
**solved by 2sozx JJLeo**
====题意====
$t$ 个询问，每个询问包含两个数 $n,m$，问将 $n\times m$ 个数分成最少多少个数使得这些数能够组合成 $n$ 个 $m$ 和 $m$ 个 $n$。$n,m\le 10^4$

====题解====
如果 $n=m$ 显然直接分成 $n$ 个 $m$ 最优。否则假设 $n<m$ ，先分出 $n$ 个 $n$ 接下来进行 $(n,m-n)$ 的子任务即可。
=====C.=====
**solved by 2sozx**
====题意====
给定一颗 $n$ 个节点的树，定义三种操作：
  * 第一种操作：选择一个节点 $x$ 并且给定一个值 $w$ ，所有结点的值增加 $w-dis(i,x)$。
  * 第二种操作：选择一个节点 $x$ ，让 $x$ 的值与 $0$ 取 $\min$
  * 第三种操作：询问一个节点 $x$ 的值。
$n,q\le5\cdot10^4$
====题解====
第二个操作显然是很容易实现的，现考虑第一个操作。考虑将一个点定义为根 $root$ ，选择一个点 $x$ ,那么 $root$ 的儿子的子树不包含 $x$ 的儿子子树内所有的点的值应该改变为 $w-dis(root,i)-dis(root,x)$，而包含了 $x$ 的儿子的子树的值的改变会有不同。
第一种做法：
  * 考虑到包含了 $x$ 的儿子的子树每次只会有一个儿子，因此我们可以用动态点分治来维护。
  * 具体细节[[.2sozx:牛客多校第七场C]]
第二种做法：
  * 考虑包含 $x$ 的儿子的子树的改变与其余儿子的子树的值会有多少不同，从根节点出发，每次向 $x$ 移动一位则会让整个子树的值增加 $2$ ，因此用树链剖分可以维护。
=====D.=====
**solved by 2sozx Bazoka13 JJLeo**
====题意====
$1e6$ 次询问，每次给定一个不超过 $1e5$ 的数字 $n$，询问$1-n$的平方和是否为平方数
====题解====
首先可以知道平方和公式为$\frac{n(n+1)(2n+1)}{6}$，那么将$6$分解为$2、3$或$1、6$后选择分子某两项除去，判断剩余三个数是否为平方数，枚举情况即可
=====E.=====
**upsolved by**
====题意====

====题解====

=====F.=====
**solved by **
====题意====
====题解====
=====G.=====
**upsolved by**
====题意====

====题解====

=====H.=====
**solved by JJLeo**
====题意====
求$\sum_{i=1}^{k}\sum_{j=1}^{n}{[i \mod j \le 1]} \pmod{10^9+7}$。$(n,k \le 10^{12})$
====题解====
直接数论分块即可。注意细节！！！
=====I.=====
**upsolved by 2sozx JJLeo**
====题意====
$n$个不同的点的生成森林中，每个点权值为该点的度数和平方，问所有生成森林的所有点的权值和是多少，$T$组数据。$(n,T \le 5000)$
====题解====
每个点都是对称的，因此只需固定一个点最后乘以$n$即可。首先设$h_i$为$i$个不同的点的生成森林数量，利用purfer序列可以得到$O(n^2)$递推式$$h_i=\sum_{j=0}^{i-1}\binom{i-1}{j}j^{(j-2)}$$接下来设$g_i$为我们所考虑的点所在的树大小为$i$时所有情况该点贡献的权值和，考虑将该点固定为根，然后枚举该点的度数，利用prufer序列算出方案数，再乘以度数的平方和，得到$O(n^2)$递推式$$g_i=\sum_{j=1}^{i-1}\binom{i-2}{j-1}{(i-1)}^{i-2-(j-1)}$$最后设$f_i$为节点数为$i$时一个固定节点对答案的贡献，考虑枚举该点所在树的大小，则剩下的节点组成森林，可以得到$O(n^2)$递推式$$f_i=\sum_{j=2}^{j=i}\binom{i-1}{j-1}g_jh_{i-j}$$对于每个询问，我们只需$O(1)$输出$nf_n$即可。
=====J.=====
**upsolved by JJLeo**
====题意====
一共有$26$个对象，每个对象有$26$个指针，此外还有还有$26$个全局指针，现在有$n$条指令，每条指令指明一些指针可以访问一些指针所指向的对象，问以任意顺序重复这些指令无数次，每个全局指针有可能指向的对象的集合。
====题解====
题意理解有点小问题，以为一个指针同一时刻可以指向多个对象，然后就去dfs，直接暴毙。\\
只需要对每个指针状压一下能指向哪些对象，然后不断进行$OR$操作直到一轮不发生变化即可。
=====记录=====
0min：开局分题\\
10min：讨论了D题，冲D，WA，发现少讨论了情况\\
18min：AC，冲H\\
55min：ZYF AC H，MJX冲B\\
71min：MJX AC B，一起冲J\\
???min：疯狂WA J，MJX去看C\\
257min：MJX AC C，后继续一起看J\\
till end：J WA\\
after end：模拟题一生之敌
=====总结===== 
  * MJX要练练英语加快读题速度
  * CSK重写J到最后RE了（悲），并且比赛前一定要休息好，不然就会$2h$就宕机
  * ZYF要练习更好地理解题意（尤其是大模拟），避免和空气斗智斗勇。另外要加强知识的理解，例如因为对prufer序列一知半解而把I题完全想歪。
CVBB ACM Team

用户工具

站点工具

页面工具
