• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AtCoder Beginner Contest 210题解

admin

11月 28, 2021

A B

过水,略…

C

统计长度为k的区间的最多本质不同的数。用尺取法维护下左右指针就可以了.调了许久的原因是更新答案时出现了问题。
当我移动指针时,我们应该移动一个就更新一个,而不是将移动与更新分离。这里就写到这了.

D

遇到这种有绝对值的题,最好的做法还是分类讨论将绝对值拆开.
拆开后就会发现可以用二维前缀和的方式保留当前子矩阵的max,之后扫一遍即可.
比赛时光记录左边的矩阵了忽略了右边的矩阵……还是思维上的漏洞啊

E

真的是光明正大的用图论的背景考察数论的知识。根据克鲁斯卡尔算法的思想,我们先将所有的边按照边权全排序,从小到大,对于当前每个操作,能用就用显然更优。考虑对于一个操作而言它做的贡献,这个题可以先不思考我们每个操作可以具体的连那些边,因为点的范围都到1e9了,显然是抽象的。u和v可以连边当且仅当(u=(v+a_i))%(N),换句话说可以写成(u=v+a_i+k*N)式子还可以转换成(u=v+k*gcd(a_i,N))(u和v在模gcd(a_i,N)的意义上是同余的)。也就是说只使用第i个操作时所有模(gcd(a_i,N))的值相同的点都可以连边。这时整个图就被分成了(gcd(a_i,N))个联通块,因为模(gcd(a_i,N))共有(gcd(a_i,N))中结果。考虑如果一个一个操作的考虑的话无法确切的统计答案。考虑前i个操作一起,这个时候能够被连起来的点为(u=v+k_1*A_1+k_2*A_2+…+k_i*A_i+k_0*N),这个时候的联通块纪委即为(gcd(k_1*A_1,k_2*A_2,…,k_i*A_i,k_0*N))而这时每个操作的答案我们就可以通过差分轻松计算了…

F

未做…

发表回复

您的电子邮箱地址不会被公开。