2018-2019 Southeastern European Regional Programming Contest (SEERC 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 (+)

Problem E

Solved by ultmaster. 00:36 (+)

题意：平面上有若干个点，每次询问一个底边在 $x$ 轴上的，高为 $l$ 的等腰直角三角形里有几个点。

题解：因为 $l$ 不变，记录每个点要被包含的最左位置和最右位置，然后扫描线就好了。

Problem F

Solved by zerol & kblack. 03:29 (+2)

Problem G

Solved by kblack. 01:21 (+)

题意：一种很奇怪的方格价值计算，修改是翻转某行或列。

题解：发现每有一个对齐的二的幂次边长的同色方格价值减少 $4$，而大方格同色等价于行的翻转状态相同且列的翻转状态相同，弄个类似线段树的东西统计一下乘乘加加。

Problem I

Solved by kblack. 00:47 (+1)

题意：对于一个排列，对所有的逆序对连边，求最大独立支配集。

题解：等价于计数极大上升子序列，从边求排列可以用树状数组，求极大上升子序列可以用单调栈，当然这题数据范围小得一批怎么玩都行。