题意：一个数列，一开始只有一个1，进行k次操作，每次操作都把数列中原本的数全都翻倍然后追加在数列的后面，形成了一个全新的数列，输出全新数列中l到r的和。
分析：以上的题意是经过转化后的题意，变的非常简单，而不在卡在二维的思维中出不来。
可以看到如果在后半段，就等于前半段对应位置的两倍，可以从最高2^k个数的维护，k不断-1，最终变成维护数列中第一个1，直接返回1即可，形成了一个完美的递归。
1 ll dg(int u ,int d,int k) { 2 if(u==1&&d==1)return 1; 3 int t=k>>1; 4 if(d>t)return 2*dg(u-t,d-t,t); 5 else if(u<=t)return dg(u,d,t); 6 else return dg(t,d,t)+2*dg(u-t,1,t); 7 } 8 9 10 void solve() { 11 int t; 12 scanf("%d",&t); 13 int s=0; 14 while(t--) { 15 int n,u,d; 16 scanf("%d%d%d",&n,&u,&d); 17 int a=1<<n; 18 printf("Case %d: %lld ",++s,dg(a+1-u,a+1-d,a)); 19 } 20 }
但是这样肯定会超市，如果每次都进入第三个if，复杂度直接飙升2^n。
我们可以想到用记忆化的方法，但是2^30二维数组开不下，可以用map来存就行了。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <bitset> 8 #include <string> 9 #include <cctype> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} 24 25 //-------------------------- 26 27 const int maxn=1000010; 28 map<pair<int,int>,ll> m; 29 30 ll dg(int u ,int d,int k) { 31 if(u==1&&d==1)return 1; 32 int t=k>>1; 33 if(d>t){ 34 pair<int,int> p(u-t,d-t); 35 if(!m[p])m[p]=dg(u-t,d-t,t); 36 return 2*m[p]; 37 } 38 else if(u<=t){ 39 pair<int,int> p(u,d); 40 if(!m[p])m[p]=dg(u,d,t); 41 return m[p]; 42 } 43 else { 44 pair<int,int> p1(t,d); 45 pair<int,int> p2(u-t,1); 46 if(!m[p1])m[p1]=dg(t,d,t); 47 if(!m[p2])m[p2]=dg(u-t,1,t); 48 return m[p1]+2*m[p2]; 49 } 50 } 51 52 53 void solve() { 54 int t; 55 scanf("%d",&t); 56 int s=0; 57 while(t--) { 58 int n,u,d; 59 scanf("%d%d%d",&n,&u,&d); 60 int a=1<<n; 61 printf("Case %d: %lld ",++s,dg(a+1-u,a+1-d,a)); 62 } 63 } 64 65 66 67 68 int main() { 69 70 #ifndef ONLINE_JUDGE 71 freopen("in.txt", "r", stdin); 72 freopen("out.txt", "w", stdout); 73 #endif 74 //iostream::sync_with_stdio(false); 75 solve(); 76 return 0; 77 }