2020-2021:teams:hotpot:200829-200904

差别

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

到此差别页面的链接

--- 2020-2021:teams:hotpot:200829-200904 [2020/09/04 09:30]
lotk
+++ 2020-2021:teams:hotpot:200829-200904 [2020/09/04 14:47] (当前版本)
misakatao 更新
@@ 行 12: / 行 12: @@
 =====比赛=====
+.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/2/5'' ''rank:778''
 =====题目=====
-无
+本周无
 ======陶吟翔======
 =====专题=====
+本周无
 =====比赛=====
+.8.29 [[abc177|Atcoder Beginner Contest 177]] ''prob:5/6/6'' ''rank:638''
+.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/2/5'' ''rank:845''
 =====题目=====
+TCO Algo Round 2B - DIV1 第二题
+TCO South America Qualifier - DIV1 第二题
+TCO Algo Round 3A - DIV1 第一题
+TCO South Asia Qualifier - DIV1 第一题、第二题、第三题
 ======郭衍培======
 =====专题=====
+本周无
 =====比赛=====
+.8.29 [[abc177|Atcoder Beginner Contest 177]] ''prob:5/5/6'' ''rank:1223''
+.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/3/5'' ''rank:886''
 =====题目=====
+本周无
 ======本周推荐======
-林星涵：
+林星涵：[[后缀数组|后缀数组]]
-[[后缀数组|后缀数组]]
+推荐理由：经典的后缀结构工具，用途十分广泛
 陶吟翔：
-题目大意：
+题目大意：有一个$(H+1) \times W$的矩形，你可以从第一行任意一个点出发，只能向下或向右走，但是对于每一行$i$，这一行的第$A_i$到$B_i$个格子不能向下走，问对于$2$到$H+1$，到达这些行最短走几格，如果不能走到输出-1
-数据范围：
+数据范围：$1 \le H,W \le 2 \times 10^5$
-解题思路：
+解题思路：首先走到第$i$行肯定要向下走$i-1$，所以我们考虑最小化往右走的次数，在一开始所有格子的开始和结束位置都是自己，因为可以从任意一个格子开始，往右走最小步数是0，但是对于第$i$行的区间$[A_i,B_i]$，里面所有格子的结束位置是$B_i+1$，因为这些格子不能往下走，而我们发现，一但很多个格子的结束位置相同，我们就不用考虑远的那些，直接考虑最后面那个就行了，所以我们用一个set维护格子，一但有格子结束位置一样我们就删到只剩最后一个，然后每次找向右走步数最少的格子输出，如果格子都被删光了就无法走到，输出-1。关于找到向右走步数最少的格子，可以用一个multiset来存目前剩余的格子的值，输出时直接调用multiset的最小值即可
-推荐理由：
+推荐理由：首先对于最小化向右走的次数和删去不必要的格子考察了做题者的观察能力，同时set和multiset的维护方式考察了做题者的语言运用能力
 郭衍培：
-题目大意：
+题目大意：给定m和一个集合d，一个虫子在$n\times n$的方格中跳。一开始任选一点，每次跳到曼哈顿距离为d中元素的点。一共跳m次，问一共有多少种路径。
-数据范围：
+数据范围：$1\le n\le 10^9$，$0\le m,d_i\le 10$，保证d中元素互不相同。
-解题思路：
+解题思路：每个起点的方案数，只和到四条边的距离有关。其中大于100的距离和100相同。所以每个起点的方案数，都可以在一个$201 \times 201$的方格中找到。dp算出小方格中的结果，对边上和中间的，加上对应点乘个数即可。
-推荐理由：
+推荐理由：很好的题，以前没见过类似的思路

2020-2021/teams/hotpot/200829-200904.1599183014.txt.gz · 最后更改: 2020/09/04 09:30 由 lotk