Difference between revisions of "2018-2019 ACM-ICPC, NEERC, Southern Subregional Contest, Qualification Stage"
(5 intermediate revisions by the same user not shown) | |||
Line 32: | Line 32: | ||
Solved by zerol. 00:55 (+) | Solved by zerol. 00:55 (+) | ||
+ | |||
+ | 题意:把若干个整数分解成互不相同的二元组的积。 | ||
+ | |||
+ | 题解:相同的数一起搞,暴力枚举因子。 | ||
== Problem E == | == Problem E == | ||
Solved by zerol. 01:49 (+) | Solved by zerol. 01:49 (+) | ||
+ | |||
+ | 题意:给出一个数列,每次询问一个数的最左和最右出现位置,将这两个位置之间的数都改成这个数。 | ||
+ | |||
+ | 题解:用 set 记录数列中的每一段连续相同数字。同时每个数字单独开一个 set 记录在哪些段出现。每次操作就是删除若干段并插入一段。 | ||
== Problem F == | == Problem F == | ||
Line 46: | Line 54: | ||
Solved by zerol. 01:08 (+) | Solved by zerol. 01:08 (+) | ||
+ | |||
+ | 题意:给出一棵树上移除每一条边后形成的两个连通块的最大顶点标号对,构造这棵树。 | ||
+ | |||
+ | 题解:发现结果一定能够变成以 n(最大标号)为根的一棵菊花。然后如果 (n,x) 出现了 k 次,那么从 n 连一条有 k 条边的链到 x,中间填的点标号必须小于 x。 | ||
== Problem H == | == Problem H == | ||
Line 64: | Line 76: | ||
Solved by zerol. 00:09 (+) | Solved by zerol. 00:09 (+) | ||
+ | |||
+ | 温暖的签到。 | ||
== Problem K == | == Problem K == |
Latest revision as of 09:33, 17 October 2018
欢乐信心场。
Problem A
Solved by ultmaster. 00:17 (+)
题意:挺奇怪的。要把一些东西安排一下,做完一件事情必须要休息一段时间,然后最少要多久完成。每件事情的开始时刻在剩余系下是有规定的。
题解:反正贪心往前放就好了。
Problem B
Solved by ultmaster. 01:32 (+2)
题意:从某个点出发向右走,有一些区间可以横着走,还有一些区间再向右走的同时会向下掉。求问最长能走多少。
题解:肯定是从横着走的区间的左端点开始的。然后滑动窗口或二分都可以。
DIRT1:没有处理最后一段以后的问题。二分边界错了。(开闭搞晕了)
DIRT2:没有意识到等于 0 的时候也会凉凉。
Problem C
Solved by kblack. 00:47 (+1)
题意:消消乐,$x+x = 2x$,问消光至少要加几个。
题解:除掉 $gcd$ 以后都是 $2$ 的幂,贪心从小到大合并,少的就加。
Problem D
Solved by zerol. 00:55 (+)
题意:把若干个整数分解成互不相同的二元组的积。
题解:相同的数一起搞,暴力枚举因子。
Problem E
Solved by zerol. 01:49 (+)
题意:给出一个数列,每次询问一个数的最左和最右出现位置,将这两个位置之间的数都改成这个数。
题解:用 set 记录数列中的每一段连续相同数字。同时每个数字单独开一个 set 记录在哪些段出现。每次操作就是删除若干段并插入一段。
Problem F
Solved by kblack. 00:27 (+)
温暖的签到。
Problem G
Solved by zerol. 01:08 (+)
题意:给出一棵树上移除每一条边后形成的两个连通块的最大顶点标号对,构造这棵树。
题解:发现结果一定能够变成以 n(最大标号)为根的一棵菊花。然后如果 (n,x) 出现了 k 次,那么从 n 连一条有 k 条边的链到 x,中间填的点标号必须小于 x。
Problem H
Solved by ultmaster. 00:38 (+)
题意:有一个形状奇怪的东西,用 1x2 的瓷砖去填,瓷砖只能横着放。放不下就得把瓷砖劈成两半。问最少劈几块瓷砖。
题解:求一下最少需要几块 1x1 的,然后除以 2 取上整就好了。
Problem I
Solved by zerol. 00:05 (+)
温暖的签到。
Problem J
Solved by zerol. 00:09 (+)
温暖的签到。
Problem K
Solved by kblack. 01:37 (+)
题意:求一个数列最大中位数(偶数个取小的)大于 $m$ 的剖分。
题解:另 $b_i = b_{i-1}+(a_i \ge m)$,显然的 dp 的转移条件是 $b_i-b_j > \lfloor{\frac{j-i}{2}}\rfloor$,整理移项后是 $2b_i-i > 2b_j-j$,套个树状数组。
Problem L
Solved by kblack. 02:11 (+2)
题意:两面镜子上有感应器,你可以射一根光束,问最多射到多少感应器。
题解:观察发现,公差(换边一次距离) $x$ 的,因为覆盖的点是超集,一定比公差 $x(2n+1)$ 的好,所以只要测试公差是 $2$ 的幂的就好了。