力扣370周赛

力扣第370场周赛

找到冠军 I

答案即入度为0的点

class Solution {
public:int findChampion(vector<vector<int>>& grid) {vector<int>d(100+5);int n = grid.size() , m = grid[0].size();for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < m ; j ++){if(grid[i][j] == true){d[j] ++;}}}for(int i = 0 ; i < n ; i ++){if(d[i] == 0)return i;}return -1;}
};

找到冠军 II

和I相同，加个判断下入度为0的点的个数即可

class Solution {
public:int findChampion(int n, vector<vector<int>>& edges) {vector<int>d(n+5);for(int i  = 0 ; i < edges.size(); i ++ ){cout << edges[i][1] << " ";d[edges[i][1]]++;}int res = 0 , cnt = 0;for(int i = 0 ; i < n ; i ++){if(d[i] == 0){res  = i;cnt ++;}}if(cnt > 1)return -1;return res;}
};

在树上执行操作以后得到的最大分数

题目可以转化为
在树中选任意节点，使得从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于0且选的值最小
从根节点开始dfs，选根节点或者子树的和

class Solution {
public:long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {vector<vector<int>> g(values.size());long long res = 0;for (auto &e: edges) {int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);}function<long long (int , int )> dfs = [&](int u , int f) -> long long {long long ans = values[u] , su = 0;for(auto j:g[u]){if(j == f)continue;su += dfs(j , u);}if(su == 0 || ans < su)return ans;return su;};for(auto x : values)res += x;res -= dfs(0 , -1);return res;}
};

平衡子序列的最大和

1.定义 b[i] = nums[i] - i，问题变成从 b 中选出一个非降子序列，求对应的 nums 的元素和的最大值，离散化后在1e5内

2.定义 f[i] 表示子序列最后一个数的下标是 i 时，对应的 nums 的元素和的最大值。那么答案就是 max⁡(f)
f[i] = max(f[j] , 0) + nums[i];

3.等式左边单点修改，右边区间查询用线段树优化

class Solution {
public:struct Node{int l, r;long long v;  // 区间[l, r]中的最大值}tr[400008];void pushup(int u){tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);}void build(int u, int l, int r){tr[u] = {l, r};if (l == r) return;int mid = (l + r) >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}long long query(int u, int l, int r){if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;int mid = (tr[u].l + tr[u].r) >> 1;long long v = 0;if (l <= mid) v = query(u << 1, l, r);if (r > mid) v = max(v, query(u << 1 | 1, l, r));return v;}void modify(int u, int x, long long v){if (tr[u].l == x && tr[u].r == x) tr[u].v = v;else{int mid = (tr[u].l + tr[u].r) >> 1;if (x <= mid) modify(u << 1, x, v);else modify(u << 1 | 1, x, v);pushup(u);}}long long maxBalancedSubsequenceSum(vector<int>& nums) {int n = nums.size();// 离散化 nums[i]-iauto b = nums;for (int i = 0; i < n; i++) {b[i] -= i;}sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end()); // 去重build(1, 1, 100001);for (int i = 0; i < n; i++) {// j 为 nums[i]-i 离散化后的值（从 1 开始）int j = lower_bound(b.begin(), b.end(), nums[i] - i) - b.begin() + 1;long long f = max(query(1,0, j), 0LL) + nums[i];modify(1, j, f);}long long res = -0x3f3f3f3f;for(long long x : nums)res = max(res , x);if(query(1,0, 100001) == 0)return res;return query(1,0, 100001);     }
};