Codeforces Round #764 Masha-forgetful 题解 (Java/C++)

题解

字典树+DP。

首先，任何大于3的数都能表示为若干个2和若干个3的和。因此我们我们每一个区间的长度要么是2要么是3。

那么对于原本的n个电话号码，我们将其所有长度为2和长度为3的子串添加进字典树中被查。字典树将记录这个子串的下标和位置。

接下来就是DP的部分。dp[i]表示前i个数字的解决方案。这里稍微不同寻常的是：dp[i]不是一个数字，而是一个对象。如果dp[i]=null则表示没有解决方案。
于是对于dp[i]的值有两个选择：1. 如果dp[i-2]不为空，且字母i-1和i能在字典树中找到，则dp[i]的值为字典树记录的值。2. 同理，我们考虑3个字母在字典树中查询，并检查dp[i-3]的值。如果都不行，那么dp[i]为空。

于是我们只需要从m到1依次根据字典树和DP的记录计算出每个区间的信息即可。

代码

Java

C++