NWERC 2017

Contest Info

date: 2019.04.27 14:33-19:33

practice link

Solutions

A. Ascending Photo

题目大意:给定一个数组 \(h_1,h_2,\dots, h_n\),让你把它分成若干连续段,使得将这些段重排之后,序列单调不降。求最少的段。

题解:显然 \(h_i>h_{i+1}\)\(i\) 后面一定要被断开。那么我们现在已经得到了一些初始的段,段内重复的元素显然也可以合并。现在我们考虑这些段怎么 merge 成为一个单调不降的序列。

每次我们找到所有段头的最小值 \(x\)\(x\) 在每个段的出现后面都应该被切一刀(如果它不是段的最后一个元素)。设下一次的最小值为 \(y\),并且存在一段的 \(y\) 是通过切掉 \(x\) 被暴露出来的,那么这一刀可以被黏回去。

但是这样会出现问题:

  • 假设初始的两段分别为 2 3 43,那么我们把第一段的 2 3 间的一刀黏回去了,并且 3 4 间的一刀也黏回去了,这样显然不合法。

fix 的方法,我们记录一下上一轮可以黏回去的段有几个,如果大于 \(1\) 个,那么这一轮就随便黏;如果只有一个,那么这一轮的该段就不能黏。(这里的正确性可以用类似增广路的思想,可以从一个不合法的位置从后往前推导)。

但还是会有问题:

  • 假设初始的两段为 2 3 4 5 63,那么 2 3 可以黏,3 4 不可以黏,4 5 可以黏。到现在都没问题,但是 5 6 不能黏,这里出现了错误。

fix 的方法,我们把连续的一段(离散化之后连续)仅在该段出现(出现次数为 \(1\))的数字合并成一个即可,idea 就是同时做这一组。那么上述两段合并后为 2 3 43

时间复杂度 \(\mathcal{O}(n\log n)\)

B. Boss Battle

签到题。

C. Connect the Dots

题目大意:给你一些平面上的带标号整点,要求你用段数尽可能少的一条折线段将它们按顺序连起来(类似于解锁手机屏幕),求最小段数。

题解:贪心。记 \(f_{i}\) 表示到第 \(i\) 个点时最少的段数,\(S_{i}\) 表示达到最小段数可能的入射角集合。

转移时,假如 \(p_{i+1}-p_{i}\in S_{i}\),那么一定会选择这种方案(后面证明),即 \(f_{i+1}=f_{i},S_{i+1}={p_{i+1}-p_{i}}\);否则的话,线段可以先沿着原方向走任意长的一段距离,然后再拐弯到 \(p_{i+1}\),即 \(f_{i+1}=f_{i}+1\)\(S_{i+1}\) 是一个区间,区间具体的范围需要一定的讨论,这里就不展开说了。

上面的证明也比较简单,因为第一种情况少了一段,所以它可以在 \(p_{i+1}\) 处旋转任意的角度(开始新的一段),可以认为这和第二种情况中 \(S_{i+1}=[0,2\pi)\) 是等价的。因此第一种情况必然更优。

D. Dunglish

签到题。

E. English Restaurant

题目大意:有一个餐馆,里面有 \(n\) 张桌子,每张桌子有 \(c_{i}\) 个位置。有 \(t\) 波客人来吃饭,每波客人的数量是 \(1\sim g\) 中的整数的等概率随机。一波客人来时,他们会选择最小的位置数不少于人数的空闲桌子,然后占据这张桌子。如果没有这样的桌子,这波客人会离开。求最后店里期望的人数。

题解:这题有一个重要的性质,占用哪些桌子只取决于客人的数量,而不取决于同样数量下客人来的顺序。证明的话考虑交换相邻两波客人的情况即可。

我们首先补上 \(t\) 张有 \(g\) 个位置的桌子,这样所有人就都有位置坐了,只需要在计算时把多余桌子的期望设为 \(0\) 即可。然后对桌子排序。对于位置数相同的桌子,我们认为排在前面的桌子更小,即对于某种数量的桌子,我们一定会坐一个前缀。

\(dp[i][j]\) 表示来了 \(j-i+1\) 波客人时,他们恰好占据了第 \(i\sim j\) 张桌子的概率。转移时枚举最后一波客人占据的桌子 \(k\),那么有 \(dp[i][j]+=dp[i][k-1]\cdot dp[k+1][j]\cdot{j-i\choose k-i}\cdot\text{prob}\),其中 \(\text{prob}\) 表示最后一波客人占据 \(k\) 的概率。这里还需要证明左(\(i\sim k-1\))右(\(k+1\sim j\))两侧选择桌子是互不干扰的,这个是比较显然的。

然后我们考虑占用了若干不相邻区间的情况。设 \(dp1[i][j]\) 表示前 \(i\) 张桌子中,占用了 \(j\) 张桌子,且桌子 \(i\) 被占用的概率。转移时枚举最右边一段区间的长度,上一段区间的右端点,以及除最后一段区间外桌子占用的数量即可。写出式子会发现能够合并同类项,从而将复杂度优化到 \(\mathcal{O}(n^{3})\)。最后答案即为 \(\sum_{i=1}^{n+t}dp1[i][t]\)

