Xiao7 发布于2022年11月8日 分享 发布于2022年11月8日 【题目描述】 一开始,病人D的体内只有一个K病毒。但是病毒是会繁殖的,每小时后一个K病毒会“分身术”,变成3个K病毒和一个L病毒,而一个L病毒会变成4个L病毒。 如图所示,红色圆圈表示K病毒,蓝色圆圈表示L病毒。 现在医生要知道,K小时后,第x到y行一共有多少个K病毒? 【输入格式】 输入有多行(最多1000行),每行三个整数,分别是K,x和y 【输出格式】 K小时后第x到y行一共有多少个K病毒 【样例输入】 3 3 7 【样例输出】 14 【数据范围】 0<=K<=30 1<=x<=y<=2^k 【分析】 设f[k,i]表示K小时后最上面i行的K病毒总数,g[k,i]表示K小时后最下面i行的K病毒总数,则所求答案为f[k,y]-f[k,a-1] 如果i>=2^(k-1),则g[k,i]=2g[k-1,i-2^(k-1)]+c[k]),否则g[k,i]=g[k-1,i]。其中c[k]表示3^k f的求解可以参考g数组,此处不再详细说明。 var k,a,b:longint; function c(x:longint):qword; begin if x=0 then exit(1) else exit(c(x-1)*3); end; function f(k,i:longint):qword; var k2:qword; begin if i=0 then exit(0); if k=0 then exit(1); k2:=1 shl (k-1); if i>=k2 then exit(f(k-1,i-k2)+c(k-1)*2) else exit(f(k-1,i)*2); end; function g(k,i:longint):qword; var k2:qword; begin if i=0 then exit(0); if k=0 then exit(1); k2:=1 shl (k-1); if i>=k2 then exit(g(k-1,i-k2)+c(k-1)) else exit(g(k-1,i)); end; begin while not eof do begin readln(k,a,b); writeln(f(k,b)-f(k,a-1)); end; end. 链接帖子 意见的链接 分享到其他网站 更多分享选项…
推荐的帖子