![loading..](https://cdn.luogu.com.cn/upload/image_hosting/rcuo9m9v.png)
![loading..](https://cdn.luogu.com.cn/upload/image_hosting/rcuo9m9v.png)
P2272 [ZJOI2007]最大半连通子图 题解
本题解相对于其他题解的特色有二: 一、深入分析了为什么要去重 二、给出了链式前项星的 O(m)O(m)O(m) 线性去重方式 下面进入正文。 不难发现,将原图缩点成一个DAG后,图中的每一条链都是一个半连通子图,而最长的链就是最大半连通子图。 注意:新图中一个点的权值为这个点代表的SCC的点数,一个链的长度为各点权值之和。 统计最长链的权值不难,可以使用拓扑排序或记搜实现。为了避免引入STL影响效率,本文统一使用记搜。 本题的难点在统计方案数。 统计最小生成树方案数、最短路方案数等经典题的解法会给我们启示,紧紧抓住三角不等式这一核心算式,不断更新答案并继承方案数,这种方法依然使用本题。 但有所不同的是,本题需要考虑重边。 认真思考不难发现,传统的 tarjan 缩点得到的DAG中会出现重边(这里的重边是..
更多通信基站覆盖问题 题解
本题来自于某次付费答疑,经本人后续查证,题目出自印度德里理工学院的一次期中考试。 题面 Let us consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose the residents of all these houses are avid cell phone users. You want to place cell phone base station..
更多P8458 「REOI-p1」打捞 题解
如果将所有数列都扩展到 kkk 的长度, 1e91e91e9 级别的数组肯定会时间空间双爆炸。 所以这个题要利用周期性。 不难发现,两个数列的最小正周期为 lcm(li,lj){\rm lcm}(l_i,l_j)lcm(li,lj) , 我们真正需要处理的是在这个最小正周期内的交叉积。 尽管如此,若 li,ljl_i,l_jli,lj 都是质数,他们的最小正周期也可以很长很长。遍历最小正周期求交叉积依然无法AC。 通过分析那 60%60\%60% 的数据我们可以发现,若 li,ljl_i,ljli,lj 互质,那么,在一个最小正周期中, aia_iai 中的每一个元素,都把 aja_jaj 中的每一个元素乘了 111 次,而且只乘了 111 次。那么我们可以利用分配律,得 ∑aiaj=∑(ai..
更多