2015-2016 Nizhny Novgorod SU Contest

Problem A

Upsolved by kblack.

题意：若干工厂按比例需要其他某些工厂的产品，生产的产品可以分给别的工厂或销售，已知去年销售和互相供货的量，求按今年销量的需求每个工厂总共需要生产多少产品。

题解：显然的方程组复杂度过高，直接考虑迭代松弛即可。

注：使用 C++14 会无故超时，见鬼了！

Problem B

Solved by ultmaster. 01:01 (+)

题意：挺复杂的。英文水平不行。

题解：模拟。签到。

Problem C

Solved by ultmaster. 03:37 (+1)

题意：求 A-E 的字符串和 a-e 的字符串在建立合理映射并旋转后最多能有多少个位置相同。

题解：关键是要算出状态 $f(i,j,k)$ 表示旋转 $i$ 后 $j$ 对应 $k$ 的数量。置要用到的位为 1，然后做 25 次卷积。然后枚举置换求一求就好了。两倍的 NTT（$2 \cdot 10^5$）似乎不行，降到一半之后卡过了。也不知道常数为什么这么大。

Problem E

Solved by ultmaster.

题意：数列 $a$ 是一个 $0 \ldots n-1$ 的排列，由某种规则构造。询问一堆奇怪的式子。

题解：蛮无聊的一道题。发现规律之后瞎搞搞就好了。CF 的时限可能是乱给的，玄学常数优化（long long 改 int，递归改迭代）之后，900 多 ms 卡过去了。过得快的人位操作姿势都很高端。

所以问题来了：这么无聊的题现场居然不做？

Problem F

Solved by kblack. 01:47 (+3)

题意：给出三个点的坐标，丁字行的单和另两条边的长度，问是否能覆盖。

题解：分为三种情况：全部由短边覆盖，2个点由短边覆盖，1个点由短边覆盖（0个点可以转化为1个点），分类讨论即可。

Problem G

Upsolved by ultmaster. (-5)

题意：求 winner 数量的操作如下：将序列排序，求有多少个数比这个数前面的所有数加起来都要大。有修改操作。

题解：

ultmaster (题解中的方法):

利用 winner 数量不会太多的性质，可以使用当前找到的 winner 的前缀和寻找第一个符合要求的数，然后验证是否成立。不管是否成立都将前缀和替换成新的前缀和继续迭代。单次询问复杂度是 $O(\log MAX \log (n+m))$。要开一个 set 和一个树状数组然后交替插入询问。一开始不知道为什么写了二分树状数组，折腾了好久发现完全没用。 刚开始离散化也是比较麻烦的。由于是个多重集要考虑相等的元素算同一个还是算不同的。我的方法是增加 pair 的第二维强行把这些元素区分出来。但是结果好像还是没有避免序列最前面的两个数要特判的问题。

Problem H

Solved by zerol. 00:21 (+)

LCT 模板题。签到。