前面所有 \(dp\) 当然还要针对期望进行计算,不过原理几乎是一样的。

时间复杂度 \(\mathcal{O}(n^{3})\)

F. Factor-Free Tree

题目大意:定义 FFT 为一棵二叉树,且每个节点有一个正整数权值,满足任意一个点 \(u\) 和它的任意一个祖先 \(v\) 的权值互质。给出长度为 \(n(1\le n\le 10^6)\) 的数列 \(a_1,a_2,\dots, a_n(1\le a_i\le10^7)\) 表示一棵 FFT 的中序遍历,让你构造任意一棵合法的 FFT 或者判断无解。

题解

solution 1

FFT 的约束等价于每个节点和其子树中其他节点互质,而中序遍历一棵子树对应一个区间。

预处理 \(10^7\) 以内的质数和每个数的最小质因子,可以求出每个位置 \(i\) 向左右延伸的极大互质区间,复杂度为 \(\mathcal{O}(A+n\log A)\)。考虑按中序遍历的顺序(依次枚举 \(a_i\))增量构造合法的 FFT,类似笛卡尔树维护一条右链。

假设当前枚举到 \(i\),满足 \(R[i] > R[\text{top}]\)\(R[\text{top}]\) 表示右链的 \(\min R\),后面会说到栈顶的 \(R\) 就是 \(\min R\))。我们希望让 \(R\) 大的深度尽可能小,于是一直出栈,满足出栈元素对应的子树中的 \(\min j \ge L[i]\),直到不能出栈。此时将 \(i\) 入栈,因为父亲确定,所以它超过父亲的 \(R\) 是无用的,将 \(R\) 与父亲取 \(\min\) 即可。

入栈的时候要检查一下父亲是否能包含 \(i\),不能包含则无解。构造部分的时间复杂度为 \(\mathcal{O}(n)\)。总时间复杂度为 \(\mathcal{O}(A+n\log A)\)

solution 2

位置 \(i\) 可以作为区间 \([L,R]\) 的根的必要条件是 \(i\) 与区间内其他位置都互质。对于区间 \([L,R]\),如果只有一个这样的位置,那么显然就选择这个位置;否则假设有两个以上的位置,我们说明选任意一个都不影响最终的可行性。

假设 \(u,v\)仅有的两个不同的合法位置,那么 \(u\)\(v\) 将区间切成三段。假设这三段分别有解,那么 \(u,v\) 选择哪一个都不影响,若选择 \(u\) 为根,那么可以让 \(v\) 直接连上 \(u\)。假设三段中存在无解,则必然导致无解,否则矛盾(只能在 \(u,v\) 断开)。如果不止 \(u,v\) 两个合法位置证明同理。

因此,我们可以从 \([1,n]\) 开始选择一个合法的位置作为根,然后递归处理左右。在处理 \([L, R]\) 时,可以从两个端点开始一起向中间枚举,这样最终的时间复杂度是 \(\mathcal{O}(n\log{n})\) 的,可以考虑最终的分治树,每一层的复杂度是 \(\mathcal{O}(\min(\text{size}[\text{lch}],\text{size}[\text{rch}]))\),因此本质上是个启发式合并的逆过程。

加上预处理互质区间的部分,总的时间复杂度为 \(\mathcal{O}(A+n(\log{A}+\log{n}))\)

G. Glyph Recognition

题目大意:给出平面上 \(n(1\le n\le 1000)\) 个整点。对于正 \(k(3\le k\le 8)\) 边形,将其中心放在原点,其中一个顶点放在 \(x\) 正半轴,定义其顶点到原点的半径为 \(R_k\),求一个最大的 \(R_{k1}\) 使得这 \(n\) 个点都不在其内部,求一个最小的 \(R_{k2}\) 使得这 \(n\) 个点都在其内部,则 \(\displaystyle \text{score}_k=\frac{R_{k1}^2}{R_{k2}^2}\)。输出 \(\text{arg_max}(\text{score}_k)\)\(\max(\text{score}_k)\)

题解:对于每个点,求出其刚好落在边界上的 \(R\),然后取最小值为 \(R_1\),取最大值为 \(R_2\)。计算 \(R\) 的时候,可以利用 fmod 将其旋转到正多边形以原点为中心的三角剖分的第一块区域,然后解一下三角形即可。时间复杂度 \(\mathcal{O}(nk)\)

用二分解三角形也可以,但是精度比较差,Claris 用二分过了,但是我反正是 wa 54。

H. High Score

题目大意:给出 \(a,b,c,d\ge0\),要你把 \(d\) 分配给 \(a,b,c\),使得 \(a^{2}+b^{2}+c^{2}+7\min\{a,b,c\}\) 最大,求这个最大值。

题解:枚举最小值,把 \(a,b,c\) 都提升到最小值后,显然剩余的 \(d\) 全分给最大值最优,那么最终答案是一个关于最小值的(分三段的)二次函数,分别求最值即可。

