ByteDance2019-Day2

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)=p_{1}^{2t_{1}-1}(p_{1}-1)\cdots p_{s}^{2t_{s}-1}(p_{s}-1)\)

我们先把 \(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 了。