最近感觉状态不知道咋回事….每次写出来基本都没有编译错误且一次性过样例，然而完全都做不到1A，甚至要五六发才能过。真奇怪

A City

WD 签到

M value

题意：给两个100000长数列$a,b$，选一堆1到n之间的数，最终收益是
$$
\sum _ {i被选}a[i]-\sum _ {i\ne j都被选且i|j,i\ne1}b[j]
$$
其中$b[j]$是可以被不同的i减很多次的

解：显然$2^1,2^2,2^3,2^4$与$3^1,3^2,3^3$以及其它的互不干扰。可以分开统计。发现数的数量减少得很快，可以直接对每一组暴力枚举。

E Flow

合作 & LYF写下面的题解几乎完全照搬LYF写的

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

一开始读错题浪费了好多时间（以为路径长度不相同）

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

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

这个过程中不需要关心容量被减的是哪条边，因为当把图操作到流量和最大值相等的那一刻一定刚好把被减的用光或是还剩着，不会有不可行的情况。

C Dirichlet k-th root

狄利克雷卷积相关

H King

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

解：

假设长度大于$\frac{n}{2}$，则随机取一个位置$x$，则$a[x],a[x+1]$或$a[x],a[x+2]$相邻出现在最长等比数列里的概率是$\frac{1}{4}$，因此随机取$m$个位置检测的话，找不到最长等比数列的概率为$(\frac{3}{4})^m$。每次找时暴力向左右两端延伸看长度即可。写之前对题目意思比较清晰，但写的时候搞错了，以为只需要把长度大于$\frac{n}{2}$的等比子列长度任意输出一个即可，事实上完全可以构造出有两个等比子列长度都大于$\frac{n}{2}$的情况，因为两个数列中有些数是可以共用的。后来因为$m$取值过大(50以上)T了。其实稍微计算一下就可以知道，不管n的数据规模，m大于30时其实错误率就已经在万分之一到千分之一级别了，也就是说需要有一千到一万组数据才期望能卡掉。复杂度$O(n*m)$

LYF在赛场上也想出了一个方法，因为概率是$\frac{1}{4}$，因此把每个数和后两位的比值都拿出来，则该比值应该在总数中大约占比大于$\frac{1}{8}$。把所有符合的比值都尝试找一遍最长延伸即可。看起来是$O(n)$非常优秀，但是一些细节比较难写，比如从哪里开始尝试延伸，如果把位置记下来的话怎么记？数列中可能同时存在很多个比值相同的长度各异的等比子列，如何区分它们。

G Happiness

LYF 大模拟下面题解直接照搬LYF’s blog

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

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