0x0
C
by Nerovix(自闭版)
没看出如来corner case，我背锅。
其实是n+1个圆把平面划分成了很多区域，每个区域内答案是一样的。那么如果某个点取到最优，一定可以挪动这个点使得它从内或是从外贴近某个圆的圆周。枚举贴近的是哪个圆的圆周，剩下的圆与这个圆求交，转弧覆盖。
D
By Margarita
经典场上不会做，场下傻逼题
当进制较小时，随进制增长位数掉得很快，那么我们可以拆成2个部分，对进制\(2\sim 10000\)暴力跑过去，对于\(>10000\)的进制通过枚举总位数\(d\)和第一个值\(a\)，显然必须满足\(a*10000^d\le n\land a\le nowans\)这两个数才是有效的，令进制为\(x\)，需要满足\(a*x^d\le n\land a*x^d+(nowans-a)*x^{d-1}>n\)才是有效的进制，满足这几个条件后的\(x\)的数量级显然是\(\log\)的，之后就随便做了。
G
By Margarita
场上我没看这题，感觉看了的话应该能做个七七八八（？），就是一个根号分治和下取整的小trick，还是每题都要看一遍啊。。。
题目等价于求
\[ \frac{1}{m^{\underline{n}}}\sum_{i=1}^n\sum_{j=1}^mm^{\underline{n-1}}\cdot\frac{1}{L}\sum_{k=1}^L\lceil\frac{a_i+b_j}{k}\rceil \]
依赖上取整\(\lceil\frac{x}{k}\rceil=\lfloor\frac{x+k-1}{k}\rfloor\)进行化简得
\[ n+\frac{1}{mL}\sum_{k=1}^L\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{a_i+b_j}{k}\rfloor \]
（之后除法均为下取整）注意到有
\[ \frac{a_i+b_j}{k}=\frac{a_i}{k}+\frac{b_j}{k}+[a_i\%k+b_j\%k\ge k] \]
故上式为
\[ \sum_{k=1}^L\left(m\sum_{i=1}^n\frac{a_i}{k}+n\sum_{j=1}^m\frac{b_j}{k}+\sum_{i=1}^n\sum_{j=1}^m[a_i\%k+b_j\%k\ge k]\right) \]
对于一个确定的\(k\)，上式显然可以用树状数组做到\(O(n\log k)\)的复杂度。
由于是除法，故考虑根号分治，取\(B=\sqrt{\max a_i+\max b_j}\)，上式为
\[ \sum_{k=1}^{\min\{B,L\}}\left(m\sum_{i=1}^n\frac{a_i}{k}+n\sum_{j=1}^m\frac{b_j}{k}+\sum_{i=1}^n\sum_{j=1}^m[a_i\%k+b_j\%k\ge k]\right)+\\ \sum_{k=1}^Bk\cdot\left|\left\{(i,j,x)|\frac{a_i+b_j}{x}=k\land B\le x\le L\right\}\right| \]
前面一坨东西能用树状数组\(O(Bn\log B)\)处理，考虑后面的。算算后面的式子每一项的贡献可以化为
\[ \sum_{k=1}^B\sum_{i=1}^n\sum_{j=1}^m\max\left(0,\min\left(\frac{a_i+b_j}{k},L\right)-B\right) \]
考虑这个式子怎么做，\(a_i+b_j\ge kL\)部分的贡献是\(L-B\)，\(a_i+b_j<Bk\)部分的贡献是\(0\)，故我们只关心\(Bk\le a_i+b_j<Lk\)即\(Bk-a_i\le b_j<Lk-a_i\)部分的贡献。此时上式中的\(\min\)和\(\max\)没有了，变为
\[ \sum_{k=1}^B\sum_{i=1}^n\sum_{j=1}^m\frac{a_i+b_j}{k}-B \]
套用之前的处理即可求出该式，由于\(j\)连续且随着\(i\)的增长单调减，故可以维护一个双指针来往树状数组里加减东西，复杂度同为\(O(Bn\log B)\)。
综上，我们在\(O(Bn\log B)\)复杂度内解决了此题。
刚开始我还写了个主席树来求下半部分的贡献，然后就T飞了，然后发现可以排序a，然后就没事了，诶嘿
I
by Nerovix
先floyd。然后假设c(x,y)表示\(x\to y\)在\(v[i]\to v[i+1]\)中出现了多少次。那么题意即找到u,v，最大化
\[ save(u,v)=\sum_{s,t}c(s,t)\max\{0,d(s,t)-d(s,u)-d(v,t),d(s,t)-d(s,v)-d(u,t)\}\\ =\sum_{s,t}c(s,t)\max\{0,d(s,t)-d(s,u)-d(v,t)\}+\max\{0,d(s,t)-d(s,v)-d(u,t)\}\\ =\sum_{s,t}c(s,t)\max\{0,d(s,t)-d(s,u)-d(v,t)\}+\sum_{s,t}c(s,t)\max\{0,d(s,t)-d(s,v)-d(u,t)\}\\ =w(u,v)+w(v,u) \]
考虑咋求w(u,v)。
枚举u,t,把s按照d(s,t)-d(s,u)排序，把v按照d(v,t)排序。然后枚举v。观察哪些s会对此时的u,v和t产生贡献。发现由于已经对s排了序，max不取0的是一段区间。那么区间求和一下（由于v也排了序，实际实现时采用双指针），把此时的贡献累加到w[u][v]上去。最后选最大的w[u][v]+w[v][u]。
复杂度\(O(n^3\log n)\)。由于log来自排序，且本题时限5s，可以通过。