首页 > 其他分享 >contest/1922 D Berserk Monster

contest/1922 D Berserk Monster

时间:2024-01-23 22:11:42浏览次数:34  
标签:一次 Monster 攻击 1922 怪物 端点 Berserk

来来来,看看英语不好的我最开始理解的题目是怎么样的:

(1)有一堆怪物在打架,每一次从左到右,一只怪物向离自己最近的怪物攻击一次,每一次怪物都攻击一次后会死掉多少只怪物。怎么做......

(2)仔细阅读以后发现可能是所有怪物同时发动攻击。变简单了。

(3)再阅读,发现所有怪物被攻击以后,受到的伤害并不会被累加,只是说收到的伤害在某一次大于一个值以后(严格大于才会去世)。于是就变得脑残起来。

做法:

记录每一个点最近的左端点和最近的右端点,于是每一次有怪物死掉以后都会导致相邻的点的

左边的点的 右边

右边的点的 左边     点发生变化。

而且每一次可能会死的只有那些最近的端点发生改变的点。

其实就是一道很简单的题目,但是总是喜欢脑补题意,忽略了一些性质。

标签:一次,Monster,攻击,1922,怪物,端点,Berserk
From: https://www.cnblogs.com/ybC202444/p/17983538

相关文章

  • D. Berserk Monsters
    原题链接题解1.最笨的想法,链表,每次在还没被杀死的怪物里遍历一遍,如果被杀死了就从链表中删除这个节点但是TLEon#72.进阶想法,仍然是链表,我们想,如果有些怪物永远都不会被杀死,那我们就没必要遍历它。所以我们从可能被杀死的怪物中遍历如果一个怪物这个回合被杀死,但是在上个回......
  • CF1922F Replace on Segment
    看到有区间操作,结合\(n\le100\)的数据范围,直接考虑区间dp。设\(f_{l,r,x}\)表示将区间\([l,r]\)全部替换成\(x\)的最小步数。首先有\(f_{l,r,x}=\max_{p=l}^{r-1}f_{l,p,x}+f_{p+1,r,x}\),但这无法将该状态下的所有的情况都转移到,所以考虑再设一个\(g_{l,r,x}\)表示......
  • CF526F Pudding Monsters 题解
    题目链接:CF或者洛谷析合树真是连续段问题的降智神器先看下题目的一些特殊性,每行每列恰好有一个棋子。考虑特殊性,\(n\timesn\)的棋盘,那么就该判断是否有\(n\)个棋子,容易观察到,也就是相当于每一行并且每一列都有一个棋子。而容易知道,这些棋子所在的行或者列拿出来应当是“......
  • CF1922
    A简单题。发现如果存在匹配点就yes。B简单题。发现\(2^x+2^y\leq2^z(x,y<z)\),所以必定要有两个同样的最大值,然后直接列,两个最大值\(qzh_{i-1}+C^n_2\),三个\(C^n_3\),注意判0。C简单题。注意到走最近一定不比跳劣,所以能走最近就走最近,否则跳。D发现只有部分可能被选到,......
  • CF1922B & C & D
    CF1922B分析注意到\(2^0+2^1<2^2\),因此若\(a_i\nea_j\nea_k\),这组数就是不合法的,所以题目转化为有多少对三元组\(i,j,k\)使得\(a_i,a_j,a_k\)中至少有两个数相等。考虑分类讨论。第一类,\(a_i,a_j,a_k\)中有两个数相等,不妨设\(a_i=a_j\),那么先开一个map维护所有\(a......
  • CF1784C Monsters (hard version) 题解 线段树
    题目链接:https://codeforces.com/problemset/problem/1784/C题目大意:你面前有\(n\)只怪兽,每只怪兽都有一个初始血量,你可以进行两类操作:操作1:选择任意一个血量大于\(0\)的怪兽,并将它的血量降低\(1\);操作2:将所有存活的怪物的血量各自减去\(1\),如果存在怪物的血量恰好降为......
  • CF1901 D Yet Another Monster Fight 题解
    LinkCF1901DYetAnotherMonsterFightQuestion现在给你一堆怪物,你拥有法术(一个法术可以连续攻击这n个所有怪物),你可以选择任意一个怪物作为法术的第一个攻击目标(伤害为\(x\)),然后除了第一个攻击目标可以任意,其他攻击目标只能为曾经攻击目标的相邻怪物。然后伤害依次递减,\(x......
  • D. Yet Another Monster Fight
    原题链接1.导论这道题能不能用贪心做?答案是不能,具体为什么已经有题解给出回答。当贪心无法求解时,我们考虑一下动态规划。2.算法设计对于任一节点,其最坏情况(即所需最大起始威力值,后文称最大值)是什么?当第一个被攻击的怪物(以下称头怪物)在其右边时,其最大值为右边怪物的数量加上自......
  • 惠普战99 Monster高算工作站发布:96个大核192线程
    惠普发布了战家族新品战99Monster满血高算工作站。据介绍,战99Monster搭载了最新AMD线程撕裂者Pro7000系列处理器,型号为AMDThreadripperPro7995WX,Zen4架构,采用台积电4nm制程。规格达到了恐怖的96核心192线程规模,三级缓存高达384MB,基础频率2.5GHz,最高可睿频至5.1GHz,TDP为35......
  • [题解]AT_abc153_f [ABC153F] Silver Fox vs Monster
    模拟赛最后\(15\)分钟想到的做法。思路首先有一个显然的贪心策略:我们放炸弹的地方要尽可能的使这个炸弹能影响到更多的怪上。那么我们可以将对于一个怪\(i\)能够影响到它的区间表示出来\([\max(1,l_i-d),a_i+r]\)。然后将这些区间排个序,可以粗略画出这样的图:根据上......