关于acm:ACM算法竞赛日常训练DAY3题解与分析旅游tokitsukaze-and-Soldier

106次阅读

共计 2507 个字符，预计需要花费 7 分钟才能阅读完成。

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 long
using 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
是思考到叶子的深度可能为 2（即叶子的父亲就是根）

    // 此时根肯定被标记，那么叶子就不能被标记

    // 如果是个别状况，那么父亲必定不会被标记（因为父亲的标记须要儿子解决实现之后再决定）

    // 本人就打上标记

    if(g[x].size() == 1 and x != s)return sel[x] = !sel

, void();
    bool tag = true;//tag == true 示意以后点能够被标记
    if(x == s)sel[x] = true;// 根肯定被标记

    else if(sel

)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 long
using 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 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