首页 > 代码库 > （记忆化+暴力）UVA - 12627 Erratic Expansion
（记忆化+暴力）UVA - 12627 Erratic Expansion
题意：一个数列，一开始只有一个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\n",++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\n",++s,dg(a+1-u,a+1-d,a));62 }63 }64 65 66 67 68 int main() {69 70 #ifndef ONLINE_JUDGE71 freopen("in.txt", "r", stdin);72 freopen("out.txt", "w", stdout);73 #endif74 //iostream::sync_with_stdio(false);75 solve();76 return 0;77 }
（记忆化+暴力）UVA - 12627 Erratic Expansion
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。