======2020/05/02——2020/05/08周报======

=====团队训练=====

2020.5.2 [[acmgooglecup2011invitationalprogrammingcontest|ACM Google Cup 2011 Invitational Programming Contest]] ''prob:4/6/10'' ''rank:11/69''

=====林星涵=====

====专题====

[[lotk_树套树|树套树]]  ps:以前的一些链接搬运中，还有一个坑待填

=====陶吟翔=====

====专题====

[[mst|最小生成树]]

[[toposort|拓扑排序]]


=====郭衍培=====

====专题====

[[多项式对数函数|多项式对数函数]]

=====本周推荐=====

林星涵： [[https://www.luogu.com.cn/problem/P4278|洛谷P4278 带插入区间K小值]] 树套树、块状链表模板，代码量较大，仅作练习代码能力食用。

陶吟翔：Codeforces597Div2-D，题目大意是有$n$个城市，现在要让每个城市都通上电，可以选择在若干个城市建造发电厂，在第$i$个城市建造发电厂需要花费$c_i$的钱，或者选择在两个城市之间连接电缆，在第$i$个城市和第$j$个城市之间连接电缆需要花费$(k_i+k_j) \times d$的钱，$d$为两个城市间的曼哈顿距离，最小化总花费。解法十分巧妙，首先在城市与城市之间建边，并且建立一个超级源点和每个城市连边，边权为在每个城市建造发电厂的花费。这样一来，我们对新图求最小生成树的值即可，这样可以保证至少有一个城市建造了发电厂，每个城市都通上电且花费最小。具体代码可以在最小生成树的专题里找到，[[http://codeforces.com/contest/1245/problem/D|这里是网址]]

郭衍培：[[https://www.luogu.com.cn/problem/P1891|洛谷1891 疯狂LCM]] 给定正整数n,求$\sum^n_{i=1}\text{lcm}(n,i)$。推式子，不难发现其实是要求$n\sum_{d|n}\sum^d_{i=1}i[\gcd(i,d)=1]$。值得注意的是，$\sum^d_{i=1}i[\gcd(i,d)=1]=\frac{\phi(d)}{2}d$。于是枚举d即可。