AtCoder Beginner Contest 210题解
2024-10-21 04:13:57
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
未做...
最新文章
- FZU月赛20160416 ABEF
- Hadoop中HDFS的管理
- ZOJ 1067 Color Me Less
- WIN8+VS2013编写发布WCF之三（调用）
- 阻止浏览器关闭 区分刷新和关闭 自试IE可用
- Hibernate逍遥游记-第6章 通过Hibernate操纵对象(select-before-update)
- hadoop namespace
- java编码问题
- thinkphp 3.2 导入第三方类库的两种方式
- margin外边距合并问题以及解决方式
- View绘制流程
- Spring Boot基础讲解
- Numpy常用API
- day 30 客户端获取cmd 命令的步骤
- as3.0影片简介失效，不阻碍下面影片简介的事件
- javascript extend
- ANTLR#1：描述一个简单计算器
- selenium python 启动Firefox
- HDUOJ---2112HDU Today
- Give $20/month and provide 480 hours of free education