Difference between revisions of "2018-2019 Southeastern European Regional Programming Contest (SEERC 2018)"
(Created page with "== Problem A == Unsolved. (-5) 题意:问有多少种方法将一个数拆成两个回文数。 题解:写了个暴力 T 飞。 == Problem B == Solved by ultmaster. 0...") |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 10: | Line 10: | ||
Solved by ultmaster. 01:32 (+) | Solved by ultmaster. 01:32 (+) | ||
+ | |||
+ | 题意:圆周上有 $n$ 个点均匀分布。求有多少三元点对满足能形成一个包含圆心的三角形。 | ||
+ | |||
+ | 题解:所有方案减去不好的就可以了。答案是 $\displaystyle \frac{n(n-1)(n-2)}{6} - n \sum_{i=0}^{(n-1)/2} i$。 | ||
+ | |||
+ | 处理 unsigned long long 要用到一点小技巧,把 2 和 3 先除掉。 | ||
== Problem C == | == Problem C == | ||
Solved by zerol. 00:53 (+) | Solved by zerol. 00:53 (+) | ||
+ | |||
+ | 题意:一棵树上有黑点和白点,选出 k 个黑点使得直径最小。 | ||
+ | |||
+ | 题解:由于数据范围很小,枚举直径长度和直径中心进行 dfs 计算黑点个数是否超过 k。由于直径长度可能为奇数,所以每条边上加一个点。 | ||
== Problem E == | == Problem E == | ||
Solved by ultmaster. 00:36 (+) | Solved by ultmaster. 00:36 (+) | ||
+ | |||
+ | 题意:平面上有若干个点,每次询问一个底边在 $x$ 轴上的,高为 $l$ 的等腰直角三角形里有几个点。 | ||
+ | |||
+ | 题解:因为 $l$ 不变,记录每个点要被包含的最左位置和最右位置,然后扫描线就好了。 | ||
== Problem F == | == Problem F == | ||
Solved by zerol & kblack. 03:29 (+2) | Solved by zerol & kblack. 03:29 (+2) | ||
+ | |||
+ | 题意:给两个长度为 n 的数列,通过不超过 2n 次区间修改成该区间的最大值/最小值的操作,使它们相同。 | ||
+ | |||
+ | 题解:a 能修改为 b 的充要条件是 b 相同相邻数字压缩后是 a 的子序列。把那个 a 中的子序列向左右扩张(一个一个把旁边不是子序列的值吃掉),然后修复边界。每个数字都有目标边界和不把不该吃掉的吃掉的边界,从能吃的开始吃,吃完了后会扩张两边的可行边界,用一个 set 维护一下,最后肯定能吃完。 | ||
== Problem G == | == Problem G == | ||
Solved by kblack. 01:21 (+) | Solved by kblack. 01:21 (+) | ||
+ | |||
+ | 题意:一种很奇怪的方格价值计算,修改是翻转某行或列。 | ||
+ | |||
+ | 题解:发现每有一个对齐的二的幂次边长的同色方格价值减少 $4$,而大方格同色等价于行的翻转状态相同且列的翻转状态相同,弄个类似线段树的东西统计一下乘乘加加。 | ||
== Problem I == | == Problem I == | ||
Solved by kblack. 00:47 (+1) | Solved by kblack. 00:47 (+1) | ||
+ | |||
+ | 题意:对于一个排列,对所有的逆序对连边,求最大独立支配集。 | ||
+ | |||
+ | 题解:等价于计数极大上升子序列,从边求排列可以用树状数组,求极大上升子序列可以用单调栈,当然这题数据范围小得一批怎么玩都行。 |
Latest revision as of 14:30, 31 October 2018
Problem A
Unsolved. (-5)
题意:问有多少种方法将一个数拆成两个回文数。
题解:写了个暴力 T 飞。
Problem B
Solved by ultmaster. 01:32 (+)
题意:圆周上有 $n$ 个点均匀分布。求有多少三元点对满足能形成一个包含圆心的三角形。
题解:所有方案减去不好的就可以了。答案是 $\displaystyle \frac{n(n-1)(n-2)}{6} - n \sum_{i=0}^{(n-1)/2} i$。
处理 unsigned long long 要用到一点小技巧,把 2 和 3 先除掉。
Problem C
Solved by zerol. 00:53 (+)
题意:一棵树上有黑点和白点,选出 k 个黑点使得直径最小。
题解:由于数据范围很小,枚举直径长度和直径中心进行 dfs 计算黑点个数是否超过 k。由于直径长度可能为奇数,所以每条边上加一个点。
Problem E
Solved by ultmaster. 00:36 (+)
题意:平面上有若干个点,每次询问一个底边在 $x$ 轴上的,高为 $l$ 的等腰直角三角形里有几个点。
题解:因为 $l$ 不变,记录每个点要被包含的最左位置和最右位置,然后扫描线就好了。
Problem F
Solved by zerol & kblack. 03:29 (+2)
题意:给两个长度为 n 的数列,通过不超过 2n 次区间修改成该区间的最大值/最小值的操作,使它们相同。
题解:a 能修改为 b 的充要条件是 b 相同相邻数字压缩后是 a 的子序列。把那个 a 中的子序列向左右扩张(一个一个把旁边不是子序列的值吃掉),然后修复边界。每个数字都有目标边界和不把不该吃掉的吃掉的边界,从能吃的开始吃,吃完了后会扩张两边的可行边界,用一个 set 维护一下,最后肯定能吃完。
Problem G
Solved by kblack. 01:21 (+)
题意:一种很奇怪的方格价值计算,修改是翻转某行或列。
题解:发现每有一个对齐的二的幂次边长的同色方格价值减少 $4$,而大方格同色等价于行的翻转状态相同且列的翻转状态相同,弄个类似线段树的东西统计一下乘乘加加。
Problem I
Solved by kblack. 00:47 (+1)
题意:对于一个排列,对所有的逆序对连边,求最大独立支配集。
题解:等价于计数极大上升子序列,从边求排列可以用树状数组,求极大上升子序列可以用单调栈,当然这题数据范围小得一批怎么玩都行。