首页 > 代码库 > Find 找规律，递推

Find 找规律，递推

2024-07-12 16:07:53   220人阅读

Find

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

给出N
for(i = 1; i <= N; i ++) a[i] = i;
solve(n,a[]) {
     if(n == 1) return;
    将奇数下标的数赋给a1，假设有len1个
    将偶数下标的数赋给a2，len2个
    solve(len1,a1)
    solve(len2,a2)
    for(int i = 1; i <= len1; i ++) a[i] = a1[i];
    for(int i = 1; i <= len2; i ++) a[i + len1] = a2[i];
}

给出M个查询，1. 查询执行完solve的数组a中第i个数是什么，2. 查询原数组a中第i个数现在的位置

Input

多组数据

对于每组数据，第一行N,M(1 <= N <= 10^18, 1 <= M <= 10^5)

接下来M行，每行两个数x,y (1 <= x <= 2, 1 <= y <= n)

x = 1，查询执行完solve的数组a中第i个数是什么

x = 2, 查询原数组a中第i个数现在的位置

Output

每个查询输出一行，你的答案

Sample Input

4 21 22 46 41 11 51 32 4

Sample Output

341636

Hint

例子N = 4,{1,2,3,4} -> {1,3} + {2,4} = {1,3,2,4}
N = 6,{1,2,3,4,5,6}-> {1,3,5} + {2,4,6} = {1,5} + {3} + {2,6} + {4} = {1,5,3,2,6,4}

 

 

 1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <string.h> 5 #include <algorithm> 6 using namespace std; 7 #define ll long long 8 ll fun2(ll y,ll n) 9 {10     if(y==1)11     return 1;12     if(y&1)13     {14         return fun2(((y>>1)+1),((n+1)>>1));15     }16     else17     {18         return ((n+1)>>1)+fun2(y>>1,n>>1);19     }20 }21 ll fun1(ll y,ll n)22 {23     if(y==1)24     return 1;25     ll m=(n+1)>>1;26     if(y<=m)27     {28         return (fun1(y,m)<<1)-1;29     }30     else31     {32        return  (fun1(y-m,n>>1)<<1);33     }34 }35 int main()36 {37     ll n,x,y,ans;38     int m,i,j;39     while(scanf("%lld%d",&n,&m)!=EOF)40     {41         for(i=0;i<m;i++)42         {43             scanf("%lld%lld",&x,&y);44             if(x==1)45             {46                printf("%lld\n",fun1(y,n));47             }48             else49             {50                 printf("%lld\n",fun2(y,n));51             }52         }53     }54     return 0;55 }
View Code

 


联系
我们