首页 > 其他分享 >[Ynoi2015] 纵使日薄西山

[Ynoi2015] 纵使日薄西山

时间:2024-05-19 16:29:41浏览次数:37  
标签:纵使 顺序 Ynoi2015 日薄西山 相邻 端点 操作

按照题目来模拟,假设\(a_x\)为最大的,那么任意时刻不可能选中\(a_{x-1}\)或者\(a_{x+1}\)来操作的

然后就可以发现,我们选出的数一定是不相邻的,也就是说,我们每次在还可以选择的数中找出最大的数(满足此条件下下标最小),并且把相邻的两个数标记为不可选择,一直重复这个过程直到为\(0\);显然这个过程与操作顺序是无关的,只与我们选择出的数有关,答案就是我们选择出的数的和

像这种操作的数不相邻且操作顺序无关紧要就可以尝试用线段树模拟(操作顺序无关紧要的处理方法太多了,有了操作数不相邻之后,我们就可以在合并区间的时候考虑左子节点的右端点和右子节点的左端点的关系就好了,这里就要用到线段树)

具体见这篇文章

标签:纵使,顺序,Ynoi2015,日薄西山,相邻,端点,操作
From: https://www.cnblogs.com/dingxingdi/p/18200445

相关文章

  • P5070 [Ynoi2015] 即便看不到未来
    题意给定一个序列,静态区间查询区间的长度为\(1\to10\)的极长值域连续段个数。Sol考虑离线下来跑扫描线。枚举右端点,维护每个左端点的答案。不难想到,\(i\)对\(lst[i]\)是没有贡献的,考虑右端点为\(i-1\),若此时的\(l\lelst[i]\)。\(i\)不作贡献。所以我们把值域上......
  • Ynoi2015 我回来了
    介绍个最劣解\(O(m\sqrtn+n\sqrtn+n\alpha(n)\lnn)\)做法。首先令\(b_i\getsa_i-1\),区间\([l,r]\)的答案就是:\[r-l+1+\sum\limits_{k=l}^r\text{mex}_{i=l}^r\left\lfloor\frac{b_i}{k}\right\rfloor\]考虑如何动态维护后面那个式子。我们对每一个\(k\in[1,n]\)维......
  • 【题解】[Ynoi2015] 我回来了
    题目分析:所谓的期望乘以\(R-L+1\)其实就是求亵渎的触发次数,因为我们能选择的伤害只有\(R-L+1\)种。有一个很显然的转化,就是对于伤害\(d\),我们以随从的血量......
  • [Ynoi2015] 纵使日薄西山
    题传考虑一个\(a_i\)变为最大值的时候,由于它与两边的值相对大小不变,因此\(a_i\)造成的贡献必然是它自己,进一步地,题目操作可以简化为每次选择一个靠左地最大值,将其和左......
  • 2021 年终总结|纵使前方不易,独善其身,继续前行。。。
    序言害,最怕的就是年中、年终总结,似乎又是一个忙忙碌碌而又碌碌无为的一年。不过也好,总算是正视过去的一年,吸取经验教训,为了日后做一些规划。好的一点,敢于面对了。其实是舔着......
  • [Ynoi2015] 盼君勿忘
    题传世纪诈骗题首先,所有子序列分别去重的和的意思是什么?令可重集\(S\)为序列\(a_l,a_{l+1}\dotsa_r\)的所有子序契合。假设我们有一个序列\(T\),对\(T\)去重......
  • [Ynoi2015] 此时此刻的光辉
    题传做完CF1422F再做这道题就肥肠有感觉了。如果你不想再看一题那么我就无耻推销一下我的题解。\[\text{————————我是分割线————————}\]请确保你......
  • [Ynoi2015] 我回来了
    题传7个月后再来看这道题,还是感觉太妙了。由于答案最终输出\(E\timesLen\),所以本质上是问\(\foralld\in[L,R]\)的贡献和,再进一步想,亵渎的要求就是寻找序列\[x_......
  • [Ynoi2015] 即便看不到未来
    题传\(O(10n\logn)\)能过,居然不卡常,青结了。感觉是比较套路的一道Ynoi了qwq。首先看题目,需要找的就是一段长度为\(1\dots10\)的极长连续的(公差为1)的等差数......