CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====团队训练=====
^ 比赛时间 ^ 比赛名称 ^ 当场过题数 ^ 至今过题数 ^ 总题数 ^ 排名 ^
|2020-07-25| [[2020牛客暑期多校第五场]] |  5  |  10  |  11  |87/1116|
|2020-07-27| [[2020牛客暑期多校第六场]] |  6  |  8  |  11  |64/1019|
|2020-07-29| [[2020HDU暑期多校第二场]] |  6  |  11  |  12  |N/A|

===== 本周推荐 =====
====2sozx====
===CF 1388 E===
  * 分类：计算几何

  * 题意：给定 $n$ 条平行与 $x$ 轴的线段并且 $y_i>0$ ，现在选择一个向量，将这些线段沿着向量平移到 $x$ 轴，期间线段不能有相交，顶点相交除外，问最后平移到 $x$ 轴后左右端点距离最小值是多少。$(n\le2000,-10^6\le xl_i<xr_i\le10^6,1\le y_i\le10^6)$

  * 题解：有个很显然的结论，如果要达到最小值必然会有两条线段顶点相交，因此我们可以枚举两条线段相交，记录相交时的向量，显然对于两条的线段，如果此时向量位于顶点相交的向量内部，则这两条线段最后会相交，因此我们可以通过扫描线来判断什么向量是可行的。\\ \\ 对于一个向量我们要快速判断通过这个向量移动后 $x$ 坐标的最大值和最小值是多少，考虑一个点 $x_i,y_i$ 通过向量移动会到什么位置。令向量为 $v=(a,b),b<0$ ，这个点最后会到 $(x_i-y_i*a/b,0)$ ，横坐标为关于 $x_i,y_i$ 的一次函数，将一个线段看作两个点，因此可以构造出两个凸壳，然后对于每个可行的向量在上面二分查找即可。注意答案会很大，极大值要开够。

  * comment：考虑的细节挺多，最后这个二分要思考一下，比赛时没想到
====Bazoka13====
===Northern Subregional 2015 K ===
  * 分类：计算几何、$dp$

  * 题意：给定$n$个点($n \leq 2000$)，选出尽量少的点，使得从起点开始沿着给定顺序两点连线移动一个半径为$d(d\leq 10^6)$的圆能够覆盖住所有的点。

  * 题解：$n^2$预处理后$n^2$转移$dp$

  * 利用切线角度的合并可以很轻松的找到对于每个起点，选择哪些点可以覆盖其中间所有的点，$dp$过程中就可以在满足情况的点对之间进行转移，但是有可能会出现回溯的点序(详细图片在[[.bazoka13:geometry|这里]])，因此我们需要正反各扫一次。
  
  * 同时有一个小技巧就是利用旋转和分类处理可以防止$atan2$的奇妙结果影响答案

  * comment：正反遍历实在太顶了，同时旋转处理角度的技巧有get到
====JJLeo===
===2020HDU多校第二场D  Diamond Rush===
  * 分类：dp，数据结构，字符串哈希。

  * 题意：给定一个$n \times n$的方格图，每次只能向右向下走，要从左上角走到右下角。每个方格有一个权值$a_{i,j}$，路径上每经过一个点就会获得${(n^2)}^{a_{i,j}}$的权值。现在有$q$次询问，询问若一个矩形区域不可通过，所有合法路径中的最大权值对$10^9+7$取模。$(n \le 400, q \le 2 \times 10^5)$

  * 题解：如图所示，设灰色区域为被禁止通过的区域，那么所有合法路径一定至少经过了一个红色格子或绿色格子，同时至少经过了一个红色格子或绿色格子的路径也是合法的。因此可以求出每个点分别到起点和终点的最大权值，求一下每一行的前缀后缀最大值即可。{{:2020-2021:teams:farmer_john:jjleo:hdu2020d.png?600|}}

  * 然而cls并没有让这题就这样结束，可以发现权值太大没有办法直接维护。观察权值的底数可以发现我们可以将权值和写成$n^2$进制，这样权值相加可以保证不会发生进位，从而将比较大小改为比较两个字符串的字典序。每次转移中相当于在某一位加了个$1$，因此我们可以用主席树维护每个权值，比较大小时维护区间哈希值，在线段树上二分最长公共前缀，最终比较第一位不同的而得出大小关系。另外因为我们要维护每个点分别到起点和终点的最大值，最终求每一行的最大值前后缀需要进行加法，因为两者相加的哈希值等于两者的哈希值相加，所以直接将两棵树放一起进行比较即可。

  * comment：每一步转化都十分巧妙，同时也十分磨练码力。
=====题目=====
  * [[2020.7.27|每日亿题2020.7.27]]
  * [[2020.7.30|每日亿题2002.7.30]]
=====个人训练=====
===== 2sozx =====

==== 比赛 ====
  * 2020.07.29 [[.2sozx:Educational Codeforces Round 92 (Rated for Div 2)]]
  * 2020.07.30 [[.2sozx:Codeforces Round 660 (Div. 2)|Codeforces Round #660(Div. 2)]]
==== 题目 ====
  * 无
===== Bazoka13 =====
==== 比赛 ====
  * 2020.07.30 [[.bazoka13:Codeforces Round 660 (Div. 2)|Codeforces Round #660(Div. 2)]]
====题目====
===== JJLeo =====
==== 比赛 ====
  * 2020.07.24 [[.JJLeo:codeforces_round_659_div._1|Codeforces Round #659 (Div. 1)]] 
  * 2020.07.25 [[.jjleo:m-solutions_programming_contest_2020|M-SOLUTIONS Programming Contest 2020]]
  * 2020.07.28 [[.jjleo:educational_codeforces_round_92_rated_for_div._2|Educational Codeforces Round 92 (Rated for Div. 2)]]
  * 2020.07.31 [[.JJLeo:codeforces_round_660_div._2_virtual_participation|Codeforces Round #660 (Div. 2) Virtual participation]]
==== 题目 ====
CVBB ACM Team

用户工具

站点工具

页面工具
