The red figure is the Minkowski sum of blue and green figures. ©Wikipedia概念 闵可夫斯基和是两个欧几里得空间的点集的和，以德国数学家闵可夫斯基命名。我们这样定义点集 $A$ 和 $B$ 的闵可夫斯基和： $$A+B=\{a+b \ | \ a \in A,b \in B \}$$ 类似地，闵可夫斯基差可以被定义为： $$A-B=\{c \ | \ c +B \subseteq A\} $$ 计算方法 考虑点集 $A + B$ 的凸包上的每一个点 $c = a + b$，那么 $a$ 一定位于 $A$…
Description 可怜有一个长度为 $n$ 的正整数序列 $A$，但是她觉得 $A$ 中的数字太小了，这让她很不开心。 于是她选择了 $m$ 个区间 $[l_i, r_i]$ 和两个正整数 $a, k$。她打算从这 $m$ 个区间里选出恰好 $k$ 个区间，并对每个区间执行一次区间加 $a$ 的操作。（每个区间最多只能选择一次。） 对区间 $[l, r]$ 进行一次加 $a$ 操作可以定义为对于所有 $i ∈ [l, r]$，将 $A_i$ 变成 $A_i + k$。现在可怜想要知道怎么选择区间才能让操作后的序列的最小值尽可能的大，即最大化 $\min A_i$。 Idea…
Description 有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,…,p_n$，你会对它进行若干轮操作，每一轮操作，你会保留序列中极大的数，也就是说对于每个数字，如果它比相邻的数字都大，那么会被保留下来。比如一个排列 $(3,2,5,1,4,6)$，经过一轮操作之后序列变成 $(3,5,6)$，第二轮操作之后序列变成 $(6)$，经过恰好 $2$ 轮之后序列里只有一个元素。 请问有多少个长度为 $n$ 的序列，经过恰好 $k$ 次操作之后，序列里只有一个元素，由于答案很大，对一个素数 $P$ 取模。 Idea ⾸先考虑给定⼀个排列，…
你还相信圣诞老人吗？…
Description 众所周知，圣诞树是一棵 $n$ 个节点的树。 这意味着它将包含很多割点，这导致了结构不稳定。你需要为它添加一些边，使得割点不存在。 给出你的加边方案。 Idea 我们可以先考虑如果是割边的话应该怎么做。显然答案下界是 $\lceil \dfrac{l}{2} \rceil$ ，其中 $l$ 是叶节点个数 我们可以构造出这样的⽅案：令叶节点的权值为 1 ，⾮叶节点的权值为 0 ，求整棵树的带权重⼼ $c$。由于重⼼的每个⼉⼦的⼦树⾥都只有不超过 $\lfloor \dfrac{c}{2} \rfloor$ 个叶⼦，我们不难构造出⼀组⽅案使得每条边连接的两个叶⼦都来⾃于重⼼的不同⼉⼦的⼦树。 考虑割点。显然答案下界是…
Description [https://www.luogu.org/problemnew/show/P4705] Alice 和 Bob 又在玩游戏。 对于一次游戏，首先 Alice 获得一个长度为 $n$ 的序列 $a$，Bob 获得一个长度为 $m$ 的序列 $b$。之后他们各从自己的序列里随机取出一个数，分别设为 $a_x, b_y$，定义这次游戏的 $k$ 次价值为 $(a_x + b_y)^k$。 由于他们发现这个游戏实在是太无聊了，所以想让你帮忙计算对于 $i = 1, 2, \cdots, t$，一次游戏 $i$ 次价值的期望是多少。 由于答案可能很大，只需要求出模…
题目描述
红包举办了一场才艺大赛，有 n 个人参加。每个人表演需要 p 分钟，最后评审需要 v 分钟才能评选出第一名。
然而这样一共就需要 pn + v 分钟。红包觉得太慢了，于是决定通过分轮加快速度。 每轮把剩下的人分成一些组，然后同时进行比赛，然后留下第一名。
等这一轮的全部比完，就进行下一轮。 直到只剩下一个人为止。
求最少需要多少时间。 可以认为评委个数以及场地数无限。
思路
枚举进行的轮数 $k$。对于每个 $k$，最初一定分成了 $\sqrt[k]{n}$ 组。直接向下取整计算即可， 不足 $n$ 个人就逐个补齐。
代码
#include
> Original article: Listen to Sam Smith’s Haunting Ballad ‘Fire on Fire’ From Netflix ‘Watership Down’ Adaptation , by Gil Kaufman [https://www.billboard.com/author/gil-kaufman-6882925] from billboard [https://www.billboard.com/articles/columns/pop/8491217/sam-smith-fire-on-fire-watership-down-netflix-listen] Sam Smith [https://www.billboard.com/music/sam-smith]just added something very important…