CodeForce Round#276 Div.2

像我这种永远懒得做E,成天水水前四题的咸鱼有啥资格存在?QQ图片20160623113150

A. Factory

One industrial factory is reforming working plan. The director suggested to set a mythical detail production norm. If at the beginning of the day there were x details in the factory storage, then by the end of the day the factory has to produce (remainder after dividing x by m) more details. Unfortunately, no customer has ever bought any mythical detail, so all the details produced stay on the factory.

The board of directors are worried that the production by the given plan may eventually stop (that means that there will be а moment when the current number of details on the factory is divisible by m).

Given the number of details a on the first day and number m check if the production stops at some moment.

Solution

很容易发现a不断进行处理一定会产生循环节,而如果循环节内没有出现0的话就是永远无法达到

于是暴力弄出循环节即可


B. Valuable Resources

Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems.

Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates. The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square.

Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.

Solution

答案很容易发现是x的极差和y的极差的较大值的平方,于是排个序搞搞就好了

n那么小为什么不来一发惊险刺激的枚举呢?


C. Bits

Let's denote as the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and is maximum possible. If there are multiple such numbers find the smallest of them.

Solution

贪心的考虑,先不断地用1堆出一个大于R的数

根据二进制下第i位大于前面所有位代表的数之和可以想到一种贪心的方法

即从最低位向最高位删,删到当前数\in[L,R]为止

时间复杂度O(\log n)


D. Maximum Value

You are given a sequence a consisting of n integers. Find the maximum possible value of (integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.

Solution

先考虑把数字从小到大排序

然后对于a[i],我们需要找到一个a[j]\;\;(j>i)满足a[j]\;mod\;a[i]最大化

而我们知道,mod这个东西,在a[j]=a[i]*k-w的时候满足w越小,模越大

这就有了一个很显然的单调性,只需要判断是否存在就可以了

这点可以二分做到O(\log n),桶则可以做到O(1)

对于判断是否存在a[i]*k只需要直接开桶记录下就可以

由调和级数可以知道这个记录的过程的时间复杂度为O(n\log n)

 

发表评论