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最左边和最右边比当前前缀和大的位置，相减即是答案，取最大。 $m = \lfloor \frac{an+b}{c} \rfloor$. $f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$: 当 $a \ge c$ or $b \ge c$ 时，$f(a,b,c,n)=(\frac{a}{c})n(n+1)/2+(\frac{b}{c})(n+1)+f(a \bmod c,b \bmod c,c,n)$；否则 $f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)$。 $g(a,b,c,n)=\sum_{i=0}^n i \lfloor\frac{ai+b}{c}\rfloor$: 当 $a \ge c$ or $b \ge c$ 时，$g(a,b,c,n)=(\frac{a}{c})n(n+1)(2n+1)/6+(\frac{b}{c})n(n+1)/2+g(a \bmod c,b \bmod c,c,n)$；否则 $g(a,b,c,n)=\frac{1}{2} (n(n+1)m-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1))$。 $h(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c} \rfloor^2$: 当 $a \ge c$ or $b \ge c$ 时，$h(a,b,c,n)=(\frac{a}{c})^2 n(n+1)(2n+1)/6 +(\frac{b}{c})^2 (n+1)+(\frac{a}{c})(\frac{b}{c})n(n+1)+h(a \bmod c, b \bmod c,c,n)+2(\frac{a}{c})g(a \bmod c,b \bmod c,c,n)+2(\frac{b}{c})f(a \bmod c,b \bmod c,c,n)$；否则 $h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)$。

Problem B

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

Problem C

Unsolved.

Problem D

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

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)

Problem G

Unsolved.

Problem H

Upsolved by dream_cloud.

Problem I

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

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$，过了。

复杂度玄学。