2018 ECNU AK ICPC/CCPC Typing Speed Contest

One,Two,Three,AK

自不量力的Xiejiadong去刚J这道数学题，浪费了大量时间搞假算法，背大锅。

Problem A

Solved by dreamcloud. 01:26:50(+1)

题意：给定一个01串$S$,求出它的一个尽可能长的子串$S_{i..j}$，满足存在一个位置$i \le x \lt <j$, $S_{i..x}$中0比1多，而$S_{x+1..j}$中1比0多。求满足条件的最长子串长度。

题解：把0看作-1，1就看作1，0比1多，即累和为负，反之为正。做完前缀和，枚举位置x，分别找到x最左边和最右边比当前前缀和大的位置，相减即是答案，取最大。

Problem B

Solved by oxx1108. 03:46:24(+7)

Problem C

Unsolved.

Problem D

Solved by oxx1108. 00:45:57(+)

题意：给若干区间取其中$k$个区间使得公共部分和最大。

题解：签到，区间排个序，右端点扔优先队列里即可。经典的面试题套路。

Problem E

Solved by Xiejiadong. 03:52:04(+2)

题意：所有区间的众数出现的次数组成数列，求第$k$小的数。

题解：考虑二分答案，验证答案是否$\ge mid$。

checker 的写法是，枚举左端点，然后找到第一个出现次数达到$mid$的右边界，显然，这个边界右侧的都成立。用双指针法解决。

时间复杂度$o(nlogn)$。

Problem F

Solved by oxx1108. 00:33:40(+2)

题意：一堆括号，求一共有多少个子串是合法的匹配括号

题解：维护前缀和以及前缀和值出现的个数，当出现右括号时将前缀和加一的个数清零即可。计数就计之前出现过多少个相同的数。

没开LL挖了一发，忘记处理负数挖了一发。

Problem G

Unsolved.

Problem H

Upsolved by dream_cloud.

题意：$Ans=\sum_{i=1}^{n}\sum_{j=i}^{n}[max{A_i,A_{i+1},...,A_{j} }=max{B_i,B_{i+1},...,B_j}]$ ，表达式为真，则为1，否则为0.

题解：枚举A中的每个位置x，找到往左第一个大于等于A[x]的，往右第一个大于A[x]的（单调栈）。在B中找到与A[x]值相等的且最靠近x的两边的位置。易得对答案的贡献。

Problem I

Solved by dreamcloud. 02:52:10(+)

题意:$n*m$的格子，其中有一些格子灯亮着。沿途的格子必须是亮着的。站在最开始是亮的格子上可以花费一个金币点亮一行或者一列的灯。问你要从左上角到右下角，最少花费。

题解：类似最短路，其实就是在那些一开始就是亮的格子间转移。从一开始就是亮的格子可以往相邻不超过一行或一列的所有格子，花费一个金币转移，相邻两行或两列的原来亮的格子也可达到。或者不花钱上下左右走到原来就是亮的点。最短路跑一下

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 02:23:14(+3)

题意：求$max_{1\le i,j\le n}^{a_i\ge a_j}(a_i$ $mod$ $a_j)$。

题解：当$a_j$比较大的时候，我们考虑枚举约数。

比如枚举$2$的时候，肯定找比$(a_i+1)/2$大的数里面最小的，这样的差值一定最大。

那么当小的时候，就直接暴力枚举。

这个大和小的边界比较难调，需要计算一下，最后手动设了$100$以及加了个剪枝，过了。

复杂度玄学。