题解说每段暴力算最小的几个值就好了。。不是很懂

I. Installing Apps

题目大意:有 \(n(1\le n\le 500)\) 个手机 App 需要安装,手机上只有 \(c(1\le c\le 10000)\) 的空间。每个 App 需要 \(d_i\) 的空间下载,安装好之后需要 \(s_i\) 的空间(安装的过程不需要额外的空间,可以视为从 \(d_i\) 直接变为 \(s_i\))。问你按什么样的顺序安装 App 可以安装最多的 App。

题解:让 \(d_i=\max(d_i, s_i)\),那么每个 App 安装的时候需要 \(d_i\) 的空间,装好之后需要 \(s_i\) 的空间。这个题看起来就像是:按某种最优策略排序,然后 dp。我们按照 \(d_i-s_i\) 从大到小排序,然后 \(\text{dp}[i][j]\) 表示前 \(i\) 个 App 我们安装 \(j\) 个,还能剩下的最大的空间。复杂度 \(\mathcal{O}(n^2)\)

下面证明按照 \(d_i-s_i\) 降序排序的正确性,我们假设集合 \(S\) 中的每个 App 都要安装,在这个前提下证明:

Proof 1:

考虑合法的安装顺序中两个相邻的 App \((d_a,s_a)\)\((d_b,s_b)\),并且 \(d_a-s_a\le d_b-s_b\)。我们证明交换两个 App 不会更差(也是合法安装顺序)。假设安装 \(a\) 之前有 \(X\) 的空间,因为之前的安装顺序是合法的,所以 \(d_a\le X\)\(s_a+d_b\le X\)。交换之后,我们只需要证明 \(d_b\le X\)\(s_b+d_a\le X\)

因为 \(s_a>0\) 所以第一个显然。对于第二个,有 \(d_a-s_a\le d_b-s_b\) 推出 \(s_b+d_a\le s_a+d_b\le X\),也成立。\(\Box\)

Proof 2

考虑一个很经典的贪心。你有若干个作业的 DDL 时间 \(d_i\) 和完成每个作业需要的时间 \(s_i\),那么如果要做完每个 DDL,你一定是按照 \(d_i\) 升序来做这些作业。

同理,在这道题中,我们让 DDL 时间为 \(c-(d_i-s_i)\),完成时间为 \(s_i\)\(\Box\)

J. Juggling Troupe

题目大意:序列 \(s_1,s_2,\dots,s_n\)\(s_i\in \{0, 1, 2\}\)。如果某个位置的值 \(x\ge 2\),那么下一秒它会给左右相邻位置各一个 \(1\),如果相邻位置是边界,那么那个 \(1\) 就扔掉。当没有位置 \(\ge 2\) 的时候停止,问最终状态的序列。

题解:可以发现每个 \(2\) 是独立的,我们考虑一个 \(2\) 对终态的影响。假设位置 \(i\) 有一个 \(2\),那么我们找到左边第一个 \(0\) (一开始在边界位置补 \(0\))的位置 \(L\),右边第一个 \(0\) 的位置 \(R\)。那么我们会把位置 \(L,R\)\(1\),然后把位置 \(L+R-i\)\(0\)(稍微画一下就可以发现),如果没被置 \(0\) 那么位置 \(i\) 也是 \(1\)

那么我们只需要一开始把所有的 \(0\) 放进一个 set,然后从左往右依次枚举输入序列中的每个 \(2\) 即可。注意如果 \(L+R-i\) 的位置是 \(2\) 也没关系,我们往 set 中放入 \(L+R-i\),但是仍然要枚举这一个位置的 \(2\)

K. Knockout Tournament

题目大意:定义 \(n(2\le n\le 4096)\) 个人的淘汰赛为,第一轮 \(k\) 人轮空,剩余 \(n-k\) 人两两一组进行一场淘汰,第一轮结束后剩下的人数恰好是 \(2\) 的幂次。之后每一轮两两一组进行淘汰直到只剩下一个人。每个人有一个能力值 \(a_i\),若 \(i\)\(j\) 比赛,则 \(i\) 获胜的概率为 \(\displaystyle \frac{a_i}{a_i+a_j}\)。让你在比赛开始前,任意安排好整个赛程,使得 \(1\) 号获胜的概率最大,求这个最大概率。

题解:首先令 \(m\) 为不大于 \(n\) 的最大的 \(2\) 的幂次,则 \(k=2m-n\)。将除了 \(1\) 号之外的人按 \(a_i\) 排序,将第一轮轮空的位置都放在左边,第一个人站第一个位置,剩下的人按 \(a_i\) 升序从左到右站,则第一个人获胜的概率最大。

考虑用一个子树递推来计算这个概率,每个节点需要分别枚举左右子树中获胜的人来计算答案,时间复杂度 \(\mathcal{O}(n^2)\)(每一对人只会在 lca 被计算)。 用 std::unordered_map 来存储答案则空间复杂度为 \(\mathcal{O}(n\log{n})\)