目录
Q1. 数字小镇中的捣蛋鬼
原题链接
思路分析
AC代码
Q2. 最高乘法得分
原题链接
思路分析
AC代码
Q3. 形成目标字符串需要的最少字符串数 I
原题链接
思路分析
AC代码
Q4. 形成目标字符串需要的最少字符串数 II
原题链接
思路分析
AC代码
Q1. 数字小镇中的捣蛋鬼
原题链接
Q1. 数字小镇中的捣蛋鬼
思路分析
签到题
AC代码
class Solution:def getSneakyNumbers(self, nums: List[int]) -> List[int]:cnt = Counter(nums)return [x for x in set(nums) if cnt[x] == 2]Q2. 最高乘法得分
原题链接
Q2. 最高乘法得分
思路分析
划分型dp
定义状态f(i, j) 为 b 前 i 个数 和 a 前 j 个数匹配的最大得分
那么 f(i + 1, j) = max{f(i, j), f(i, j - 1) + a[j - 1] * b[j]}
时间复杂度O(4len(b))
AC代码
class Solution:def maxScore(self, a: list[int], b: list[int]) -> int:n = len(b)f = [[-inf] * 5 for _ in range(n + 1)]f[0][0] = 0for i in range(n):f[i + 1][0] = 0for j in range(1, 5):f[i + 1][j] = max(f[i + 1][j], f[i][j - 1] + a[j - 1] * b[i], f[i][j])return max(f[i][4] for i in range(n + 1))Q3. 形成目标字符串需要的最少字符串数 I
原题链接
Q3. 形成目标字符串需要的最少字符串数 I
思路分析
见Q3
AC代码
auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);return 0;
}();constexpr int inf = 1e9;
struct AhoCorasick {static constexpr int ALPHABET = 26;struct Node {int len = 0;int fail = 0;array<int, ALPHABET> son;int last = 0;Node() : son{} {}};vector<Node> tr;AhoCorasick() {init();}void init() {tr.reserve(5000);tr.assign(2, Node());tr[0].son.fill(1);tr[1].last = 1;}int newNode() {tr.emplace_back();return tr.size() - 1;}void add(const string& s) {int p = 1, i = 1;for (char ch : s) {int x = ch - 'a';if (!tr[p].son[x])tr[p].son[x] = newNode();p = tr[p].son[x];tr[p].len = i ++;}}void build() {queue<int> q;q.push(1);while (q.size()) {int x = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[x].son[i]) {tr[x].son[i] = tr[tr[x].fail].son[i];continue;}tr[tr[x].son[i]].fail = tr[tr[x].fail].son[i];tr[tr[x].son[i]].last = tr[tr[tr[x].son[i]].fail].len ? tr[tr[x].son[i]].fail : tr[tr[tr[x].son[i]].fail].last;q.push(tr[x].son[i]);}}}int son(int p, int x) {return tr[p].son[x];}int fail(int p) {return tr[p].fail;}int last(int p) {return tr[p].last;}int len(int p) {return tr[p].len;}int size() {return tr.size();}
};class Solution {
public:int minValidStrings(vector<string>& words, string target) {int m = words.size(), n = target.size();AhoCorasick ac;for (auto &s : words) ac.add(s);ac.build();vector<int> f(n + 1, inf);f[0] = 0;int cur = 1;for (int i = 1; i <= n; ++ i) {cur = ac.son(cur, target[i - 1] - 'a');if (ac.len(cur))f[i] = min(f[i], f[i - ac.len(cur)] + 1);}return f[n] == inf ? -1 : f[n];}
};Q4. 形成目标字符串需要的最少字符串数 II
原题链接
Q4. 形成目标字符串需要的最少字符串数 II
思路分析
AC自动机+dp
一个很暴力的思路就是把所有前缀都存AC自动机里面，然后在AC自动机上匹配target来进行dp
和3213. 最小代价构造字符串做法一样
但是存所有前缀会爆掉，我们修改一下AC自动机的插入，对于一个单词的插入，路径上的节点都是一个单词结尾
这样我们看似只插入了每个单词，实际上我们插入了每个单词的所有前缀
定义状态 f(i) 为 构造target 前 i 个字符所需最少字符串数
当前匹配到i，对应自动机节点为cur，那么转移方程为：
f(i) = min{f[i], f[i - ac.len(cur)] + 1}
为什么呢？不应该匹配所有前缀吗？
事实上，如果target可以构造，事实上存在合法构造，下图一定存在若干不相交的线段覆盖整个区间那么我们把target当成一个文本串，我们可以在上面匹配出所有target包含的是自动机中单词的子串，而我们每次跳fail指针，都是跳最长后缀
如果存在多组覆盖整个区间的不相交线段组，我们一定会走线段数最少的那一条
事实上，多组合法覆盖一定是相交的，我们假如正走在一条非最优解路径，到达一条线段的结束的时候我们自然会往最优解路径的方向去跳
这个过程可以手玩一下来加深理解
时间复杂度O(Σlen(words[i]))
AC代码
auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);return 0;
}();constexpr int inf = 1e9;
struct AhoCorasick {static constexpr int ALPHABET = 26;struct Node {int len = 0;int fail = 0;array<int, ALPHABET> son;int last = 0;Node() : son{} {}};vector<Node> tr;AhoCorasick() {init();}void init() {tr.reserve(5000);tr.assign(2, Node());tr[0].son.fill(1);tr[1].last = 1;}int newNode() {tr.emplace_back();return tr.size() - 1;}void add(const string& s) {int p = 1, i = 1;for (char ch : s) {int x = ch - 'a';if (!tr[p].son[x])tr[p].son[x] = newNode();p = tr[p].son[x];tr[p].len = i ++;}}void build() {queue<int> q;q.push(1);while (q.size()) {int x = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[x].son[i]) {tr[x].son[i] = tr[tr[x].fail].son[i];continue;}tr[tr[x].son[i]].fail = tr[tr[x].fail].son[i];tr[tr[x].son[i]].last = tr[tr[tr[x].son[i]].fail].len ? tr[tr[x].son[i]].fail : tr[tr[tr[x].son[i]].fail].last;q.push(tr[x].son[i]);}}}int son(int p, int x) {return tr[p].son[x];}int fail(int p) {return tr[p].fail;}int last(int p) {return tr[p].last;}int len(int p) {return tr[p].len;}int size() {return tr.size();}
};class Solution {
public:int minValidStrings(vector<string>& words, string target) {int m = words.size(), n = target.size();AhoCorasick ac;for (auto &s : words) ac.add(s);ac.build();vector<int> f(n + 1, inf);f[0] = 0;int cur = 1;for (int i = 1; i <= n; ++ i) {cur = ac.son(cur, target[i - 1] - 'a');if (ac.len(cur))f[i] = min(f[i], f[i - ac.len(cur)] + 1);}return f[n] == inf ? -1 : f[n];}
};
