CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 2020/01/01 -- 2020/02/02 周报 ======

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

无

===== Marvolo =====

==== 专题 ====

无

==== 比赛 ====

[[https://atcoder.jp/contests/abc177|AtCoder Beginner Contest 177]]

==== 题目 ====

见本周推荐

===== Kevin =====

==== 专题 ====

无

==== 比赛 ====

无

==== 题目 ====

无

===== TownYan =====

==== 专题 ====

无

==== 比赛 ====

[[https://atcoder.jp/contests/abc177|AtCoder Beginner Contest 177]]

==== 题目 ====

无

===== 本周推荐 =====

==== Marvolo ====

AtCoder:

[[https://atcoder.jp/contests/abc177/tasks/abc177_f|I hate Shortest Path Problem]]

题意:

给出一个$n*m$的方格,每一行有一些格子是禁止向下走的.现在要求从第一行的某个格子出发,每一次只能向下或者向右走,问走到第$i$行最少要走几步.

tag:线段树

题解:

用一棵线段树维护从第一行走到下面某一行的所有位置各需要走几步.考虑如何向下转移.假如说不能向下走的区间是$[l,r]$,那么线段树中的$[1,l-1],[r+1,m]$位置的值+1,$[l,r]$位置的值加正无穷.又因为,$r+1$这个位置可能从左边的某个位置走过来(显然不用考虑更往右的位置),所以还需要建一个线段树维护下$ans_{i}-i$的值,每次用一个最小值来更新$r+1$这个位置.

comment:自己的思路有一个漏洞,没有考虑$r+1$这个位置.

==== Kevin ====

咕咕咕

==== TownYan ====

咕咕咕

CVBB ACM Team

用户工具

站点工具

页面工具