目录

3432. 统计元素和差值为偶数的分区方案
3433. 统计用户被提及情况
3434. 子数组操作后的最大频率
3435. 最短公共超序列的字母出现频率

一、统计元素和差值为偶数的分区方案

本题可以直接模拟，当然我们也可以来从数学的角度来分析一下这题的本质

设 $S$ 为数组之和，$L$ 为 $[0,i]$ 的区间和，则 $S-L$ 为 $[i+1,n-1]$ 的区间和，对于任意的 $i$，左右子数组的区间和差值为 $L-(S-L)=2L-S$，题目问有几个 $i$ 的 $2L-S$ 为偶数，显然 $2L-S$ 是否为偶数只和 $S$ 有关，当 $S$ 为偶数时，$2L-S$ 总是为偶数。

故本题的答案是固定的，要么所有的 $2L-S$ 都是偶数，有 $n-1$ 个，要么都不为偶数，有 $0$ 个，代码如下

class Solution {
public:int countPartitions(vector<int>& nums) {int n = nums.size();int s = accumulate(nums.begin(),nums.end(), 0);return s % 2 ? 0 : n - 1;}
};

二、统计用户被提及情况

本题是一个纯模拟题，关键在于如何统计每个用户被提及的次数，而这取决于该用户是否在线。这里我们可以记录每一个用户的最近一次的在线时间，在用它和消息发送的时间进行比较，从而判断出当前消息是否提及该用户，代码如下

