2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/16 17:40]
admin 创建
+++ 2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/17 22:26] (当前版本)
prime21 [pmxm]
@@ 行 1: / 行 1: @@
 ===== 团队 =====
+.07.12 [[2020-nowcoder-multi-1|2020牛客暑期多校训练营（第一场）]] ''pro: 4/10/10'' ''rk: 42/1116'' **DONE**
+.07.13 [[2020-nowcoder-multi-2|2020牛客暑期多校训练营（第二场）]] ''pro: 8/11/11'' ''rk: 17/1158'' **DONE**
+.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)$。

2020-2021/teams/intrepidsword/2020.07.10-2020.07.16_周报.1594892427.txt.gz · 最后更改: 2020/07/16 17:40 由 admin