Contest Info

date: 2019.02.17 09:30-14:30

practice link

Solutions

A. Always Return a Value

题目大意：给你一个包括条件语句和 return 的语言，要你分析它是必定返回值，可能返回值，还是必定不返回值。代码不超过 1.5kb。

题解：算法用 bitset 随便搞搞就行了，主要是要写个编译器很烦。我写了 \(300\) 多行 orz。

B. Cheese

题目大意：给定 \(n\) 个物品，每个物品为 \((V_i, M_i)\)。让你最多选两个物品各切一刀（选择一个 \(p\in [0, 1]\)，物品被切为 \((pV_i, pM_i)\) 和 \(((1-p)V_i, (1-p)M_i)\)。然后分成两堆，使得两堆的 \(\sum V\) 相等，且 \(\sum M\) 相等。

题解：假设每个物品为宽为 \(V_i\)，高为 \(\frac{M_i}{V_i}\) 的长方形。我们对它们按照高度排序，然后依此摆放起来，使得下边界对齐。需要将它们分成两堆，使得两堆的宽度之和相等，且面积之和相等。注意到我们可以切两刀，所以只需要找到一段连续的长为 \(\frac{\sum V}{2}\) 的区域，它的面积等于 \(\frac{\sum M}{2}\) 即可。左右边界处便是切的两刀，因为我们按照高度排序了，所以直接二分即可。

D. Cross-section

题目大意：给你平面上的一个 \(n\) 个点的简单多边形，以及一个点 \(A(x_{0},y_{0})\)。设有一条直线过 \(A\)，倾角在 \([0,\pi)\) 中均匀分布，求直线与简单多边形交线长（可能有多段）的期望。

题解：显然答案为该简单多边形在以 \(A\) 为极点的极坐标系下的面积除以 \(\pi\)。考虑三角剖分，问题转化为要计算一个过极点的三角形的面积。我们直接暴力把线段的极坐标方程求出，再暴力积分即可（感觉我数学还行）。

E. Grouping by Prefixes

题意：给定一个有\(n\le2000\)个小写字符串（每个字符串）的可重集合\(S=\{s_1,\cdots,s_n\}\)。定义字符串集合\(P=\{p_1,\cdots,p_m\}\)是\(S\)的划分，当且仅当满足下面三个条件：

• \(p_i\)不为空
• 令\(T_i\)为\(S\)中以\(p_i\)作为前缀的字符串集合，\(T_i\)不为空
• \(T_1,\cdots,T_m\)是\(S\)的一个划分

求大小为\(m\)的划分方案数。

题解：建立\(S\)的字典树，以前缀不包含其它串的结尾节点为关键点，求出虚树，即是要求选出\(m\)个没有包含关系的子树覆盖所有叶子节点的方案数。在虚树上按dfs序进行dp.令dp[i][j]为按dfs序决策到了第\(i\)个点，选了\(j\)个子树的方案数，转移有两种，一是选这个子树，转移到dp[k+1][j+1]，其中\(k\)是子树\(i\)中最大的dfs序；二是不选，这时这个子树不可以是一个叶子，转移到dp[i+1][j]。最后答案是dp[n+1][m].

I. Security Policy

题目大意：要求你给一个平面图 \(5\) 染色。

题解：可以证明一个平面图至少有一个点度不超过 \(5\)，然后就和这道题一样了。

J. Encryption

题目大意：定义 \(f(X)\) 为所有小于等于 \(X\) 且与 \(X\) 互质的数之和。给出 \(f(X)\)，求 \(X\)。

题解：设 \(X\neq1,X=p_{1}^{t_{1}}\cdots p_{s}^{t_{s}}\)，容易证明 \(f(X)=\frac{1}{2}\left(p_{1}^{2t_{1}-1}(p_{1}-1)\cdots p_{s}^{2t_{s}-1}(p_{s}-1)\right)\)。

我们先把 \(X\) 分解，如果全是小质数，那么就比较简单了，我们从 \(p_{s}\) 开始逐个计算即可。

如果有一个大质数，那么 \(p_{s}-1\) 中的较大质数可能会和 \(p_{s}\) 乘在一起，比较麻烦。考虑到 \(p_{s}\ge10^{5}\)，那么 \(p_{1}^{2t_{1}-1}(p_{1}-1)\cdots p_{s-1}^{2t_{s-1}-1}(p_{s-1}-1)(p_{s}-1)\) 不超过 \(10^{13}\)，这个范围内的数约数个数并不多，大约在 \(10^{4}\) 这个级别。我们可以直接暴力枚举 \(p_{s}-1\) 中的小质数部分，然后就能很容易地 check 了。