2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/17 16:57] chielo [jsh] |
2020-2021:teams:intrepidsword:2020.07.10-2020.07.16_周报 [2020/07/17 22:26] (当前版本) prime21 [pmxm] |
||
|---|---|---|---|
| 行 26: | 行 26: | ||
| ==== pmxm ==== | ==== pmxm ==== | ||
| + | 本周个人训练: | ||
| + | codeforces 2600难度的题目10道 | ||
| + | TCO 2015 round 1A/1B | ||
| + | 组队训练： | ||
| + | |||
| + | 个人问题: | ||
| + | |||
| + | 能用简单平衡树搞定的问题写了权值线段树，有点得不偿失 | ||
| + | 完美匹配建模问题需要补 | ||
| + | |||
| + | 组队问题： | ||
| + | 团队中期题dirty，团队中期题进度有点慢 | ||
| ==== jsh ==== | ==== jsh ==== | ||
| 行 41: | 行 53: | ||
| ==== pmxm ==== | ==== 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 ==== | ==== jsh ==== | ||
| 行 55: | 行 75: | ||
| 换一个思路，我们记 $s_i = \oplus_{j \le i}{x_j}$，相当于已知了 $s_0$ 的情况，我们再额外选取出 $n$ 个只有两个变量的和，线性无关，且代价和尽可能小。 | 换一个思路，我们记 $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_周报.1594976230.txt.gz · 最后更改: 2020/07/17 16:57 由 chielo
