2015 EC Final

排名	当场过题数	至今过题数	总题数
63/283	5	?	13

B

upsolved by JJLeo

题意

给定一个长度为 $n$ 的环，初始身上有 $x$ 元钱，每经过一个位置身上的钱会变为 $max(0,x+a_i)$，问初始 $x$ 最少是多少，才能保证存在一种走 $\le P$ 步的方案使得最终钱数 $\ge G$。($1\le n\le {10}^5$，$1\le G,P\le {10}^{18}$，$|a_i|\le {10}^9$)

题解

二分答案，先走一圈，如果变化 $\le 0$，说明再走几圈不会更优，直接取前缀最大值即可；否则，再走一圈，如果没有变化，说明一圈中出现了和 $0$ 取 $max$ 的情况，再走多少圈都不会变，直接取前缀最大值即可；如果有变化，一定是变大了，说明一圈中没有出现和 $0$ 取 $max$ 的情况，再走多少圈也不会出现，因此无限绕圈走到还剩下两圈长，再取前缀最大值就好了。总时间复杂度为 $O(n\log G)$。

其实可以 $O(n)$，考虑要不要和 $0$ 取 $max$，要的话一开始取 $0$ 就好了，然后按上面的方法判断；不要的话走的时候强制不和 $0$ 取 $max$，但最后答案要和前缀最小值的相反数取 $max$，如果要无限绕圈显然一圈的价值要为正，因此前缀最小值只需考虑第一圈的情况。

C

upsolved by

题意

给定一个字符串的 $SA$ 和 $manacher$ 数组，问字典序最小的满足条件的字符串。字符集为小写字母。$n\le {10}^5$

题解

$sa[1]$ 一定放 $a$ ，显然 $S[sa[i]]\ge S[sa[i-1]]$ ，如果$rank[sa[i-1]+1]>rank[sa[i]+1]$ 显然 $S[sa[i]]>S[sa[i-1]]$ ，否则可以相等。

通过 $manacher$ 数组可以判断每个位置是否相等，相等可以用并查集合并，不等最多有 $n$ 个关系。

不合法情况：

• 其中一个字符超过 $z$
• $manacher$ 数组中长度不能超过串长，并且不能超过左右边界
• $manacher$ 数组偶数位长度应该为偶数，奇数位应该为奇数
• 还没过不清楚还有没有其他的

D

solved by Bazoka13

题意

题解

F

solved by 2sozx JJLeo

题意

$n$ 个人

题解

J

upsolved by 2sozx Bazoka13

题意

题解

K

upsolved by 2sozx

题意

给定一个三维凸包，问映射到一个平面上的最大面积是多大。$n\le 50$

题解

显然可以 $O(n^4)$ 找到所有三维凸包上的平面，之后随机多次，每次随机一个法向量，表示映射的方向，这样可以找到所有对答案有贡献的平面。

考虑用这些平面构成答案，即为$(\sum _{i=1}^{mx}{S}_i\cdot e_i)\cdot E$，其中 $e_i$ 为第 $i$ 个平面的法向量， $E$ 为选择的方向，最大值显然即为 $|\sum _{i=1}^{mx}{S}_i\cdot e_i|$

PE就当过了吧

L

solved by 2sozx JJLeo

题意

题解

EGHI

upsolved by

题意

过于离谱。

题解

下次一定！

记录

0min：分题, MJX 冲 A
7min：MJX AC, ZYF 冲 M
20min：ZYF AC, CSK 冲 D
38min：CSK AC, MJX ZYF 疯狂看 L
172min：MJX WA2 后 AC,不知道开哪题了, CSK 冲 J
296min：想了半天 F 的计数, 终于想起来dp了, WA1 后 ZYF AC
till end：J 'PE' 了10发，无了
after end：这UVALive感觉出问题了，J应该是过了的

总结

Dirt

F(+1)：mjx经典脑瘫瞎写，不用乘2

L(+2)：zyf老脑瘫了，不知道在写啥，各种写反。