CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 团队 =====

2020.07.12 [[2020-nowcoder-multi-1|2020牛客暑期多校训练营（第一场）]] ''pro: 4/10/10'' ''rk: 42/1116'' **DONE**

2020.07.13 [[2020-nowcoder-multi-2|2020牛客暑期多校训练营（第二场）]] ''pro: 8/11/11'' ''rk: 17/1158'' **DONE**

2020.07.16 [[2015-beijing-regional|2015 ACM-ICPC Asia Beijing Regional Contest]] ''pro: 8/8/11'' ''rk: 3/202''

===== 个人 =====

==== zzh ====

本周无个人训练。

=== 专题 ===

无

=== 比赛 ===

无

=== 题目 ===

无

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

组队训练：

个人问题:

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

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

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

===== 本周推荐 =====

==== zzh ====

[[2015-beijing-regional#k_a_math_problem|2015 ACM-ICPC Asia Beijing Regional Contest K]]

一道比较有趣的数学题。

==== pmxm ====

一道赛中瞎想出来的题
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
$$
==== jsh ====


[[https://acm.sjtu.edu.cn/OnlineJudge/problem/4167|上交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)$。
CVBB ACM Team

用户工具

站点工具

页面工具
