2018 ECNU AK ICPC/CCPC Typing Speed Contest

From EOJ Wiki
Jump to navigation Jump to search

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

复杂度玄学。