2015-2016 Nizhny Novgorod SU Contest

From EOJ Wiki
Revision as of 14:26, 21 March 2018 by Ultmaster (talk | contribs)
Jump to navigation Jump to search

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 模板题。签到。