DAY3共2题：

  • 游览
  • tokitsukaze and Soldier
作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1093.html

游览

题目传送门：https://ac.nowcoder.com/acm/problem/15748

该题次要考查对树的了解，以及简略的树上dp和贪婪算法。

咱们将会住的节点标记为1，其余不住的节点标记为0。

咱们能够发现，根节点（s）是肯定会标记为1的，那么剩下的节点该怎么调配能够使得标记为1的节点数最多呢？

当咱们在某个点x标记时，咱们能够发现它的父亲、儿子们都不能再被标记了。然而点x的兄弟却不受影响，接下来考虑一下哪些节点的兄弟多呢？应该是叶子节点。

所以咱们能够想到首先将根节点和叶子结点全副都标记为1，而后遍历整棵树，如果某个点的父亲和儿子们都没被标记，那么他也能够被标记为1。

留神思考非凡状况，比方只有一个点的树，只有两个点的树....
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 5e5 + 9, inf = 8e18;bitset<maxn> sel;vector<int> g[maxn];int n, s;void dfs(int x, int pre){    //如果到了叶子节点，就间接标记并返回    //这里sel[x] = !sel[pre]是思考到叶子的深度可能为2（即叶子的父亲就是根）    //此时根肯定被标记，那么叶子就不能被标记    //如果是个别状况，那么父亲必定不会被标记（因为父亲的标记须要儿子解决实现之后再决定）    //本人就打上标记    if(g[x].size() == 1 and x != s)return sel[x] = !sel[pre], void();        bool tag = true;//tag == true示意以后点能够被标记        if(x == s)sel[x] = true;//根肯定被标记    else if(sel[pre])tag = false;//如果父亲被标记了，那么以后点肯定不能被标记            //看看儿子们是否被标记    for(auto &y : g[x])    {        if(y == pre)continue;        dfs(y, x);        if(sel[y])tag = false;    }    sel[x] = tag;}signed main(){    scanf("%lld %lld", &n, &s);        for(int i = 1;i < n; ++ i)    {        int x, y;scanf("%lld %lld", &x, &y);        g[x].push_back(y), g[y].push_back(x);    }        dfs(s, 0);    int ans = 0;    for(int i = 1;i <= n; ++ i)        if(sel[i])ans ++;//统计标记的点的个数    printf("%lld\n", ans);    return 0;}

做完这道题，咱们能够总结一点点对于树上dp这一类题的教训技巧：

1.将非凡点作为根，建设一棵树，建树个别用双向边，边的条数严格等于点的个数-1。

2.优先思考树中非凡的点，比方根、叶子。

3.不要遗记思考非凡状况，比方一条链状的树（此时留神根是否会被断定为叶子、留神复杂度是否会爆）、仅有1个点的树（可能须要特判）。

tokitsukaze and Soldier

题目传送门：https://ac.nowcoder.com/acm/problem/50439

这题次要考查贪婪+优先队列保护区间k个最值。

咱们察看题目能够发现，当咱们枚举到一个士兵的要求是"队伍人数不能超过s[i] = k"时，那么此时军队的战斗力最大值应该是所有s >= k的军人中的最大的k个军人的战斗力之和。

咱们能够思考用一个优先队列保护最大的k个值之和(小根堆，每次弹出最小值，即可保护最大值之和），而后通过限度“遍历形式”使得当遍历到第i集体(s[i] = k)时，优先队列里的所有值对应的s都是>= k的，这样就只需要求出优先队列里最大的k个数字之和即可，这个遍历形式就是依照s[i]降序排列，而后从前往后遍历。

咱们能够保护一个大小始终等于s[i]的优先队列，因为s[i]为降序，所以这个优先队列的元素个数的最大值是始终在减小的，减小的时候只须要弹出最小的元素即可，用一个变量sum保护优先队列里的所有元素之和（push时加上，pop时减去）。

#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e5 + 9;struct Node{    int v, s;}a[maxn];signed main(){    int n;scanf("%lld", &n);        for(int i = 1;i <= n; ++ i)scanf("%lld %lld", &a[i].v, &a[i].s);        sort(a + 1,a + 1 + n, [](const Node &u, const Node &v)         {             return u.s > v.s;         });        priority_queue<int, vector<int>, greater<int> > pq;    int ans = 0, sum = 0;    for(int i = 1;i <= n; ++ i)    {        sum += a[i].v, pq.push(a[i].v);        while(pq.size() > a[i].s)sum -= pq.top(), pq.pop();        ans = max(ans, sum);    }    printf("%lld\n", ans);        return 0;}

经验总结：

1.用某种遍历形式来限度某个条件，比方本题用"降序"来限度在以后点之前的所有点的s[i]都比以后的大或相等。

2.优先队列能够保护区间的k个最值之和，只实用于间断的查问且k只能变小或不变，因为变大的话，不晓得要将哪一个放进去。

最初

感激大家的浏览，欢送大家跟我一起刷题呀！

本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言