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)

题意：给若干个字符串，修改每个位置的字母有一个代价，问至少要多少代价可以使得每一个字符串存在一个位置与其他字符串这个位置的字母都不同。

题解：状压dp处理整块一样的字母的修改的代价（就是和减去最大的一个的代价），然后最后处理单个的修改。(一起处理的时候T了) 这题略卡常。

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 dreamcloud.

题意：$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

Upsolved by oxx.

题意：求次方迭代模某个数的值。

题解：扩展欧拉定理。不知道扩展的，分解质因数然后再套欧拉定理写到自闭。

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$以及加了个剪枝，过了。

复杂度玄学。