A.City

WD 签到

C.Dirichlet $k$-th root

数神WD

E.Flow

合作 & LYF写

题意：给定一张网络图，边带权，1为起点n为终点，1到n的每条路径都没有交点，且每条路径长度都相同。可以进行任意次操作，每次操作使得一条边容量-1，另一条边容量+1，问使得最大流达到最大的前提下，最少的操作数。

一开始读错题浪费了好多时间

然后WD提供了一个贪心的思路，就是先把能跑的流全部跑掉，这时候每条路径的残余网络边的最小值一定为0，然后把路径根据边值为0的个数从小到大排序，优先从填个数小的边一定是最优的。

发现可以优化一下这个过程：对于每条路径和$i\in[0,len]$（$len$为路径长度）可以预处理出，有多少流量是可以通过只填$i$个值为0的边来使其产生流量的。预处理完之后把所有路径的情况累加起来，就可以从小到大贪心了。

这个过程中不需要关心容量被减的是哪条边，因为可以到最后再选择那些仍然>0的边来作为被减的。

G.Happiness

LYF 大模拟

英语阅读+读入处理，先把要读的内容以字符串取出来，然后用sscanf来处理读入还是挺香的

暴力的运算次数整体是$10!O(lgn)$，估计测试用例没有极端数据，所以写的差一点也能过。常数主要还是递归传参部分，比如递归的时候如果直接创建一个变量来记录原状态其实很费时间，还原状态是可以$O(1)$完成的，优化了一下只要400+ms

H.King

ZRC & LYF

找出模意义下的最长等比数列的长度，若长度$<\frac{n}{2}$则只要输出-1

只考虑长度$\geqslant \frac{n}{2}$的情况，可以发现很密集，随机选择一个数$a_i$，那么$a_i$与$a_{i+1}$或者$a_i$与$a_{i+2}$是等比数列上相邻的两个数这一事件的概率是很大的，对于随机数据来说应该是$\frac{3}{8}$，但是对于构造过的数据好像不太好算，但是概率还是比较高的。只要选中一次，用这个比值来$O(n)$计算这一比值下等比数列的长度，那么得到的结果就是正确答案。只要随机选择几十次，选中的概率就趋近于1了。

还有一个想法是对于每个数$a_i$，记录和$a_{i+1}$和$a_{i+2}$的比值，这样记录2n个比值，可以发现，最长等比数列的比值一定会出现至少$\frac{n}{4}$次（可能还不止）（构造一种比值出现次数最少的情况，前$\frac{n}{4}$个数每隔两个空放一个，占用$\frac{3n}{4}$个空位，后面$\frac{n}{4}$个数相邻放置）。这样的比值最多只有8个，依次验证取最大值即可。

M.Value

ZRC

枚举$i$，把所有$i^k$取出来，发现最多当$i=2$时有20个数，且个数随$i$增大下降的非常快，可以直接暴力枚举