2020-2021:teams:die_java:weeksummary9

差别

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

到此差别页面的链接

--- 2020-2021:teams:die_java:weeksummary9 [2020/08/07 16:46]
mychael
+++ 2020-2021:teams:die_java:weeksummary9 [2020/08/07 17:55] (当前版本)
fyhssgss [每周推荐]
@@ 行 14: / 行 14: @@
 ====== 每周推荐 ======
-fyh:
+fyh:2020-2021 BUAA ICPC Team Supplementary Training 02 H.Split Game
-\\ 题目大意：
+\\ 题目大意：给一个多边形，全在第一象限，有一条过原点的直线，问最多能把这个多边形划分成多少区域
-\\ tag:
+\\ tag:计算几何
-\\ 做法:
+\\ 做法:先考虑给定一条分界线怎么数区域，我的做法是先算出所有交点然后看这条线两侧有多少个山峰，便是多少个区域，我们便可以从这个思路继续拓展，继续想直线在旋转的过程中答案的增量，十分善良的是数据已经是按照逆时针转好的，注意讨论这个点前驱后继组成的形状。
-\\ comment:
+\\ comment:计算几何的细节处理
-wxg:
+wxg: 2020-2021 BUAA ICPC Team Supplementary Training 02 E.line game
-\\ 题目大意：
+\\ 题目大意：有 $n$ 条线段,端点为 $(0,i) ,(1,p_i)$ 每次可以花 $v_i$ 的价值选线段 $i$ ,把 $i$ 和 与 $i$ 相交的线段全部删了, 问删完所有线段的最小代价.
-\\ tag:
+\\ tag: dp，cdq分治，单调栈
-\\ 做法:
+\\ 做法: 具体见周报
-\\ comment:
+\\ comment: 非常巧妙的dp题，用到各种dp的优化方法
-hxm:
+hxm:2020-2021 BUAA ICPC Team Supplementary Training 02 D.Forest Game
-\\ 题目大意：
+\\ 题目大意：现在有一棵$n$个节点的树，每次从中删去一个点，得到这个点所在树的大小的代价。问给定一棵树随机删除的所有情况代价和
-\\ tag:
+\\ tag:计数，点分治，fft
 \\ 做法:
-\\ comment:
+每一种删除方案对应一种排列
+我们考虑每个点对的贡献，每个点对中一个点对另一个点产生贡献当且仅当另一个点是这两点之间所有点中第一个删除的，那么距离为$m-1$的点对(即路径上有$m$个点)产生的代价为$2 \times C_{n}^{m}(m-1)!(n-m)!$
+那么我们只需要计算每种距离的点对有几个
+使用点分治+$fft$统计
+\\ comment:点分治+$fft$统计不同长度点对个数
 ----
@@ 行 37: / 行 41: @@
 ====== 傅云濠 ======
+补题选拔赛第十场的H和F
+\\ 学习了笛卡尔树
 ----
 ====== 王兴罡 ======
+比赛：[[https://atcoder.jp/contests/abc174|atcoderAtCoder Beginner Contest 174]]
 ----
 ====== 黄旭民 ======
+比赛：[[https://atcoder.jp/contests/abc174|atcoderAtCoder Beginner Contest 174]]
+ \\ 整理：整理了点分治板子

2020-2021/teams/die_java/weeksummary9.1596790004.txt.gz · 最后更改: 2020/08/07 16:46 由 mychael