2020-2021:teams:die_java:weeksummary13

差别

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

到此差别页面的链接

--- 2020-2021:teams:die_java:weeksummary13 [2020/09/03 15:22]
fyhssgss 创建
+++ 2020-2021:teams:die_java:weeksummary13 [2020/09/04 17:42] (当前版本)
wxg [每周推荐]
@@ 行 11: / 行 11: @@
 ====== 每周推荐 ======
 **fyh:**
-\\ **题目大意：**
+\\ **题目大意：**$(n+1)*m$的矩形，起点在第一行的任意位置，可以选择向右走或者向下走，其中前$n$行每一行都有一段区间$a_i,b_i$，当属于这段区间的时候不能往下走，分别回答从第一行到$2到n+1$行的最短距离。
-\\ **tag:**
+\\ **tag:**数据结构，思维
-\\ **做法:**
+\\ **做法:**从$i$行到$j$行只考虑往下走一定是需要走$j-i$步，所以我们为了计算总步数，只需要令向右的步数最小即可。维护$dp_i$表示到第i列的最小向右步数，当我们在第1行的时候所有dp值全是0（因为起点任意选择），之后对于每一行不能往下走的区间$[a,b]$，$a\leq pos\leq b$,我们不能直接到pos,必须得先走到a-1然后再走到pos，所以此处的设$dp[a-1]=val，那么dp[pos]=val+pos-a+1$。之后每次答案我们只需要查询$min\{dp_i\}$即可。上述操作可以通过线段树实现，复杂度$O(nlogn)$
-\\ **comment:**
+\\ **comment:**考试时候没有调出来这种区间加值递增的线段树
 **wxg: **
-\\ **题目大意**
+\\ **题目大意** 在平面直角坐标系中 左下角是原点，边长是 $10^6$ 的正方形区域中，有 $n$ 条水平线段和 $m$ 条竖直线段，并且所有的线段至少与正方形的一侧相交，保证在同一条直线上没有两条线段，问这些线段把这个大正方形分成了多少块。
-\\ **tag: **
+\\ **tag: **  数状数组
-\\ **做法:**
+\\ **做法:**  发现有两种情况会让正方形个数增加，1.水平线和竖直线相交会增加一块。2.一条线段的两端都与大正方形相交会增加一块。对于 1 我们可以用数状数组维护每一个 y 轴上的点有多少条水平直线，对于每个竖线统计个数。
-\\ **comment: **
+\\ **comment: **  增加块数的条件是思考点。
 **hxm:**
-\\ **题目大意：**
+\\ **题目大意：**   判断两个圆角矩形相交
-\\ **tag:**
+\\ **tag:**   计算几何
-\\ **做法:**
+\\ **做法:** 拆分成四个圆和两个矩形，分别判断
+圆和圆就比圆心距
+矩形和矩形：判断一个矩形的顶点是否在另一个矩形内部。通过叉积的方式
+圆和矩形：先判断圆心是否在矩形内，否则只可能是圆与某一条边相交，先判圆心到直线距离，然后再看看两端点在异侧还是同侧
+如果在异侧，那么就相交
+如果在同侧，那么只有当端点存在于圆内相交
-\\ **comment:**
+\\ **comment:** 分类讨论
 ----
@@ 行 40: / 行 46: @@
 ====== 王兴罡 ======
+本周摸鱼
 ----
 ====== 黄旭民 ======
+学习了python，学会了运用python简便解决问题

2020-2021/teams/die_java/weeksummary13.1599117729.txt.gz · 最后更改: 2020/09/03 15:22 由 fyhssgss