CodeForces 754 D. Fedor and coupons

Description All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of…

BZOJ 3005 体育课

Description 又是一节体育课的时间了,有n个同学排成了一排。他们都很讨厌排在第一个位置的同学,于是后面的同学中比第一个高的都会产生一个高兴值,这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为0。 现在体育老师来了,他拥有神奇的魔法,现在他能做如下的三件事: 询问某段区间高兴值最大的那个是多少。 把某两个同学交换一下位置。 选取一段区间的人,把第一个人身高加上t,第二个加上2t,第三个加上3t以此类推。 但是体育老师不会数数,于是他找到你了,对于每一个询问,他要你帮他求出那个值。 Input 第一行两个整数n,m表示有n个人,有m个操作。 第二行n个整数,顺序输入每个人的身高。(身高<=10^8) 接下来m行,每行第一个数位一个type表示是做哪一件事情。 如果type=1,那么接下来有两个整数l,r,表示询问这段区间的最大的高兴值 如果type=2,接下来两个整数a,b,表示交换这两个位置的人 如果type=3,接下来三个整数l,r,t,表示把l个人的升高增加t,l+1个人增加2t……

BZOJ 2119: 股市的预测

Description 墨墨的妈妈热爱炒股,她要求墨墨为她编写一个软件,预测某只股票未来的走势。股票折线图是研究股票的必备工具,它通过一张时间与股票的价位的函数图像清晰地展示了股票的走势情况。经过长时间的观测,墨墨发现很多股票都有如下的规律:之前的走势很可能在短时间内重现!如图可以看到这只股票A部分的股价和C部分的股价的走势如出一辙。通过这个观测,墨墨认为他可能找到了一个预测股票未来走势的方法。进一步的研究可是难住了墨墨,他本想试图统计B部分的长度与发生这种情况的概率关系,不过由于数据量过于庞大,依赖人脑的力量难以完成,于是墨墨找到了善于编程的你,请你帮他找一找给定重现的间隔(B部分的长度),有多少个时间段满足首尾部分的走势完全相同呢?当然,首尾部分的长度不能为零。 Input 输入的第一行包含两个整数N、M,分别表示需要统计的总时间以及重现的间隔(B部分的长度)。接下来N行,每行一个整数,代表每一个时间点的股价。 Output 输出一个整数,表示满足条件的时间段的个数 Sample Input 12 4 1 2 3 4 8 9 1 2 3 4 8 9 Sample…

BZOJ 4408: [Fjoi 2016]神秘数

Description 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}, “` 1 = 1 2 = 1+1 3 = 1+1+1 4 = 4 5 = 4+1 6 = 4+1+1 7 = 4+1+1+1 “` 8无法表示为集合S的子集的和,故集合S的神秘数为8。 现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间[l,r](l<=r),求由a[l],a[l+…

BZOJ 3784: 树上的路径

Description 给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序,输出前M个距离值。 Input 第一行两个正整数N,M 下面N-1行,每行三个正整数a,b,c(a,b<=N,C<=10000)。表示结点a到结点b有一条权值为c的边。 Output 共M行,如题所述. Sample Input 5 10 1 2 1 1 3 2 2 4 3 2 5 4…