【ACM算法竞赛日常训练】DAY3题解与分析【旅游】【tokitsukaze and Soldier】

DAY3共2题:

  • 旅游

  • tokitsukaze and Soldier

? 作者:Eriktse
? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?
? 原文链接(阅读原文获得更好阅读体验):

旅游

题目传送门: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[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 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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?

原文链接:https://www.cnblogs.com/eriktse/p/17258574.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【ACM算法竞赛日常训练】DAY3题解与分析【旅游】【tokitsukaze and Soldier】 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • Python基于回溯法子集树模板实现8皇后问题

    下面是详细讲解“Python基于回溯法子集树模板实现8皇后问题”的完整攻略。 1. 什么是回溯法 回溯法是一种通过断尝试和回溯来寻找解的算法。它通常用于解决组合问题、排列问题、子集问题等。回溯的基本思想是:从问题的某一种状态开始搜索,当搜索到某一状态时,如果这种状态不是问题的解,则回溯到上一个状态续搜索。 2. 子集树模板 子集树是回溯法的一种常用模板,它通…

    python 2023年5月14日
    00
  • Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例 在Python中,我们可以使用笛卡尔积算法实现N个数组排列组合运算。在本攻略中,我们将介绍如何使用Python2.7实现笛卡尔积算法,提供两个例来说明如何使用笛卡尔积算法进行排列组合运算。 步骤:了解笛卡尔积算法 在笛卡尔积算法中我们需要考虑以下因素: 数组:数组是指需要进行排列合运算的N个数…

    python 2023年5月14日
    00
  • Python编程实现粒子群算法(PSO)详解

    Python编程实现粒子群算法(PSO)详解 粒子群算法(PSO)是一种基于群体智能的优化算法,它可以用于解决一些优化问题。在本文中,我们将详细讲解如何使用Python编程实现粒子群算法,包括粒子群算法的基本原理、粒子群算法的应用场景以及粒子群算法的注意事项。 粒子群算法的基本原理 粒子群算法是一种基于群体智能的优化算法。在粒子群算法中,我们将待优化的问题看…

    python 2023年5月13日
    00
  • java数据结构和算法中数组的简单入门

    下面是关于 “JAVA数据结构和算法中数组的简单入门”的攻略。 数组的定义和介绍 在Java中,数组是同一类型的数据元素的集合,元素可以通过索引进行访问。数组的元素可以是各种类型的数据,包括整数,浮点数,字符和字符串等。 在Java中,数组是一个对象。这意味着数组变量是对数组对象的引用,而不是数组对象本身。当你声明一个数组时,你实际上声明了一个数组引用变量。…

    数据结构 2023年5月17日
    00
  • python入门之算法学习

    下面是关于“Python入门之算法学习”的完整攻略。 1. 算法学习概述 算法是计算机科学的核心,是解决问题的有效方法。Python作为一种高级编语言,具简单易学、易读易写等特点,非常适合用于算法学习和实现。本攻略将介绍Python入门之算学习的基本知识实践技巧。 2. 算法学习基础 2.1 算法的定义 算法是一组有限的、清晰、可执行的规则,用于解决特定问题…

    python 2023年5月13日
    00
  • 详解01背包问题原理与使用方法

    01背包问题详解 问题描述 给定一个背包,其容量为 $C$,现在有 $n$ 个物品,其中第 $i$ 个物品的体积为 $w_i$,价值为 $v_i$。问如何选择物品放入背包中,使得背包中物品的总价值最大。 思路分析 动态规划 这是一个经典的动态规划问题,可以使用动态规划来解决。我们定义 $dp[i][j]$ 表示前 $i$ 个物品中,容量为 $j$ 的背包可获…

    算法 2023年3月27日
    00
  • Java数据结构及算法实例:快速计算二进制数中1的个数(Fast Bit Counting)

    Java数据结构及算法实例:快速计算二进制数中1的个数 简介 本文将介绍在Java中快速计算二进制数中1的个数的算法。本算法是一种基于位运算的算法,其核心思想是利用位运算的快捷性,将原问题转化为每次计算一位是否为1的问题,使得计算速度大大提升。 背景知识 在理解本算法之前,需要了解Java中的一些背景知识: 1. 位运算 Java中的位运算符有如下几个: &…

    数据结构 2023年5月17日
    00
  • Java数据结构常见几大排序梳理

    Java数据结构常见几大排序梳理 在Java中,数据排序是非常常见的操作。下面我们详细讲解一下Java数据结构常见几大排序的梳理。 常见几大排序 Java数据结构中常见几种排序算法包括: 冒泡排序(Bubble Sort) 快速排序(Quick Sort) 插入排序(Insertion Sort) 选择排序(Selection Sort) 希尔排序(Shel…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部