UVA 12627 Erratic Expansion （递归，分治）

骑猪看日落 2024-02-17 22:48 17阅读 0赞

题意：一开始有一个红气球，每小时后，一个红气球会变成3个红气球和一个蓝气球，而每一个蓝气球会变成4个蓝气球；经过K个小时后，第A~B行共有多少个红气球？

紫书思路：分治思想，k小时由四个k-1小时的情况而成，其中右下角全是蓝气球，不用考虑。

f(k,i)表示k小时之后最上面i行的红气球总数，g(k,i)表示k小时之后最下面i行的红气球总数（当 i<=0 时，f(k,i) = g(k,i)=0），则所求答案为总的气球个数 - f(k,a-1) -g(k,(1<<k) -b)。

如果i>=2^(k-1)，则满足g(k,i)=2\*g(k-1,i-2^(k-1)) + c(k)，否则g(k,i)=g(k-1,i)。其中，c(k) = 3^k 表示k小时后红气球的总数。

同理可求f(k,i).

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long LL;
    
    LL C(int k){  //红气球总数 
       LL t = 1; 
       for(int i = 0; i < k; i++) t *= 3;
       return t;	
    }
    
    LL F(int k,int a){  //最上面a行 
    	if(a <= 0) return 0;
    	if(k == 0) return 1;
    	if(a <= (1<<k-1)) return 2*F(k-1,a);
    	else return F(k-1,a - (1<<k-1)) + 2*C(k-1);
    }
    
    LL G(int k,int b){  //最下面b行 
    	if(b <= 0) return 0;
    	if(k == 0) return 1;
    	if(b <= (1<<k-1)) return G(k-1,b);
    	else return 2*G(k-1,b - (1<<k-1)) + C(k-1);
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	int cnt =0;
    	while(T--){
    		int K,A,B;
    		scanf("%d%d%d",&K,&A,&B);
    		LL tot = C(K);
    		LL f = F(K,A - 1);
    		LL g = G(K,(1<<K) - B);
    		printf("Case %d: %lld\n",++cnt,tot - f - g);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 12627 Erratic Expansion （递归，分治）

题意：一开始有一个红气球，每小时后，一个红气球会变成3个红气球和一个蓝气球，而每一个蓝气球会变成4个蓝气球；经过K个小时后，第A~B行共有多少个红气球？紫书思路：分治思想，

骑猪看日落/ 2024年02月17日 22:48/ 0 赞/ 18 阅读

相关二分法递归查找 (递归分治篇)------- 算法笔记013

问题引出 > 给出我们一组数据：1 2 3 4 5 6 7 8 9 10 > 要求返回要查找数据的下标对于这样的一个问题我们可以有两种思路去解决；第一种：

Dear 丶/ 2023年07月04日 12:41/ 0 赞/ 75 阅读

相关递归与分治法

将问题分解，通过求解局部性的小问题来解开与原本的问题。这种技巧称为分治法，我们在很多算法中都能看到。这个算法的步骤如下： 1.将问题"分解“成局部问题 2.递归地求解局

水深无声/ 2022年12月03日 13:27/ 0 赞/ 202 阅读

相关 uva 12627——Erratic Expansion

题意：一开始有1个红气球，每小时一个红气球都会变成3个红气球和1个蓝气球，1个蓝气球会变成4个蓝气球，问k个小时后a行到b行的红气球的数量。思路：递推。a为偶数时

客官°小女子只卖身不卖艺/ 2022年08月10日 00:59/ 0 赞/ 25 阅读

相关第二章递归与分治策略

学习要点理解递归的概念掌握设计有效算法的分治策略通过下面的范例学习分治策略设计技巧分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相

悠悠/ 2022年08月01日 00:19/ 0 赞/ 203 阅读

相关递归与分治——字典序排列

问题描述： n个元素\{1,2,..., n \}有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当

古城微笑少年丶/ 2022年06月09日 10:30/ 0 赞/ 288 阅读

相关期末复习——递归与分治策略

【1】阶乘函数 int DiGui(int n) { if(n==0) return 1; retur

偏执的太偏执、/ 2022年06月02日 02:35/ 0 赞/ 223 阅读

相关 UVA 12627 Erratic Expansion

题目大致意思为告诉你一个红球为0时状态，已知一个红球每过一个时间会变为文档所示图中的3红1蓝，而蓝球每过一个时间则会变为4个蓝球。问在某一时刻，h1与h2之间的红球有几个。

ゝ一世哀愁。/ 2022年05月16日 10:10/ 0 赞/ 93 阅读

相关递归和分治思想及其应用

目录递归和分治思想一些实例逆序输出字符串查找数组元祖是否存在汉诺塔问题八皇后问题

末蓝、/ 2022年05月16日 01:35/ 0 赞/ 202 阅读

相关算法实验——递归与分治

一、实验目的：理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。具体要求： 1. 分析

古城微笑少年丶/ 2022年05月13日 14:54/ 0 赞/ 277 阅读