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 \limits_{i = 1}^{mx} S_i \cdot e_i) \cdot E\)，其中 \(e_i\) 为第 \(i\) 个平面的法向量， \(E\) 为选择的方向，最大值显然即为 \(|\sum \limits_{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老脑瘫了，不知道在写啥，各种写反。