程序员们，节日快乐！今天的周赛第一题模拟，有个点卡了一下，不细心；第二题直接暴力搜；第三题分析出一般表达式后直接dfs；第四题拓扑排序。这次的特点就是第三、四题难度有降低。
5906. 句子中的有效单词数
class Solution {public:bool judge(string s){int len = s.size();int k = 0;for(int i = 0; i < len; i ++){if(s[i] >= '0' || s[i] <= '9')return false;else if(s[i] == ',' || s[i] == '.' || s[i] == '.'){if(i != len - 1)return false;}else if(s[i] == '-'){if(i==0 || i == len-1)return false;k++;if(k>=2)return false;}}return true;}int countValidWords(string sen) {int i = 0, cnt = 0;string tmp="";while(i < sen.size()){if(sen[i] == ' ' || i == sen.size() - 1){if(i == sen.size() - 1 && sen[i] != ' ') tmp += sen[i];if(tmp.size() > 0 && judge(tmp))cnt ++;tmp="";}tmp += sen[i];i++;}return cnt;}};
5907. 下一个更大的数值平衡数
class Solution {public:bool judge(int n){vector<int> cnt(10 , 0);while(n){cnt[n % 10] ++;n /= 10;}for(int i = 0; i < 10; i ++)if(cnt[i] != 0 &&cnt[i] != i) return false;return true;}int nextBeautifulNumber(int n) {for(int i = n + 1; i <= 1224444; i ++){if(judge(i))return i;}return -1;}};
5908. 统计最高分的节点数目
首先得稍微推一推这个分数怎么算，抽象出统一的表达式。很明显，删除一个节点后，剩下左子树（如果有的话）、右子树（如果有的话）、以及父节点那边部分（如果有的话），分数也就是 左*右*父节点部分。父节点部分的节点数=n-左-右-1，这也显然。所以分数=左*右*(n-1-左-右)。左、右分别指左右子树的节点数噢。接下来关键的就是如何求左右子树数量，这就直接dfs可以解决。
代码说明：代码里有些地方初始定义的是int，理论上应该没问题，但是实际测试的时候计算分数时出现爆int的情况，所以改成了long long。其次，具体计算分数那行代码，每个部分都与1取了个max，1是乘法的幺元，不影响结果。如果某个节点没有左子树，左子树节点数是0，这部分不应该参与运算，但我们使用了统一的表达式就要保证这个0不会影响结果。
struct node{int left = -1;int right = -1;};class Solution {public:long long int ln[100010],rn[100010];node tree[100010];int dfs(int root){if(root == -1) return 0;int l = dfs(tree[root].left);int r = dfs(tree[root].right);ln[root] = l;rn[root] = r;return l + r + 1;}int countHighestScoreNodes(vector<int>& parents) {long long n = parents.size() , maxn = 0, maxcnt = 0;int root = -1;for(int i = 0; i < n; i ++){int p = parents[i];if(p == -1){root = i;continue;}if(tree[p].left == -1)tree[p].left = i;elsetree[p].right = i;}dfs(root);for(int i = 0; i < n; i ++){long long t = max(1ll , (n - 1 - ln[i] - rn[i])) * max(ln[i] , 1ll) * max(1ll , rn[i]);if( t >= maxn){if(t == maxn)maxcnt ++;else{maxn = t;maxcnt = 1;}}}return maxcnt;}};
5909. 并行课程 III
求AOV网表示的工程的最早结束时间。直接拓扑排序就行。每个节点最早结束时间是和它有（指向它的）边的节点中最晚结束时间加上自己的耗时。所以，边拓扑排序，边更新节点的最早结束时间。
class Solution {public:int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {vector<vector<int> > g(n + 1,vector<int>());vector<int> d(n + 1);vector<int> ans(n + 1);for(auto &x : relations){g[x[0]].push_back(x[1]);d[x[1]] ++;}queue<int> q;for(int i = 1; i <= n; i ++){if(d[i] == 0){q.push(i);ans[i] = time[i - 1];}}while( !q.empty()){int front = q.front();q.pop();for( auto &x : g[front]){d[x] --;if(d[x] == 0)q.push(x);ans[x] = max(ans[x] , ans[front] + time[x - 1]);}}int maxn=-1;for(auto &x : ans)maxn = max(maxn , x);return maxn;}};
文章转载自fighting小王子，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
