NOIP T1

灌水区

happy_zero @ 2023-11-18 13:55:17

做法是先把每一行排出最大最小字典序,然后把每一行的最小和所有最大字典序中最小的比较(如果相同则为 1),被怀疑过假做法,但后来想想不是,哪位巨佬能帮忙看看是不是假的吗?


by _farawaystar_ @ 2023-11-18 13:56:06

@happy_zero 不是吧

我也是差不多这么做的


by XZhuRen @ 2023-11-18 13:56:28

防止相同似乎要求次小?


by Jasonshan10 @ 2023-11-18 13:57:24

@XZhuRen 不需要吧


by happy_zero @ 2023-11-18 13:58:22

@XZhuRen 分析过了,应该不用,因为如果有多个最小的那单个最小序肯定小于最大序(这样不会所有都相同),当然也有可能我考虑漏了


by yydfj @ 2023-11-18 14:06:50

@XZhuRen 听说保证字符串互不相同,如果是这样的话不计次小也可以,但是我没看清题目数据,不知道是不是这样。


by happy_zero @ 2023-11-18 14:11:19

@yydfj 是的


by XZhuRen @ 2023-11-18 14:13:34

@yydfj 相同指的是一个字符串既作为最大构成的最小值也作为本身最小构成(例如aaaaab之类,然后有两个(因为不同但是同构))的情况。

但是分类之后似乎不用求?


by yydfj @ 2023-11-18 14:14:53

@XZhuRen 我没有求次小,但是听别人说要求次小,然后我又没看清题目数据,所以很慌


by zgy_123 @ 2023-11-18 14:20:27

@happy_zero 不会炸吗?O(n^2m)


by Wei_miraitowa @ 2023-11-18 14:20:32

所以t1最后一个大样例算强吗


| 下一页