bzoj 4725 [POI2017]Reprezentacje ró?nicowe 暴力-白红宇

bzoj 4725 [POI2017]Reprezentacje ró?nicowe 暴力

阅读量：5265 次

发布时间：2019-06-14

本文共 1728 字，大约阅读时间需要 5 分钟。

[POI2017]Reprezentacje ró?nicowe

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 141 Solved: 67

[][][]

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

Sample Output

6 3

16 15

HINT

Source

暴力跑出来，就log个数，然后随便乱搞，就可以了，枚举就好了，map存一下之类。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
            7 #include 8 9 #define N 1000710 #define it map
             
              
                >::iterator11 using namespace std;12 inline int read()13 {14 int x=0,f=1;char ch=getchar();15 while(!isdigit(ch)){ if(ch=='-')f=-1;ch=getchar();}16 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}17 return x*f;18 }19 20 map
               
                
                  >s;21 int Q,n,cnt;22 int a[N],b[N];23 24 int main()25 {26 a[1]=1,a[2]=2;27 s[1]=make_pair(2,1);28 for(n=3;;n++)29 {30 if(n&1) a[n]=a[n-1]*2;31 else for(int j=1;;j++) if(!s.count(j)) { a[n]=a[n-1]+j; break; }32 for(int j=1;j
                 
                  1e9) break;34 }35 for(it l=s.begin();l!=s.end();l++)36 b[++cnt]=l->first;37 Q=read();38 while(Q--)39 {40 int x=read();41 it l=s.find(x);42 if(l!=s.end())43 printf("%d %d\n",(*l).second.first,(*l).second.second);44 else45 {46 int y=lower_bound(b+1,b+cnt+1,x)-b-1;47 printf("%d %d\n",n+(x-y)*2,n+(x-y)*2-1);48 }49 }50 }