Contest Info

date: 2019.03.20 15:40-20:40

practice link

Solutions

A. Balanced Diet

题目大意：有 \(m\) 种糖果，一个人按一定的顺序吃糖。我们记 \(s_{i}\) 表示吃第 \(i\) 种糖的数量，\(f_{i}\) 是一个给定的常数。对于每个 \(n\)，他吃第 \(n\) 颗糖时要对于每个 \(i\) 满足 \(nf_{i}-1<s_{i}<nf_{i}+1\)。现在告诉你他吃前 \(k\) 颗糖的顺序，对于 \(f_{i}\) 则这样给出：给你一个长度为 \(m\) 的正整数数列 \(a_{i}\)，\(\displaystyle{f_{i}:=\frac{a_{i}}{\sum_{j=1}^{m}a_{j}}}\)。问你这个人最多还能吃多少颗糖。

题解：注意到题目中的不等式等价于 \(\lfloor nf_{i}\rfloor\le s_{i}\le\lceil nf_{i}\rceil\)。因而 \(n=\sum_{j=1}^{m}a_{j}\) 时，每颗糖吃的数量是固定的，如果他能吃到 \(n\) 的倍数颗，那么他就可以永远吃下去。如果 \(k>n\) 但是不是 \(n\) 的倍数，他也不一定能吃到 \(n\) 的倍数颗，因此我们要把 \(k\bmod n\) 后再做计算，这是一个坑点。

我们考虑吃第 \(k+1\sim n\) 颗糖果时的情况。显然我们知道每种糖果要吃多少颗，并且我们能知道第 \(i\) 颗第 \(j\) 种糖能够被吃的 \(n\) 的取值范围：下界是我能够开始吃的时间，即 \(\lceil nf_{j}\rceil\ge i\) 的最小的 \(n\)；上界是第 \(i-1\) 颗第 \(j\) 种糖必须要被吃的时间 \(+1\)，即 \(\lfloor nf_{j}\rfloor\ge i\) 的最小的 \(n\)。这样以后我们就转成了有若干个区间，每个区间要填一个数，使得填的数成为一个排列。这就成了一个经典的贪心。

B. Branch Assignment

题目大意：给出一个 \(n\)（\(2\le n\le 5000\)）个点，\(m\)（\(1\le m\le 50000\)）条边的有向图，保证任意两点可达。给出 \(b\)（\(1\le b \le n-1\)）和 \(s\)（\(1\le s\le b\)），将 \(1,\cdots,b\) 分成 \(s\) 个非空的集合 \(S_1,\cdots,S_s\) 。设集合 \(S\) 的代价为 \(F(S)=\sum_{i,j\in S,i\neq j} \text{dis}_i(b+1)+\text{dis}_{b+1}(j)\)，最小化总代价。

题解：先做两次最短路，求出 \(\text{dis}_i(b+1)\) 和 \(\text{dis}_{b+1}(i)\)。设\(a_i=\text{dis}_i(b+1)+\text{dis}_{b+1}(i)\)，即将 \(a_1,\cdots,a_b\) 分成 \(s\) 个非空的集合 \(S_1,\cdots,S_s\) ，集合 \(S\) 的代价为 \(F(S)=(|S|-1)\times \sum_{x\in S} x\)。

显然，将 \(a\) 从小到大排序，显然最优解是分成 \(s\) 个长度不增的连续区间。令 \(s_i=\sum_{j\le i} a_j\)，\(\text{dp}[k][i]\) 表示前缀 \(i\) 分成 \(k\) 个区间的最小值，则 \(\text{dp}[k][i]=\min \big(\text{dp}[k - 1][j] + (i - j - 1)\cdot(s_i - s_j)\big)\) 。这个看起来就非常地有决策单调性，直接分治就做完了。

或者，我们可以发现区间长度递减的性质，我们枚举 \(j\) 的时候只需要枚举到 \(i-j\le \frac{i}{k}\) 即可，时间复杂度 \(\mathcal{O}(m\log{n}+bs\log{b})\)。

C. Ceiling Function

二叉树 hash，直接用 map<pair> 即可。

D. Clock Breaking

模拟题.

E. Forever Young

签到题。

G. Oil

题目大意：有若干条平行于 \(x\) 轴的线段，它们两两严格不相交。现在要你画一条不与 \(x\) 轴平行的直线，使得跟它相交的线段总长度最大。

题解：我们可以平移最优解的直线，使得它跟一条线段的端点相交，然后枚举每个点极角排序扫描线即可。

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

K. String Theory

题目大意：定义一系列引用句的文法，一级引用是一对单引号中间有任意个非单引号字符；\(i\ge2\) 级引用是 \(i\) 个单引号后跟大于等于一个 \(i-1\) 级引用，再跟 \(i\) 个单引号，其中 \(i\) 个单引号和 \(i-1\) 级引用之间、\(i-1\) 级引用和 \(i-1\) 级引用之间都可以有任意个非单引号字符。现在告诉了你每段连续的单引号数量，问你最大是多少级引用。

题解：我们枚举引用的级数。

设 dp[i][j][0/1] 表示枚举到第 \(i\) 个单引号，当前最右边未关闭的引用是 \(j\) 级，第 \(j\) 级引用后到第 \(i\) 个位置中是否已经有一级引用（因为 \(i\) 级引用中必须要有 \(i-1\) 级引用）的状态是否存在。转移时考虑关闭第 \(j\) 级引用或新填充第 \(j-1\) 级引用。