首页 > 代码库 > Codeforces Round #381(div 2)

Codeforces Round #381(div 2)

A、(分类讨论)

  题意:你有n本书,有三种买书方案,花a元买1本,花b元买2本,花c元买3本,问最少花多少钱,使得你书的总数是4的倍数

  分析:分类讨论的题,但是要注意你可以买超过4本书……可以买5本、6本、7本让你达到4的倍数

B、=w=

C、(构造)

  题意:设mex[i][j]表示一段区间i,j内最小的没出现过的非负整数,你有m个询问[x,y],构造一个数组a,使得m个询问对应的区间中mex最小的最大。

  分析:易得让最短的区间的值填0..ans-1,构造的话就是先把最短区间从x到y依次填上0..ans-1,再将其他区间排序,从头到尾模拟着补充填

     然后看见了一种十分巧妙的构造方法,就是a[]={0,1,2...ans-1,0,1,2...}这样任意一个区间必然有0..ans-1

D、(dfs序+二分)

  题意:给你一棵树,有点权和边权,对于一个节点u,如果节点v是u的子孙,且dist(u,v)<=val(v),则u能掌握v,问每个节点分别能掌握多少节点。(n<=2e5)

  分析:根据dfs序,对于每次dfs得到的栈里的点,必然是从根开始的一条路径,对于新遍历的节点u,栈中的节点stack[i]满足dist(u,stack[i])的单调性,所以可以根据val(u)的值二分出栈中哪一段点可以掌控节点u,那么给这一段加上1

     这种当然不需要线段树,和一维数组类似,每个点记录和父亲节点的答案差d[i],那么从最底层往上走一遍就得出了每个点的答案,具体的每个点答案是所有儿子节点的答案和。

E、(线段树)

  题意:有n个数,m个操作x,y,z,每次操作先将[x,y]上的数都加上z,然后再询问整个数组最长的“山峰”序列,"山峰”是指先严格单增后严格单减的连续序列。(n<=3e5)

  分析:遇见前后数差的问题,想到写出差值数组,对于数组b[n]得到差值数组a[n-1]

     问题其实就是求a[]数组中最长的+ + + + + - - - - - - -这种序列

     对于修改也很简单,和D题一样,在两个位置删+z -z就行

     这个可以用线段树来维护

     具体的要维护3个域mx,mxl,mxr分别表示区间最长值,从左边开始可以延伸的最长值,从右边开始可以延伸的最长值

     合并[l,mid] [mid+1,r]的时候:

        先就是普通的mx[k]=max(mx[l],mx[r]),mxl[k]=mxl[l],mxr[k]=mxr[r]

        然后看能否再更新

        如果a[mid]和a[mid+1]有一个为0,说明两边无法接起来,就无法更新了

        如果a[mid]是负的,a[mid+1]是正的,也无法接起来,仍旧无法更新

        如果a[mid]和a[mid+1]同号,或者a[mid]为正,a[mid+1]为负,那么很显然可以接,mx[k]再和mxr[l]+mxl[r]比较

        对于mxl和mxr的更新,也是同理分析

Codeforces Round #381(div 2)