2020牛客暑期多校训练营（第二场）解题报告 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

B.Boundary

题目描述

Given ${n}$ points in 2D plane. Considering all circles that the origin point ${(0, 0)}$ is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

C.Cover the Tree

题目描述

Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.

题目分析

• 若本结点有奇数个子结点，随便留下一个子结点所对应的叶子结点向上传递，剩下的结点两两匹配
• 若本结点有偶数个子结点，随便留下两个子结点所对应的叶子结点向上传递，剩下的结点两两匹配

D.Duration

题目描述

Given two moments on the same day in the form of HH:MM:SS, print the number of seconds between the two moments.

F.Fake Maxpooling

题目描述

Given a matrix of size $n\times m$ and an integer ${k}$, where $A_{i,j} = lcm(i, j)$, the least common multiple of ${i}$ and ${j}$. You should determine the sum of the maximums among all $k\times k$ submatrices.

I.Interval

题目描述

There is an interval ${[1, n]}$ initially. For an interval ${[l, r]}$, if ${l < r}$, there will be two possible changes:

• Shrinking, ${[l, r]}$ changes to ${[l + 1, r]}$ or ${[l, r - 1]}$
• Expanding, ${[l, r]}$ changes to ${[l - 1, r]~(l > 1)}$ or ${[l, r + 1]~(r < n)}$

So, when ${l = r}$, the interval will be unable to be changed. You don’t want to see this, so you may need to ban some changing manners.
Specifically, we use tuple ${(l, r, dir, c)}$ to describe banning. If ${dir = L}$, you can ban the bidirectional changing between ${[l, r]}$ and ${[l + 1, r]}$ with cost ${c}$ while you can ban the bidirectional changing between ${[l, r]}$ and ${[l, r - 1]}$ with cost ${c}$ if ${dir = R}$.
Determine the minimum total cost to guarantee that ${l = r}$ will never happen. Print “-1” if it’s impossible to make it.

J.Just Shuffle

题目描述

Given a permutation with size ${n}$ and an integer ${k}$, you should find a permutation substitution ${P}$ that $\{1, 2, \cdots, n\}$ will become ${A}$ after performing substitution ${P}$ for exactly ${k}$ times. Print the permutation after performing ${P}$ for once on $\{1, 2, \cdots, n\}$. If there are multiple solutions, print any of them. If there is no solution, print “-1” in one line.

题目分析

$k$是质数，不可能有无解情况。