第 115 场 LeetCode 双周赛题解

模拟

class Solution {
public:vector<int> lastVisitedIntegers(vector<string> &words) {vector<int> res;vector<int> li;for (int i = 0, n = words.size(); i < n;) {if (words[i] != "prev")li.push_back(stoi(words[i++]));else {int j = i;for (; j < n && words[j] == "prev"; j++) {if (li.size() < j - i + 1)res.push_back(-1);elseres.push_back(li[li.size() - (j - i + 1)]);}i = j;}}return res;}
};

贪心：遍历 $groups$ ，若当前元素不等于选择的上一个位置的元素，则将当前位置加入选择的位置子序列，最终返回选择的子序列在 $words$ 对应下标的字符串序列

class Solution {
public:vector<string> getWordsInLongestSubsequence(int n, vector<string> &words, vector<int> &groups) {vector<int> ind;for (int i = 0; i < n; i++)if (ind.empty() || groups[i] != groups[ind.back()])ind.push_back(i);vector<string> res;for (auto x: ind)res.push_back(words[x]);return res;}
};

动态规划：设 $p[i]$ 为以 $i$ 结尾的满足题目所述条件的最长子序列的长度，求出 $p$ 数组后，设 $p[ind]$ 为其最大值，则从 $ind$ 开始逆序求子序列中的各个元素。

class Solution {
public:int comp_dis(string &a, string &b) {//计算字符串a和b的汉明距离if (a.size() != b.size())return -1;int res = 0;for (int i = 0; i < a.size(); i++)if (a[i] != b[i])res++;return res;}vector<string> getWordsInLongestSubsequence(int n, vector<string> &words, vector<int> &groups) {vector<int> p(n);int d[n][n];for (int i = 0; i < n; i++) {p[i] = 1;for (int j = 0; j < i; j++) {if (groups[j] == groups[i])continue;d[i][j] = comp_dis(words[j], words[i]);if (d[i][j] == 1)p[i] = max(p[i], p[j] + 1);//子序列中j可能是i的上一个元素}}int ind = 0;for (int i = 1; i < n; i++)if (p[i] > p[ind])ind = i;vector<string> res;while (1) {//逆序求子序列中的各个元素res.push_back(words[ind]);if (p[ind] == 1)break;for (int j = 0; j < ind; j++)if (groups[j] != groups[ind] && d[ind][j] == 1 && p[j] + 1 == p[ind]) {//j可以是最长子序列中ind的前一个元素ind = j;break;}}reverse(res.begin(), res.end());return res;}
};

动态规划：设 $cnt$ 表示 $nums$ 中 $vi$ 出现 $cnt[vi]$ 次，设 $p_{i,s}$ 为由 $cnt$ 中前 $i$ 个不同 $vi$ 构成的和为 $s$ 的多重集合的数目，有状态转移方程 $p_{i,s}=p_{i-1,s}+p_{i-1,s-vi}+\cdots +p_{i-1,s-vi\times cnt[vi]}$ ，类似的有 $p_{i,s-vi}=p_{i-1,s-vi}+\cdots +p_{i-1,s-vi\times (cnt[vi]+1)}$，合并一下可以得到 $p_{i,s}=p_{i,s-vi}+p_{i-1,s}-p_{i-1,s-vi\times (cnt[vi]+1)}$，另外数组中的 $0$ 需要单独处理，及答案为不考虑 $0$ 时的答案 $\times (cnt[0]+1)$。

class Solution {
public:using ll = long long;ll mod = 1e9 + 7;map<int, int> cnt;int sum_ = 0;int c0 = 0;int le(int mx) {//和不超过mx的子多重集合的数目int n = cnt.size();int p[n + 1][mx + 1];memset(p, 0, sizeof(p));p[0][0] = 1;auto it = cnt.begin();for (int i = 1; i <= n; i++) {int vi = it->first, ci = it->second;for (int s = 0; s <= mx; s++) {p[i][s] = p[i - 1][s];if (s - vi >= 0)p[i][s] = (p[i][s] + p[i][s - vi]) % mod;if (s - vi * (ci + 1) >= 0)p[i][s] = (p[i][s] - p[i - 1][s - vi * (ci + 1)]) % mod;}it++;}ll res = 0;for (int s = 0; s <= mx; s++)res = (res + p[n][s]) % mod;res = (res * (c0 + 1)) % mod;return (res + mod) % mod;}int countSubMultisets(vector<int> &nums, int l, int r) {for (auto x: nums) {if (x)cnt[x]++;elsec0++;sum_ += x;}int vr = le(r);int vl = l != 0 ? le(l - 1) : 0;return ((vr - vl) % mod + mod) % mod;}
};