CF312 div2 CDE

I come back! 还是写博客记录比较爽。。

假期加油!

CF312(div2)  C.Amr and Chemistry

脑洞题

思路:结果是求n个数相同时进行操作的步数,我们可以把每个数所有变化情况都记录下来,并记录出现的次数,因为只有用1e5的数据量。

可以利用二进制的特质,比如对数a1,把a1<<1, a1 <<2 。。。 先把数据量范围内的所有比a1大的数的次数加一,然后a1>>=1,如果此时a1为偶数,只记录a1就可以了,如果是奇数,还需要重新把比它大的所有数都记录一遍(记录指的是  让这个数出现的次数加一)。

CF312(div2)   D.Guess Your Way Out! II

脑洞+1 

思路:把所有出的[l, r]的范围都化成可能存在的区间,并且落实到最后一层,并对每一个可行区间的左端点值+1, 右端点值-1, 这样如果出现可行区间的话一定是这样的

如上图,可以看出,可行结果一定是第四个点。所以我们用线扫描的思想,从左到右就可以解决。

E题。。

数据结构一直太弱, 计数排序+线段树

看人家写的不错: http://www.cnblogs.com/crazyacking/p/4649878.html

原文地址:https://www.cnblogs.com/usedrosee/p/4658845.html