danihao123's Blog

好有意思的题呢qwq

首先观察到一点，我们可以把所有装置按照$a_i$的奇偶性进行分类（也可以说是黑白染色？）。容易发现任意偶数的最大公约数都至少是2，所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数，可以这么证一下（感谢金爷！）：

那两个奇数可以分别设成$2x + 1$和$2y + 1$，然后他们的平方和就是$4(x^2 + y^2 + x + y) + 2$。然后思考一点，就是一个奇数的平方一定是奇数，所以说那个平方和是一个偶数。但是，如果一个完全平方数是偶数，那么它的算术平方根一定是偶数。然而，一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2，所以不行。

所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系，最小割高一波即可。

代码（常数卡卡卡……只能用pb_ds的蛤希表了）：

膜了一发BYVoid的题解……竟然搞懂了

这首先是个非常简单的线性规划，就是有若干限制（每天要求的志愿者），形如：

$$P_i = X_a + X_b +\ldots + X_c\geq A_i$$

（这里用$X_i$表示第$i$类志愿者雇佣了多少个，$P_i$表示第$i$天的志愿者总数，$A_i$同原题面）

且最小化总费用。

既然我们我知道$P_i\geq A_i$，那么说明$P_i$一定可以表示为$A_i + Y_i$（$Y_i\geq 0$）。然后这样限制就变成了：

$$P_i = X_a + X_b +\ldots + X_c + Y_i = A_i$$

这个长得很像可以流量平衡的样子，但是流量的变动是表示不了的……

然后假设$P_0 = 0$且$P_{n + 1} = 0$，这样就可以对限制差分一下，我们就有了$n + 1$个限制，然后这个式子就可以流量平衡做了（因为不考虑常数项的话，同一变量只可能在两个限制中出现，并且一正一负，这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项，通过源或者汇连边即可表达）。

然后由于志愿者无限，所以这个东西也一定有解……

我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解，比我透彻多了。

代码：

流量平衡入门中……

我竟然想民白了……

这个题就是要求每个点在且仅在一个环中，这样每个点的入、出度都是1。出度肯定是1，接下来我们想想怎么保证入度为1。

我们建两排点（也可以说是拆点？），一排表示流出，一排表示接受。然后流出点向相邻的接收点连边，费用的话考虑是否和原来这一格的方向不一样就行了。

这个不需要判断是否满流啥的……因为一定有解（比如说每个行构成一个环啥的）。

代码：

啊啊啊我为什么要去颓费用流啊……

这个题可以保证每个人的车最后都会被修，所以说也就是让你最小化总等待时间辣！

直接考虑给一个技术人员建时间轴是麻烦而不可取的。我们考虑一点，对于每一个技术人员，若总共修了$t$辆车，那么第$i$个来找他修车的人会影响后面人的等待时间，换言之我们可以认为第$i$个来修车的人给答案做出了$c\cdot (t - i + 1)$（这里用$c$表示他自己的修车时间，注意他也会影响他自己）的贡献，似乎可以苟最小费用最大流呢。

但问题在于我们并不能提前知道$t$是多少，并且这样的话费用不是递增的，一个人可能会优先考虑到后面的位置去修车。那么我们考虑倒过来，去考虑倒数第$i$个来修车的人的贡献，显然这个贡献是$c\cdot i$。然后接下来就肥肠简单了，，，

代码：

二次函数费用流的入门题……我真太弱了……

可以给比赛、队伍都建点，然后$S$向每个比赛连容量为1的边，每个比赛向队伍连容量为$1$的边，来表示赢家是谁。这样一来一次比赛只有一个队伍赢了。

考虑怎么处理那个二次函数费用。费用函数为$f(x, y) = C x^2 + D y^2$，由于一个队伍的总比赛次数是已知的，所以$y$不需要，不妨假设一个队伍有$t$场比赛，则费用函数为$f(x) = C x^2 + D(t - x)^2$。

对这个函数做差分：$\Delta f(x) = f(x + 1) - f(x) = 2Cx - 2D(t - x) + C + D$，然后这个差分是单调不降的。因此我们对所有差分都从队伍向$T$连边（费用为这一点的差分），这样一来的话会优先选择费用小的边，保证这个队伍的费用一直合法。

