矩阵
「CF750E」New Year and Old Subsequence-矩阵+线段树+dp
· ✏️ 1156 words · ☕ 3 mins read

定义一个数字串为“妙”的当且仅当:该串包含某一子序列为 $2017$ ,且不包含子序列 $2016$。

定义一个数字串的“丑值”为:该串至少删去几个字符,可以使得剩余串变“妙”;如果删去任意多个字符,均无法使该串变“妙”,则该串的“丑值”是 $-1$。

给定一个长度为 $n$ 的数字串 $s$ 。有 $q$ 次询问,每次询问用 $(l_i,r_i)$ 表示。对于每次询问,回答子串 $s[l_i…r_i]$ 的“丑值”。