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

差别

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

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/17 16:56]
chielo [jsh]
+++ 2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/17 22:26] (当前版本)
prime21 [pmxm]
@@ 行 26: / 行 26: @@
 ==== pmxm ====
+本周个人训练:
+codeforces 2600难度的题目10道
+TCO 2015 round 1A/1B
+组队训练：
+个人问题:
+能用简单平衡树搞定的问题写了权值线段树，有点得不偿失
+完美匹配建模问题需要补
+组队问题：
+团队中期题dirty，团队中期题进度有点慢
 ==== jsh ====
@@ 行 41: / 行 53: @@
 ==== 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 ====
@@ 行 47: / 行 67: @@
 **题意**：
-有 $n$ ($1 \le n \le 1,000$) 个不透明的杯子，每个杯子下最多有一个小球，你可以花费 $W_{l, r}$ 的代价来获得标号在 $[l, r]$ 之间，小球数量的奇偶性。问获得所有杯子下小球情况的最小花费。
+有 $n$ ($1 \le n \le 1,000$) 个不透明的杯子，每个杯子下最多有一个小球，你可以花费 $W_{l, r}$ 的代价来获得标号在 $[l, r]$ 之间，小球数量的奇偶性。问获得所有杯子下小球情况的最小代价和。
 **题解**：
@@ 行 55: / 行 75: @@
 换一个思路，我们记 $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$ 的值。将变量考虑成点，方程考虑成边，代价考虑成边权，目标实际上是想要让这个图连通。
+考虑一下消元的过程，会发现我们首先已经有了 $s_0$，如果使用 $s_0$ 去消 $s_0 + s_i$，相当于我们花费了 $W_{1,i}$ 的代价，利用已知的 $s_0$ 来获得 $s_i$ 的值。将变量考虑成点，方程考虑成边，代价考虑成边权，目标实际上是想要花费最少的代价让这个图连通。
-综上，我们可以用最小生成树来做这个题，Prim 算法的过程也相当于消元的过程。时间复杂度 $\mathcal{O}(n^2)$。
+因此我们可以用最小生成树来做这个题，Prim 算法的过程也相当于消元的过程。时间复杂度 $\mathcal{O}(n^2)$。

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