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

Submission #143438325 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #143440403 - Codeforces
Codeforces. Programming competitions and contests, programming community