求助 CSP-S T2 50pts 做法
  • 板块灌水区
  • 楼主WYZ20030051
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/10/23 07:27
  • 上次更新2023/10/23 08:43:31
查看原帖
求助 CSP-S T2 50pts 做法
526895
WYZ20030051楼主2023/10/23 07:27

该题的 50pts 做法应该是需要 O(n2)O(n^2) 的时间复杂度才能过的吧,然而我太菜了只想到了一个 O(n2logn)O(n^2 logn) 的做法。大致做法是对于每一个子串的起点 ss ,二分出来以 ss 为起点的最长的合法的子串长度(因为子串合法时长度只能是偶数,所以就这么二分的常数应该也特别地小),然后再 O(n)O(n) 判断一下该子串是否合法。找到最长的以 ss 为起点的最长的合法的子串长度后,再让答案累加上 该长度除以 2 。请问这样做对吗(算法正确性和时间复杂度的正确性)?另外再问一下,大家的 50pts 暴力是怎么写的(

2023/10/23 07:27
加载中...