翻译有误
  • 板块CF123C Brackets
  • 楼主Exber
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/6/22 15:40
  • 上次更新2023/10/27 22:49:40
查看原帖
翻译有误
251130
Exber楼主2022/6/22 15:40

rt,应该是第 kk 小,而且比较的方法也有误,翻译:

括号数组是一个只有 “(” 或 “)” 两类字符的二维数组。括号数组中的合法路径只能从任意位置开始,向右或向下移动。如果一个 n×mn\times m 括号数组中从 (1,1)(1,1)(n,m)(n,m) 的所有路径经过的字符构成的字符串均为可以匹配的括号序列,则这个括号数组可以被称作神奇数组。

现在定义一种比较神奇数组大小的方式,假设这两个数组分别为 aabb ,两个数组行列数均相等,找到数组中满足条件 ai,jbi,ja_{i,j}\not=b_{i,j} 的位置 (i,j)(i,j),如果有多个这样的位置,则选择优先级最小的位置(给定),如果此时 ai,ja_{i,j} 为 “(",则 a<ba<b,否则 a>ba>b。如果不存在这样的位置,则 aabb 相等。

根据以上定义,请找出第 kk 小的神奇数组,数据保证有解。

输入描述

第一行输入三个整数 n,m,kn,m,k,分别表示数组大小和要寻找的数组编号。

接下来 nn 行,每行包含 mm 个正整数,表示优先级编号 pi,jp_{i,j}(保证 pi,jp_{i,j} 互不相同)。

输出描述

输出第 kk 小的神奇数组

括号数组是一个只有 “(” 或 “)” 两类字符的二维数组。括号数组中的合法路径只能从任意位置开始,向右或向下移动。如果一个 $n\times m$ 括号数组中从 $(1,1)$ 到 $(n,m)$ 的所有路径经过的字符构成的字符串均为可以匹配的括号序列,则这个括号数组可以被称作神奇数组。 

现在定义一种比较神奇数组大小的方式,假设这两个数组分别为 $a$ 和 $b$ ,两个数组行列数均相等,找到数组中满足条件 $a_{i,j}\not=b_{i,j}$ 的位置 $(i,j)$,如果有多个这样的位置,则选择优先级最小的位置(给定),如果此时 $a_{i,j}$ 为 “(",则 $a<b$,否则 $a>b$。如果不存在这样的位置,则 $a$ 和 $b$ 相等。

根据以上定义,请找出第 $k$ 小的神奇数组,数据保证有解。

输入描述

第一行输入三个整数 $n,m,k$,分别表示数组大小和要寻找的数组编号。

接下来 $n$ 行,每行包含 $m$ 个正整数,表示优先级编号 $p_{i,j}$(保证 $p_{i,j}$ 互不相同)。

输出描述

输出第 $k$ 小的神奇数组
2022/6/22 15:40
加载中...