第 126 场 LeetCode 双周赛题解

模拟

class Solution {
public:int sumOfEncryptedInt(vector<int> &nums) {int res = 0;for (auto x: nums) {string s = to_string(x);char ch = *max_element(s.begin(), s.end());for (auto &c: s)c = ch;res += stoi(s);}return res;}
};

模拟：用堆维护元素中的最小元素，用数组记录元素是否被标记过，模拟对数组的操作过程

class Solution {
public:using ll = long long;vector<long long> unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;//最小堆int n = nums.size();for (int i = 0; i < n; i++)heap.emplace(nums[i], i);ll s = accumulate(nums.begin(), nums.end(), 0LL);vector<int> tag(n);vector<ll> res;for (auto &q: queries) {if (!tag[q[0]]) {//未被标记过tag[q[0]] = 1;s -= nums[q[0]];}for (int i = 0; i < q[1] && !heap.empty();) {//尽量标记ki个数组中还没有标记的最小元素auto [v, ind] = heap.top();heap.pop();if (tag[ind])continue;tag[ind] = 1;s -= v;i++;}res.push_back(s);}return res;}
};

贪心：记录 $s$ 中各英文字母的出现次数，然后遍历 $s$ ,遇到 $?$ 时将当前出现次数最小的英文字母放至该位置，同时该字母出现次数 $+1$ ，最后对原字符串中所有 $?$ 处的字母进行排序，即得到满足条件的字符串

class Solution {
public:string minimizeStringValue(string s) {vector<int> cnt(26);string res;vector<char> li;vector<int> loc;int j = 0;for (auto c: s)if (c != '?')cnt[c - 'a']++;for (auto c: s) {if (c == '?') {int mn = *min_element(cnt.begin(), cnt.end());for (int i = 0; i < 26; i++)if (cnt[i] == mn) {cnt[i]++;li.push_back('a' + i);loc.push_back(j);break;}}j++;}sort(li.begin(), li.end());for (int i = 0; i < li.size(); i++)s[loc[i]] = li[i];return s;}
};

动态规划：设 $p[i+1][j][v]$ 为字符串 $nums[0,i]$ 中长度为 $j$ 和为 $v$ 的自序列的数目，因为 $nums$ 任意一个长为 $j$ 的子序列，$nums$ 包含该子序列的子序列数目为 $2^{n-j}$ ，所以 $nums$ 中所有子序列的能量和为 ${\sum }_{j=1}^{n}p[n][j][k]\times 2^{n-j}$

class Solution {
public:using ll = long long;int sumOfPower(vector<int> &nums, int k) {ll mod = 1e9 + 7;int n = nums.size();int p[n + 1][n + 1][k + 1];memset(p, 0, sizeof(p));p[0][0][0] = 1;for (int i = 0; i < n; i++) {p[i + 1][0][0] = 1;for (int j = 1; j <= i + 1; j++)for (int v = 1; v <= k; v++) {if (v - nums[i] >= 0)p[i + 1][j][v] = (p[i + 1][j][v] + p[i][j - 1][v - nums[i]]) % mod;p[i + 1][j][v] = (p[i + 1][j][v] + p[i][j][v]) % mod;}}vector<ll> pow(n);pow[0] = 1;for (int i = 1; i < n; i++)pow[i] = pow[i - 1] * 2 % mod;ll res = 0;for (int j = 1; j <= n; j++)if (p[n][j][k])res = (res + p[n][j][k] * pow[n - j]) % mod;return (res + mod) % mod;}
};