class Solution {
public:vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {// cnt 统计答案，online 记录每个用户最近一次上线时间vector<int> cnt(numberOfUsers), online(numberOfUsers);// 按时间顺序排序，注意：题目要求离线操作优先级更高ranges::sort(events, [](const auto& x, const auto & y){int tx = stoi(x[1]), ty = stoi(y[1]);return tx != ty ? tx < ty : x[0][0] == 'O';});for(auto e : events){int time = stoi(e[1]);if(e[0][0] == 'O'){online[stoi(e[2])] = time + 60; // 跟新最新上线时间}else if(e[2][0] == 'A'){for(auto& x : cnt) x++;}else if(e[2][0] == 'H'){for(int i = 0; i < numberOfUsers; i++){if(online[i] <= time){cnt[i]++;}}}else{string t;for(stringstream ss(e[2]); ss >> t; cnt[stoi(t.substr(2))]++);}}return cnt;}
};

三、子数组操作后的最大频率

本题题意为我们可以将任意区间内值为 $x$ 的数变为 $k$，返回进行一次操作后，$k$ 出现的最大频率。显然，我们要分 $3$ 个部分统计 $k$ 的出现次数

• 假定我们让 $[l,r]$ 内的 $x$ 全部变为 $k$
• $k$ 的出现次数 $=[0,l)$ 内的 $k$ 的次数 $+[l,r]$ 内的 $x$ 的出现次数 $+(r,n)$ 内的 $k$ 的出现次数

思路：

1. 由于 $nums$ 中数字范围为 $1$~$50$，所以我们可以暴力枚举需要改变的数字 $x$
2. 子数组相关的问题，可以考虑用动态规划来思考
   • $f[i][0]$ 表示当 $i$ 处于 $[0,l)$ 中时，$[0,i]$ 中 $k$ 的最大出现次数
   • $f[i][1]$ 表示当 $i$ 处于 $[l,r]$ 中时，$[0,i]$ 中 $k$ 的最大出现次数
   • $f[i][2]$ 表示当 $i$ 处于 $(r,n)$ 中时，$[0,i]$ 中 $k$ 的最大出现次数

• $f[i][0]=f[i-1][0]+(nums[i]==k)$，因为 $i\in [0,l)$，则 $i-1\in [0,l)$，所以它只能由自己转移来
• $f[i][1]=max(f[i-1][0],f[i-1][1])+(nums[i]==x)$，因为 $i\in [l,r]$，则 $i-1\in [l,r]$ 或者 $i-1=l-1$，所以它可以由 $f[i-1][0]$ 和 $f[i-1][1]$ 转移来
• $f[i][2]=max(f[i-1][1],f[i-1][2])+(nums[i]==k)$，因为 $i\in (r,n)$，则 $i-1\in (r,n)$ 或者 $i-1=r$，所以它可以由 $f[i-1][0]$ 和 $f[i-1][1]$ 转移来

代码如下

class Solution {// 0 1 2// f[i][j] 表示 i 为 j 状态时，k 出现的最大频率// j = 0, f[i][0] = f[i-1][0] + nums[i] == k// j = 1, f[i][1] = max(f[i-1][1], f[i-1][0]) + nums[i] == x// j = 2, f[i][2] = max(f[i-1][2], f[i-1][1]) + nums[i] == k
public:int maxFrequency(vector<int>& nums, int k) {int n = nums.size();set<int> st(nums.begin(), nums.end());int ans = 0;for(auto x : st){vector<array<int, 3>> f(n + 1);for(int i = 0; i < n; i++){f[i+1][0] = f[i][0] + (nums[i] == k);f[i+1][1] = max(f[i][1], f[i][0]) + (nums[i] == x);f[i+1][2] = max(f[i][2], f[i][1]) + (nums[i] == k);}// 注意：答案只可能在 f[n][1] 或者 f[n][2] 中，因为修改数字总比不修改数字更优ans = max({ans, f.back()[1], f.back()[2]});}return ans;}
};// 空间优化
class Solution {
public:int maxFrequency(vector<int>& nums, int k) {int n = nums.size();set<int> st(nums.begin(), nums.end());int ans = 0;for(auto x : st){int f[3]{};for(int i = 0; i < n; i++){f[2] = max(f[2], f[1]) + (nums[i] == k);f[1] = max(f[1], f[0]) + (nums[i] == x);f[0] = f[0] + (nums[i] == k);}ans = max({ans, f[1], f[2]});}return ans;}
};

四、最短公共超序列的字母出现频率

由于 $words[i].length==2$，所以对于任意字符来说，只要它的出现次数为 2，则可以组成任意一个包含该字符的 $word$，前提是我们将出现了两次的字符都对称的放在两侧，比如字符 $a、b$，如果我们的公共超序列为 $abcdeba$，则 $ab、ac、ad、ae、ba、ca、da、ea、aa$ 所有包含 $a$ 的组合都能得到，同理 $b$ 也是一样

• 简单的证明如下
• 对于字符串 $a\ast \ast \ast \ast \ast a$，显然能组成任意包含字符 $a$ 的长度为 $2$ 的子序列
• 对于字符串 $ab\ast \ast \ast ba$，去掉字符 $a$ 后得字符串 $b\ast \ast \ast b$，显然能组成任意包含 $b$ 的长度为 $2$ 的子序列，除了 $ab、ba$，但是我们在计算字符 $a$ 的组合时，已经计算过 $ab、ba$ 了，故我们能得出包含字符 $a$或 $b$ 的任意组合的长度为 $2$ 的子序列
• 当字符串为$abc\ast \ast \ast cba、abcd\ast \ast \ast dcba、...$ 时，同上
• 通过数学归纳法，得出结论：如果给定的一个或多个字符的个数为 $2$，则我们可以通过上述的构造形式，得到长度为 $2$ 的包含这些字符的所有子序列组合

所以最短公共超序列中每个字符的出现次数要么为 $1$，要么为 $2$。而 $words$ 中最多只有 $16$ 种不同的字符，我们可以枚举每种字符的出现次数的所有可能情况。$($最多有 $2^{16}$种可能$)$

故我们的问题变为判断每种情况是否合法，即是否满足题目要求。根据上面的结论，我们只要关心出现一次的字符即可。
比如对于 $abc$ 这样的最短公共超序列，如果 w o r d s = { a b 、 b c 、 c a } words =\{ab、bc、ca \} words={ab、bc、ca}，则不能满足条件，因为一个 $a$ 不能同时出现在 $c$ 的两边，我们可以将 $words$ 抽象成一个有向图，其中 $ab$ 表示 $a\to b$ 这样一条边，我们只要判断对于出现次数为 $1$ 的字符，在 $words$ 抽象成的有向图中是否有环即可。如果有环则不合法，反之，则合法 。

代码如下

class Solution {
public:vector<vector<int>> supersequences(vector<string>& words) {int n = words.size();vector<vector<int>> g(26);int all = 0; // 用 bit 位是否为 1，表示字符是否出现过for(auto s : words){int x = s[0] - 'a', y = s[1] - 'a';all |= (1 << x) | (1 << y);g[x].push_back(y);}auto has_cycle = [&](int sub)->bool{int color[26]{};// 判断是否有环auto dfs = [&](this auto&& dfs, int x)->bool{color[x] = 1;for(int y : g[x]){if(sub >> y & 1) // 只关注出现次数为 1 次的字符continue;if(color[y] == 1 || color[y] == 0 && dfs(y))return true;}color[x] = 2;return false;};// 有向图不一定连通，所以要字符都要遍历一遍for(int i = 0; i < 26; i++){if(color[i] == 0 && (sub >> i & 1) == 0 && dfs(i)) // 只关注出现次数为 1 次的字符return true;}return false;};unordered_set<int> st;int min_size = INT_MAX;int sub = all; // sub 中用 bit 位是否为 1，表示字符是否出现了 2 次// 遍历字符的出现次数的所有可能情况do{int size = __builtin_popcount((unsigned) sub);if(size <= min_size && !has_cycle(sub)){if(size < min_size){min_size = size;st.clear();}st.insert(sub);}sub = all & (sub - 1);}while(sub != all);// 记录答案vector<vector<int>> ans;for(int sub : st){vector<int> cnt(26);for(int i = 0; i < 26; i++){cnt[i] = (all >> i & 1) + (sub >> i & 1);}ans.push_back(cnt);}return ans;}
};