首页 > 其他分享 >【题解】「NOIP2012」疫情控制

【题解】「NOIP2012」疫情控制

时间:2024-08-16 21:29:47浏览次数:11  
标签:NOIP2012 疫情 题解 军队 节点 我们

https://www.luogu.com.cn/problem/P1084

这道题难在贪心的思路,实现比较简单可以直接看代码。


首先二分。现在转化为判定问题。可以用倍增求出每个军队最上面能到哪。

结论1:

  • 我们一定不会把在除了根节点以外的军队往下移动。否则肯定不优。

所以我们把能走到根节点的先存在一起最后处理,把不能到根节点的军队往上走到最高的位置然后固定。

现在我们可以拿到还需要我们去覆盖的根节点的子儿子的边权,和我们到根节点还能剩下的时间。

如果我们把这两个序列分别从大到小排序,然后

标签:NOIP2012,疫情,题解,军队,节点,我们
From: https://www.cnblogs.com/CloudWings/p/18363627

相关文章

  • [题解] [HNOI2016] 序列
    原题链接题面给定长度为$n$的序列:$a_1,a_2,\cdots,a_n$,记为\(a[1\colonn]\)。类似地,\(a[l\colonr]\)($1\leql\leqr\leqN$)是指序列:$a_{l},a_{l+1},\cdots,a_{r-1},a_r$。若\(1\leql\leqs\leqt\leqr\leqn\),则称$a[s\colont]$是$a[......
  • 2024杭电多校第十场 1002树上询问(题解)
    题意给一棵树,每个节点有一个权值,并且权值是一个排列。接下来有多次操作,每次操作要么是交换两个节点权值,要么是询问一个权值区间\([L,R]\),判断是否存在树上的一个路径,使得路径上的权值恰好都在这个区间里分析由于询问的是树上的一个路径,联想到了树上莫队中对路径的处理。这里......
  • 洛谷p1717题解
    题目描述话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽,为了表示安慰和鼓励,VIP999决定请他吃一次“年年大丰收”,为了表示诚意,他还决定亲自去钓鱼。但是,因为还要准备NOIP2013,z老师只给了他 H 个小时的空余时间,假设有 n 个鱼塘都在一条水平路边,从左......
  • 洛谷p2580题解
    题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉(详情请见已结束比赛CON900)。题目描述这之后校长任命你为特派探员,每天记录他的点名。校长会提供化学竞......
  • 计算1~n的和题解(Mars OJ P1016)
    在这儿问一下,有人用MarsOJ的吗?有的话,评论区里回复一下,谢谢。好了切入正题题目:说明给出正整数n(1<=n<=10⁶),计算1到n的和输入格式一行一个正整数(1<=n<=10⁶)输出格式一行一个整数,表示1到n的和样例 输入数据13输出数据16这题考的时循环,把1~n跑......
  • P4271 [USACO18FEB] New Barns P 题解
    题目传送门前置知识树的直径|最近公共祖先|并查集解法一个显而易见的结论:设点集\(A\)的直径的两个端点为\(u_{1},v_{1}\),另一个点集\(B\)的直径的两个端点为\(u_{2},v_{2}\),则\(A\bigcupB\)的直径端点一定是\(\{u_{1},v_{1},u_{2},v_{2}\}\)中的两个。还有......
  • P8734 奇偶覆盖 题解
    Statement矩形面积并,但是覆盖奇数次、覆盖偶数次的面积要分别输出。Solution提供一种不费脑子的做法:首先离散化、扫描线,问题变成维护区间+1-1、询问全局有多少正数是奇数、多少正数是偶数。若去除“正数”的条件,这是很容易用一个标记下传的线段树维护的,区间分别维护0,1个......
  • Git 命令大全:详细讲解与常见问题解决方案
    目录1.Git基础命令2.分支管理命令3.远程仓库管理命令4.标签管理命令5.其他常用命令6.总结Git是目前最流行的分布式版本控制系统,它使得团队协作和代码管理变得更加高效。本文将详细介绍Git的常用命令及其应用场景,并针对可能遇到的问题提供解决方案。1.Git......
  • P8518 [IOI2021] 分糖果 题解
    DescriptionKhong阿姨正在给附近一所学校的学生准备\(n\)盒糖果。盒子的编号分别为\(0\)到\(n-1\),开始时盒子都为空。第\(i\)个盒子\((0\leqi\leqn-1)\)至多可以容纳\(c[i]\)块糖果(容量为\(c[i]\))。Khong阿姨花了\(q\)天时间准备糖果盒。在第\(j\)天......
  • [CEOI2009] photo 题解
    前言题目链接:洛谷。好多错解都被我叉了,所以来贡献一发正确的题解,并予以解释。题意简述平面上有\(n\)个点,现在要求用最少的底边在\(x\)轴上且面积小于等于\(S\)的矩形覆盖所有点,这些矩形可以重叠。问最少矩形数量。矩形顶点不必是整点。\(n\leq100\)。题目分析没什......