Description

题目链接:BZOJ 1001

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

左上角点为 $(1,1)$,右下角点为 $(n,m)$(上图中 $n=3, m=4​$)。有以下三种类型的道路:

  1. $(x,y)\longleftrightarrow(x+1,y)$
  2. $(x,y)\longleftrightarrow(x,y+1)$
  3. $(x,y)\longleftrightarrow(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里,现在它们要跑到右下角 $(n,m)$ 的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为 $k$,狼王需要安排同样数量的 $k$ 只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。

数据范围:$1\le n, m\le 1000$。

- 阅读剩余部分 -

Description

题目链接:AGC 027C

给出一个 $n$ 个点,$m$ 条边的无向图(可能有自环)。每个节点有一个值 AB,你可以从任意一个节点出发,经过一些节点后(可以重复经过)并将经过节点的值顺次写出来,就可以得到一个字符串。求是否满足对于任何一个满足只包含 AB 的字符串都可以被这张图构造出来。

数据范围:$n,m\le 2\times 10^5$。

- 阅读剩余部分 -