Difference between revisions of "2018 ECNU AK ICPC/CCPC Typing Speed Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 56: | Line 56: | ||
Solved by Xiejiadong. 02:23:14(+3) | Solved by Xiejiadong. 02:23:14(+3) | ||
− | 题意:求$max_{a_i\ge a_j}(a_i$ $mod$ $a_j)$。 | + | 题意:求$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$,过了。 |
Revision as of 10:55, 5 October 2018
One,Two,Three,AK
Problem A
Solved by dreamcloud. 01:26:50(+1)
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
Unsolved.
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$,过了。