2020牛客暑期多校第七场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 66/1090 | 4 | 6 | 10 |
A¶
upsolved by KAN
题意¶
在半径为 \(r\) 的圆上找 \(n\) 个整点使得两两之间距离平方和最大。
题解¶
原题 Codeforces 460E (Round #262) 。
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\) 的儿子的子树每次只会有一个儿子，因此我们可以用动态点分治来维护。
- 具体细节
第二种做法：
- 考虑包含 \(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¶
upsolved 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)\)递推式
接下来设\(g_i\)为我们所考虑的点所在的树大小为\(i\)时所有情况该点贡献的权值和，考虑将该点固定为根，然后枚举该点的度数，利用prufer序列算出方案数，再乘以度数的平方和，得到\(O(n^2)\)递推式
最后设\(f_i\)为节点数为\(i\)时一个固定节点对答案的贡献，考虑枚举该点所在树的大小，则剩下的节点组成森林，可以得到\(O(n^2)\)递推式
对于每个询问，我们只需\(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题完全想歪。