注:赛后想到特殊性质 B 与正解没有区分度,于是修改了特殊性质 B。
暴力(也许可以瞎猜?)
这也是暴力……不过可以打表
把字符串分成 n 个长度为 2 的子段,看每段字典序是否都单调递增,是就输出 One Answer
,否则输出 No Answer
。
设形如 AB
的字符串有 x 个,n=l 或 n=l-x 有唯一解, l-x < n < l 有多解,否则无解。
动态规划。f[i][j] 表示前 i 个字符划分成 j 段是否可行。
f[i][j] = f[i-1][j-1] | f[i-2][j-1](S[i-1]<S[i])
时间复杂度 O(T \cdot l^2)
动态规划。f[i] 表示编号为 0 \sim i 的字符(如果从 0 开始编号)最多能含有多少个长度为 2 的上升子段。能表示的最少题目数量为 l-f[l-1]。注意有可能有长度为 3 的子段。
时间复杂度 O(\Sigma l)
拆成若干段最长的上升子段(即字典序递增),这些子段的长度能对应最少能表示的题目数。注意有可能有长度为 3 的子段。
时间复杂度 O(\Sigma l)