Virtual Participated on May 17, 2020.

Practice & VP available here: Codeforces Gym

• solved 5 out of 12 problems
• Rank 18/262 in official records

(√ for solved during VP, ○ for after VP, - for tried but not solved)

• Solved by Pantw

给一个环形数字序列 $\{a_i\}$，定义三元组 $(i, j, k)$ 是奇怪的，当且仅当 $i<j<k$（环意义下）且 $a_i<a_j>a_k$。

定义三元组的权值为 $|j-i|+|k-j|$（同样环意义下），求权值最小的奇怪三元组。

保证输入的序列中所有数字互异。

这个题我们根据严格全序关系的性质可以知道，必定存在相邻的三个数（环意义下相邻）满足题给条件。

那么我们直接 $\Theta(n)$ 判一判即可。

• Solved by Withinlover

给定三个整数$l$，$r$，$w$。

你有一个数字，初始值为 $0$，每次可以选择增加 $r$，或者减少 $w$，但是这个数字必须在 $[0, l]$ 的范围内浮动。问经过有限次操作后，是否会得到一个接下来无法进行任何操作的数字。如果可能，输出$DEADLOCK$，否则输出 $OK$。

很容易想到可以到达的数字均为 $\gcd (r, w)$ 的整数倍。且仅当 $r + w > l$ 时可能有解。

只需要判断 $r$ 和 $l - w$ 之间是否存在一个数字是$\gcd (r, w)$ 的倍数即可

• Simplified by Pantw
• Code by Withinlover

原始题意没看太明白。

简化后的题意是构造一个完全图的欧拉回路。

先构造出从 $1\to 2\to \dots \to n\to \dots\to 1$ 的路径。

在其中的每一个节点上，都访问一次剩余所有节点并返回。从而构造出完整的欧拉回路。

• Solved by Withinlover

有 $n$ 座城市，城市间有 $m$ 条公路。

你可以向任意城市派兵来攻占城市， 对于城市 $i$，占领需要 $a_i$ 个士兵，向该城市派遣单个士兵的花费为 $b_i$。

占领第 $i$ 条公路需要至少 $c_i$ 个士兵。占领后，可以将士兵在公路两端任意移动。

士兵不会减少，在占领一座城市或桥梁后可以立即用于占领其他城市/桥梁。

询问占领所有城市的最小花费（不要求占领所有道路）

看着就很像最小生成树。

将每一个城市的答案设为 $a_i\times b_i$（直接派兵占领）

以 $c_i$ 对边权进行排序，从小到达枚举，若道路两侧属于不同的集合$u$，$v$

• $a_u = \max(c_i, \max(a_u, a_v))$
• $b_u = \min(b_u, b_v)$
• $Ans_u = \min(a_u\times b_u, Ans_u+Ans_v)$
• $fa_v = u$

• Solved by Withinlover

有 $n$ 个球，$2n$ 次操作。$+$ 表示放入一个球， $-$ 表示取出一个球，取出操作会在已经放入的球中随机挑选一个取出，给定每一次放入与取出操作的时间，问每一个小球被从放入到被取出时的时间差的期望。

面向数据做题，样例 $1$ 和样例 $2$是用来帮助理解题意的。主要看样例 $3$。

3
+ 4
+ 10
- 11
+ 16
- 20
- 100

31.5000000000
25.5000000000
44.0000000000

分别计算第二个球和第三个球的取出时间，有

$$T_2 = 11 \times\frac{1}{2}+\frac{1}{2}\times\left(20\times\frac{1}{2}+\frac{1}{2}\times (100\times 1)\right)$$

$$T_3 = 20\times\frac{1}{2}+\frac{1}{2}\times (100\times 1) $$

至于式子怎么列出来的就不说了，高中数学。直接计算的话复杂度是 $O\left(n^2\right)$的

观察两个式子，发现 $T3$ 的表达式是 $T2$ 表达式的一部分，这提示我们可以倒着算。

稍微推一推细节就可以了，记得最后减去放入袋中的时间。