月度归档:2016年12月

BZOJ 4723: [POI2017]Flappy Bird(贪心+递推)

Description

《飞扬的小鸟》是一款风靡的小游戏。在游戏中,小鸟一开始位于(0,0)处,它的目标是飞到横坐标为X的某个位置
上。每一秒,你可以选择点击屏幕,那么小鸟会从(x,y)飞到(x+1,y+1),或者不点击,那么小鸟会飞到(x+1,y-1)
。在游戏中还有n个障碍物,用三元组(x[i],a[i],b[i])描述,表示在直线x=x[i]上,y<=a[i]或者y>=b[i]的部分
都是障碍物,碰到或者擦边都算游戏失败。请求出小鸟从(0,0)飞到目的地最少需要点击多少次屏幕。

Input

第一行包含两个整数n(0<=n<=500000),X(1<=n<=10^9)。
接下来n行,每行三个整数x[i],a[i],b[i](0<x[i]<X,-10^9<=a[i]<b[i]<=10^9)。
数据保证x[i]<x[i+1]。

Output

如果无论如何都飞不到目的地,输出NIE,否则输出点击屏幕的最少次数。

Sample Input

4 11
4 1 4
7 -1 2
8 -1 3
9 0 2

Sample Output

5

HINT

 

思路:有一个贪心的想法,如果我们维护每个障碍的上下区间,我们点击最少的次数所能到的点,一定是最后那个障碍物的下区间。考虑从前往后递推这个可行区间,如果两个障碍物之间一次都不点肯定是跌了x[i]-x[i-1],假如每次都点,那么就是x[i]+x[i+1]。然后根据障碍物确定出的上下区间,卡一卡,推出真正的可行区间。。。

 

BZOJ 4725: [POI2017]Reprezentacje ró?nicowe(打表暴力)

Description

给定一个数列a:
当n<=2时,a[n]=n
当n>2,且n是奇数时,a[n]=2a[n-1]
当n>2,且n是偶数时,a[n]=a[n-1]+r[n-1]
其中r[n-1]=mex(|a[i]-a[j]|)(1<=i<=j<=n-1),mex{S}表示最小的不在S集合里面的非负整数。
数列a的前若干项依次为:1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980。
可以证明,对于任意正整数x,只存在唯一一对整数(p,q)满足x=a[p]-a[q],定义为repr(x)。
比如repr(17)=(6,3),repr(18)=(16,15)。
现有n个询问,每次给定一个正整数x,请求出repr(x)。

Input

第一行包含一个正整数n(1<=n<=10^5)。
接下来n行,每行一个正整数x(1<=x<=10^9),表示一个询问。

Output

输出n行,每行两个正整数p,q,依次回答每个询问。

Sample Input

2
17
18

Sample Output

6 3
16 15
思路:打了个表发现,超过57项以后,如果i为奇数那么a[i]-a[i-1]>1e9.所以超过57项以后的a[i](i是一个偶数)如果还和某个数的差小于1e9必然是和它前面的相邻奇数。
然后暴力算出来,前57项的所有数之间的差,以及他们的差都是什么。
对于查询,如果在前面57项里查到了就输出。否则的话,需要二分在表里找到最大的小于他的数并得到他是在表里的第几个。因为r[]是递增的,那么如果当前x代表了一个r[i],也就意味着前面的x-1个数都已经被别的数对所代表了。又因为表里有num个,这是前57项里有的。那么x-num就是从57项后的第几个数对有这样一个差x。那么每一个数对2个数,又因为这样的计算包含了最后差等于x的那个数对,所以答案就是(57+(x-num)*2-1,57+(x-num)*2-2).

 

BZOJ 4724: [POI2017]Podzielno(数学+二分)

Description

B进制数,每个数字i(i=0,1,…,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零,不需要
用完所有数字),使得X是B-1的倍数。q次询问,每次询问X在B进制下的第k位数字是什么(最低位是第0位)。

Input

第一行包含两个正整数B(2<=B<=10^6),q(1<=q<=10^5)。
第二行包含B个正整数a[0],a[1],a[2],…,a[B-1](1<=a[i]<=10^6)。
接下来q行,每行一个整数k(0<=k<=10^18),表示一个询问。

Output

输出q行,每行一个整数,依次回答每个询问,如果那一位不存在,请输出-1。

Sample Input

3 3
1 1 1
0
1
2

Sample Output

0
2
-1
思路:对于一个B进制数,假设他的某一位为a,那么就相当于,然后,通过二项式展开,.所以说这个题目就是说让你求一个最大的B进制数满足它的各位相加是B-1的倍数。
因为a[i]均大于1,那么如果所有的数加起来模上一个B-1不等于0,那我们就把那个数删掉。做完这一切后,相当于我们已经把题目要求的数求出来了。
因为要最大,所以肯定要把越大的数往更高的位置放。所以维护一个前缀和,满足了单调性,然后二分答案。