CVBB ACM Team

2020.07.12 2020牛客暑期多校训练营（第一场） pro: 4/10/10 rk: 42/1116 DONE

2020.07.13 2020牛客暑期多校训练营（第二场） pro: 8/11/11 rk: 17/1158 DONE

2020.07.16 2015 ACM-ICPC Asia Beijing Regional Contest pro: 8/8/11 rk: 3/202

本周无个人训练。

无

无

无

本周个人训练: codeforces 2600难度的题目10道 TCO 2015 round 1A/1B

组队训练：

个人问题:

能用简单平衡树搞定的问题写了权值线段树，有点得不偿失 完美匹配建模问题需要补

组队问题： 团队中期题dirty，团队中期题进度有点慢

本周无个人训练。（摸了）

2015 ACM-ICPC Asia Beijing Regional Contest K

一道比较有趣的数学题。

一道赛中瞎想出来的题 The 2015 ACM-ICPC Asia Beijing Regional Contest E - Stamps

转移非常简单,$dp_{k+1,n}$表示(n,k)状态对应的答案

$$ dp_{i,j} = dp_{i,j-1} + dp[i-1][j]/j $$

上交OJ - 4167. 猜小球

题意： 有 $n$ ($1 \le n \le 1,000$) 个不透明的杯子，每个杯子下最多有一个小球，你可以花费 $W_{l, r}$ 的代价来获得标号在 $[l, r]$ 之间，小球数量的奇偶性。问获得所有杯子下小球情况的最小代价和。

题解：

一个比较直接的做法是将杯子下小球的情况抽象成变量 $x_i$，需要选取出 $n$ 个线性无关的变量区间和，让所需的代价尽可能小。这样做需要高斯消元，时间复杂度 $\mathcal{O}(n^3)$，不太行。

换一个思路，我们记 $s_i = \oplus_{j \le i}{x_j}$，相当于已知了 $s_0$ 的情况，我们再额外选取出 $n$ 个只有两个变量的和，线性无关，且代价和尽可能小。

考虑一下消元的过程，会发现我们首先已经有了 $s_0$，如果使用 $s_0$ 去消 $s_0 + s_i$，相当于我们花费了 $W_{1,i}$ 的代价，利用已知的 $s_0$ 来获得 $s_i$ 的值。将变量考虑成点，方程考虑成边，代价考虑成边权，目标实际上是想要花费最少的代价让这个图连通。

因此我们可以用最小生成树来做这个题，Prim 算法的过程也相当于消元的过程。时间复杂度 $\mathcal{O}(n^2)$。