9167 - 多选题(multiple)

注:赛后想到特殊性质 B 与正解没有区分度,于是修改了特殊性质 B。

5pts

暴力(也许可以瞎猜?)

20pts

这也是暴力……不过可以打表

特殊性质 A (含10pts)

把字符串分成 n 个长度为 2 的子段,看每段字典序是否都单调递增,是就输出 One Answer,否则输出 No Answer

特殊性质 B (含15pts)(修改后的)

设形如 AB 的字符串有 x 个,n=ln=l-x 有唯一解, l-x < n < l 有多解,否则无解。

45pts(不含特殊性质)

动态规划。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)

100pts

第一种

动态规划。f[i] 表示编号为 0 \sim i 的字符(如果从 0 开始编号)最多能含有多少个长度为 2 的上升子段。能表示的最少题目数量为 l-f[l-1]。注意有可能有长度为 3 的子段。

时间复杂度 O(\Sigma l)

第二种

拆成若干段最长的上升子段(即字典序递增),这些子段的长度能对应最少能表示的题目数。注意有可能有长度为 3 的子段。

时间复杂度 O(\Sigma l)