47双周赛与231周赛复盘

本周的这两场的比赛都是在国服打的,打的都不是很好(都只a了两题)。其中双周赛第三题被python卡了时间,思路什么都都是完全正确的,周赛的第三题值得学习,双周赛第四题超时,周赛第四题难度有些大。

5682. 所有子字符串美丽值之和

这个题一下想到的是前缀和,并且因为我们要计算26个字母,所以是一个26维的前缀和,我们只需要枚举这些区间,在区间上计算最大值和最小值(注意判断不含的字母),每次更新最大最小即可。

const int maxn = 500+5;
int dp[maxn][26];
class Solution {
public:
int beautySum(string s) {
memset(dp,0,sizeof(dp));
int n = s.size();
for(int i = 0;i < s.size();i++){
for(int j = 0;j < 26;j++){
if(s[i]-'a'==j)
dp[i+1][j] =dp[i][j]+ 1;
else
dp[i+1][j] =dp[i][j];
}
}
int res = 0;
for(int i = 1;i <= n;i++){
for(int j = 0;j < i;j++){
int _max = 0;
int _min = n;
for(int k = 0;k < 26;k++){
int cha = dp[i][k] -dp[j][k];
if (cha > 0){
_max = max(_max,cha);
_min = min(_min,cha);
}
}
res += (_max - _min);
}
}
return res;
}
};

这个题本身不需要两个循环,可以两个循环进行一个合并,也可以进行优化。

5683. 统计点对的数目

这个题本身不难。但是难在时间复杂度,因为时间复杂度过高,所以差三个样例没过。这个题的考察点在于,容斥原理+哈希,对于一个点对来说,链接的边的个数等于,两个节点的度数之和减去这两个点对之间的边数。同时为了减小查找的复杂度,我们需要将所有的边数的频率提前计算出来,也就是用一个哈希表保存起来,这个key的范围是0-最大度数x2,这个题很难想,思路很难。

// Author: huahua
class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<int> node_degrees(n);
unordered_map<int, int> edge_freq;
for (auto& e : edges) {
sort(begin(e), end(e));
++node_degrees[--e[0]];
++node_degrees[--e[1]];
++edge_freq[(e[0] << 16) | e[1]];
}

const int max_degree = *max_element(begin(node_degrees),
end(node_degrees));
// Need pad one more to handle "not found / 0" case.
vector<int> counts(max_degree * 2 + 2);

unordered_map<int, int> degree_count;
for (int i = 0; i < n; ++i)
++degree_count[node_degrees[i]];

for (auto& [d1, c1] : degree_count)
for (auto& [d2, c2] : degree_count)
// Only count once if degrees are different to ensure (a < b)
if (d1 < d2) counts[d1 + d2] += c1 * c2;
// If degrees are the same C(n, 2) to ensure (a < b)
else if (d1 == d2) counts[d1 * 2] += c1 * (c1 - 1) / 2;

for (auto& [key, freq] : edge_freq) {
const int u = key >> 16;
const int v = key & 0xFFFF;
// For a pair of (u, v) their actual edge count is
// d[u] + d[v] - freq[(u, v)] instead of d[u] + d[v]
counts[node_degrees[u] + node_degrees[v]] -= 1;
counts[node_degrees[u] + node_degrees[v] - freq] += 1;
}

// counts[i] = # of pairs whose total edges >= i
for (int i = counts.size() - 2; i >= 0; --i)
counts[i] += counts[i + 1];

vector<int> ans;
for (int q : queries)
ans.push_back(counts[min(q + 1, static_cast<int>(counts.size() - 1))]);
return ans;
}
};

1786. 从第一个节点出发到最后一个节点的受限路径数

这个题是一道很好的题,首先考察了多源最短路径,其次,考察了记忆化搜索,记忆化一般书后序遍历,将求出来的值保存起来。

// copyright from huahua
class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
const int kmod = 1e9+ 7;
using PII = pair<int ,int>;
vector<vector<PII>> g(n+1);
for(const auto& e : edges){
g[e[0]].emplace_back(e[1],e[2]);
g[e[1]].emplace_back(e[0],e[2]);
}
// djstra
vector<int> dist(n+1,INT_MAX / 2);
dist[n] = 0;
priority_queue<PII,vector<PII>,std::greater<PII>> q;
q.emplace(0,n);
while(!q.empty()){
const auto[d,u] = q.top(); q.pop();
for(auto [v,w] : g[u]){
if(dist[u] + w >= dist[v]) continue;
dist[v] = dist[u] + w;
q.emplace(dist[v],v);
}
}

vector<int> dp(n+1,INT_MAX);
// 包装了一个lamda 表达式
function <int(int)> dfs = [&](int u){
if(u == n) return 1;
if(dp[u] != INT_MAX) return dp[u];
int ans = 0;
for(auto [v,w] : g[u]){
if(dist[u] > dist[v])
ans = (ans + dfs(v)) % kmod;
}
dp[u] = ans;
return ans;
};
return dfs(1);
}
};