代码：

三分套三分入门题……

策略肯定是从A走到AB上一点，然后再走到CD上的一个点，再向D走。

很显然答案函数是一个关于那两个点下凸的东西（不会证？GeoGebra之类的东西画一下就好啦！还不如像我这样口胡），所以我们可以先对第一维三分，然后套上对第二维的三分……

代码：

杜教筛模板题……（然而常数卡卡卡）

我还是讲一讲基础的东西吧……

先考虑求欧拉函数的前缀和，我们先找一个它的卷积（这里用$f=\varphi\ast 1$，且设$g = 1$），发现有（用$S$表示原函数的前缀和）：

$$\sum_{i = 1}^n f(i) = \sum_{i = 1}^n g(i)\times S(\lfloor\frac{n}{i}\rfloor) = \frac{n(n + 1)}{2}$$

第二个和式的第一项是$g(1)\times S(n) = S(n)$，也就是我们需要的答案。这样的话我们把第一项分割出来，后面的项大力求，然后用$\frac{n(n + 1)}{2}$减去那些项就得到了第一项。并且注意到$\lfloor\frac{n}{i}\rfloor$的取值种类是$\sqrt{n}$级别的，又可以大力优化一波。然后考虑预处理$O(n^{\frac{2}{3}})$级别的前缀和（时间和空间都允许），再优化一波。然后考虑把没预处理的状态扔一个哈希表里（反正看起来不会很多），又优化一波……

这样复杂度就是$O(n^{\frac{2}{3}})$的了……（又不会证了）

求莫比乌斯函数的前缀和的方法类似（并且更简单一点）……

代码（又被卡成苟了）：

当年在考场上一点反演都不会啊啊啊啊啊啊

这题虽然牵扯到了对积的反演，但其实也不是很难。先让我们大力推导一波（逃

考虑枚举柿子中的$f[(i, j)]$中的最大公约数（设为$k$），然后式子变成了（这里不妨偷个懒，钦定$n\leq m$）：

$$\prod_{k = 1}^n f[k]^{\sum_{i = 1}^n \sum_{j = 1}^m\:[(i, j) = k]}$$

然后发现上面那个指数就是Problem b的式子，显然可化为$\sum_{d = 1}^n \mu(d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor$。然后似乎化简没有余地了，但是根据直觉，我们可以钦定$T = kd$，然后枚举$T$。

然后柿子变成了：

$$\prod_{T = 1}^n (\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})})^{\lfloor\tfrac{n}{T}\rfloor \lfloor\tfrac{m}{T}\rfloor}$$

柿子中的$\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})}$是一个类似狄利克雷卷积的东西（取完对数就是了），可以枚举约数预处理。并且这个东西很不错的一点就是上面的指数是莫比乌斯函数，可以取到的值只有那三种，不需要快速幂。

然后剩下的部分就和通常的反演题一般无二了……

代码（卡线过的蒟蒻……求轻喷……但我在LOJ上跑的还挺快的）：

这不是可并堆裸题吗……我这种傻逼只会用线段树合并做

显然一个集合的中位数可以用平衡树或者权值线段树求出，然后为了方便合并我用了权值线段树。

然后考虑对于一个递减的序列，选择中位数一定更优，一个递增的序列当然xjb选即可。我们可以用一个栈来维护当前的所有答案区间，然后考虑一个新的点加进来。这个点的答案如果比栈首答案小，那么就违反了单调不降的要求，我们需要把两段合并。然后完了……

代码：

现在才明白卷积真的是the deep, dark fantasies……（逃

首先约去$q_i$，得到：

$$E_j = \sum_{i < j}\frac{q_i}{(j - i)^2} - \sum_{j < i}\frac{q_i}{(j - i)^2}$$

注意到如果很容易得到等式前半部分的高效求法，后半部分把序列反过来就能做了。

那么我们会发现，设$g_x = \frac{1}{x^2}$，然后式子前半部分（姑且称作$p_j$）可表示为：

$$p_j = \sum_{i < j} q_i g_{j - i}$$

这不就是个卷积吗？FFT一波即可。

代码：