CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Update on Wiki ======
   * 创建了本周训练周报

----

====== 团队训练 ======
无

----

====== 每周推荐 ======
**fyh:**
\\ **题目大意：**$(n+1)*m$的矩形，起点在第一行的任意位置，可以选择向右走或者向下走，其中前$n$行每一行都有一段区间$a_i,b_i$，当属于这段区间的时候不能往下走，分别回答从第一行到$2到n+1$行的最短距离。
\\ **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:**考试时候没有调出来这种区间加值递增的线段树

**wxg: **
\\ **题目大意** 在平面直角坐标系中 左下角是原点，边长是 $10^6$ 的正方形区域中，有 $n$ 条水平线段和 $m$ 条竖直线段，并且所有的线段至少与正方形的一侧相交，保证在同一条直线上没有两条线段，问这些线段把这个大正方形分成了多少块。
\\ **tag: **  数状数组
\\ **做法:**  发现有两种情况会让正方形个数增加，1.水平线和竖直线相交会增加一块。2.一条线段的两端都与大正方形相交会增加一块。对于 1 我们可以用数状数组维护每一个 y 轴上的点有多少条水平直线，对于每个竖线统计个数。
\\ **comment: **  增加块数的条件是思考点。

**hxm:**
\\ **题目大意：**   判断两个圆角矩形相交
\\ **tag:**   计算几何
\\ **做法:** 拆分成四个圆和两个矩形，分别判断
圆和圆就比圆心距
矩形和矩形：判断一个矩形的顶点是否在另一个矩形内部。通过叉积的方式
圆和矩形：先判断圆心是否在矩形内，否则只可能是圆与某一条边相交，先判圆心到直线距离，然后再看看两端点在异侧还是同侧
如果在异侧，那么就相交
如果在同侧，那么只有当端点存在于圆内相交


\\ **comment:** 分类讨论

----

====== 个人训练 ======

====== 傅云濠 ======
比赛：cfdiv2#666(ABCD),abc177(ABCDEF)
其中cfdiv2666的D博弈论只是看懂了结论，大概能想象，还不是很深刻理解结论。
\\ 计算几何模板细节完善
----

====== 王兴罡 ======
本周摸鱼

----

====== 黄旭民 ======
学习了python，学会了运用python简便解决问题
CVBB ACM Team

用户工具

站点工具

页面工具
