题解 - Vijos

0

zhanghanchu LV 7 @ 2022-03-07 18:24:42

正确做法：
盘数为n时，答案是2^n-1.
盘数为2n时，答案是2*（2^n-1）.
要用高精度来做.
AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[1010000]={0,1};
int main()
{
    int la=1,s=0,n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=la;j++) a[j]*=2;
        for(int j=1;j<=la;j++)
        {
            s=0;
            if(a[j]>9)
            {
                a[j+1]+=a[j]/10;
                a[j]%=10;
                s=max(s,j+1);
            }
        }
        la=max(la,s);
    }
    a[1]--;
    for(int j=1;j<=la;j++) a[j]*=2;
    for(int j=1;j<=la;j++)
    {
        s=0;
        if(a[j]>9)
        {
            a[j+1]+=a[j]/10;
            a[j]%=10;
            s=max(s,j+1);
        }
    }
    la=max(la,s);
    for(int i=la;i>=1;i--) cout<<a[i];
    return 0;
}

0

阳光逸骏 LV 8 @ 2017-11-04 20:43:37

//快速幂+递推式：2^p-2,且个位一定是>=2的数，减2后必定不退位
var n,l,i:longint;
a:array[0..100001]of longint;
s:ansistring;
function multiply(s:longint):ansistring;
var i,j,k:longint;
begin
fillchar(a,sizeof(a),0);
a[1]:=1;
l:=1;
for i:=1 to s div 27 do
begin
for j:=1 to l do a[j]:=a[j]*134217728;
for j:=1 to l do
if a[j]>=10 then
begin
a[j+1]:=a[j+1]+a[j] div 10;
a[j]:=a[j] mod 10;
end;
k:=l+10;
while a[k]=0 do dec(k);
while(l<=k)or(a[l]>0)do
begin
a[l+1]:=a[l+1]+a[l] div 10;
a[l]:=a[l] mod 10;
l:=l+1;
end;
dec(l);
end;
for i:=1 to s mod 27 do
begin
for j:=1 to l do a[j]:=a[j]*2;
for j:=1 to l do
if a[j]>=10 then
begin
a[j+1]:=a[j+1]+a[j] div 10;
a[j]:=a[j] mod 10;
end;
k:=l+2;
while a[k]=0 do dec(k);
while(a[l]>0)or(l<=k)do
begin
a[l+1]:=a[l+1]+a[l] div 10;
a[l]:=a[l] mod 10;
l:=l+1;
end;
dec(l);
end;
for i:=l downto 1 do multiply:=multiply+chr(a[i]+48);
end;
begin
readln(n);
s:=multiply(n+1);
for i:=1 to length(s)-1 do write(s[i]);
writeln(chr(ord(s[length(s)])-2));
end.

0

FFFeiya LV 8 @ 2017-09-19 20:44:29

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

struct gade{
    int num[100]={0};
    int len;
};

gade as;

int maxe(int a,int b){
    if (a>b) return a;
    else return b;
}

gade c(gade a,gade b){
    gade ans;
    ans.len=maxe(a.len,b.len);
    for (int i=0;i<a.len;i++){
        for (int j=0;j<b.len;j++){
            int v=a.num[i]*b.num[j];
            ans.num[i+j]=ans.num[i+j]+v;
            //ans.num[i+j+1]+=v/10;
        }
    }
    for (int i=0;i<a.len+b.len;i++){
        if (ans.num[i]>9){
            ans.num[i+1]+=ans.num[i]/10;
            ans.num[i]%=10;
        }
    }
    int e=a.len+b.len-1;
    while (ans.num[e]==0) e--;
    ans.len=e+1;
    /*cout<<ans.num[ans.len]<<" ";
    for (int i=a.len-1;i>=0;i--){
        cout<<a.num[i];
    }
    cout<<"*";
    for (int i=b.len-1;i>=0;i--){
        cout<<b.num[i];
    } 
    cout<<"=";
    for (int i=ans.len-1;i>=0;i--){
        cout<<ans.num[i];
    } 
    cout<<endl;*/
    return ans;
}

gade j(gade a,int b){
    gade ans=a;
    ans.num[0]-=b;
    for (int i=0;i<a.len;i++){
        if (ans.num[i]<0){
            ans.num[i+1]-=1;
            ans.num[i]+=10; 
        }
    }
    if (ans.num[ans.len-1]==0) ans.len--;
    return ans;
    
}

gade powe(gade x,int y){
    //cout<<y<<" ";
    if (y==1) return x;
    return c(powe(x,y/2),powe(x,y-y/2));
}

int main(void){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int n;
    cin>>n;
    as.num[0]=2;
    as.len=1;
    gade f=j(powe(as,n+1),2);
    for (int i=f.len-1;i>=0;i--){
        cout<<f.num[i];
    }
}

递归化乘方+高精度算法

0

a1048576 LV 8 @ 2016-10-25 19:40:13

O（1）的算法
const
a:array[1..200] of string=('2','6','14','30','62','126','254','510','1022','2046','4094','8190','16382','32766','65534','131070','262142','524286','1048574','2097150','4194302','8388606','16777214','33554430','67108862','134217726','268435454','536870910','1073741822','2147483646','4294967294','8589934590','17179869182','34359738366','68719476734','137438953470','274877906942','549755813886','1099511627774','2199023255550','4398046511102','8796093022206','17592186044414','35184372088830','70368744177662','140737488355326','281474976710654','562949953421310','1125899906842622','2251799813685246','4503599627370494','9007199254740990','18014398509481982','36028797018963966','72057594037927934','144115188075855870','288230376151711742','576460752303423486','1152921504606846974','2305843009213693950','4611686018427387902','9223372036854775806','18446744073709551614','36893488147419103230','73786976294838206462','147573952589676412926','295147905179352825854','590295810358705651710','1180591620717411303422','2361183241434822606846','4722366482869645213694','9444732965739290427390','18889465931478580854782','37778931862957161709566','75557863725914323419134','151115727451828646838270','302231454903657293676542','604462909807314587353086','1208925819614629174706174','2417851639229258349412350','4835703278458516698824702','9671406556917033397649406','19342813113834066795298814','38685626227668133590597630','77371252455336267181195262','154742504910672534362390526','309485009821345068724781054','618970019642690137449562110','1237940039285380274899124222','2475880078570760549798248446','4951760157141521099596496894','9903520314283042199192993790','19807040628566084398385987582','39614081257132168796771975166','79228162514264337593543950334','158456325028528675187087900670','316912650057057350374175801342','633825300114114700748351602686','1267650600228229401496703205374','2535301200456458802993406410750','5070602400912917605986812821502','10141204801825835211973625643006','20282409603651670423947251286014','40564819207303340847894502572030','81129638414606681695789005144062','162259276829213363391578010288126','324518553658426726783156020576254','649037107316853453566312041152510','1298074214633706907132624082305022','2596148429267413814265248164610046','5192296858534827628530496329220094','10384593717069655257060992658440190','20769187434139310514121985316880382','41538374868278621028243970633760766','83076749736557242056487941267521534','166153499473114484112975882535043070','332306998946228968225951765070086142','664613997892457936451903530140172286','1329227995784915872903807060280344574','2658455991569831745807614120560689150','5316911983139663491615228241121378302','10633823966279326983230456482242756606','21267647932558653966460912964485513214','42535295865117307932921825928971026430','85070591730234615865843651857942052862','170141183460469231731687303715884105726','340282366920938463463374607431768211454','680564733841876926926749214863536422910','1361129467683753853853498429727072845822','2722258935367507707706996859454145691646','5444517870735015415413993718908291383294','10889035741470030830827987437816582766590','21778071482940061661655974875633165533182','43556142965880123323311949751266331066366','87112285931760246646623899502532662132734','174224571863520493293247799005065324265470','348449143727040986586495598010130648530942','696898287454081973172991196020261297061886','1393796574908163946345982392040522594123774','2787593149816327892691964784081045188247550','5575186299632655785383929568162090376495102','11150372599265311570767859136324180752990206','22300745198530623141535718272648361505980414','44601490397061246283071436545296723011960830','89202980794122492566142873090593446023921662','178405961588244985132285746181186892047843326','356811923176489970264571492362373784095686654','713623846352979940529142984724747568191373310','1427247692705959881058285969449495136382746622','2854495385411919762116571938898990272765493246','5708990770823839524233143877797980545530986494','11417981541647679048466287755595961091061972990','22835963083295358096932575511191922182123945982','45671926166590716193865151022383844364247891966','91343852333181432387730302044767688728495783934','182687704666362864775460604089535377456991567870','365375409332725729550921208179070754913983135742','730750818665451459101842416358141509827966271486','1461501637330902918203684832716283019655932542974','2923003274661805836407369665432566039311865085950','5846006549323611672814739330865132078623730171902','11692013098647223345629478661730264157247460343806','23384026197294446691258957323460528314494920687614','46768052394588893382517914646921056628989841375230','93536104789177786765035829293842113257979682750462','187072209578355573530071658587684226515959365500926','374144419156711147060143317175368453031918731001854','748288838313422294120286634350736906063837462003710','1496577676626844588240573268701473812127674924007422','2993155353253689176481146537402947624255349848014846','5986310706507378352962293074805895248510699696029694','11972621413014756705924586149611790497021399392059390','23945242826029513411849172299223580994042798784118782','47890485652059026823698344598447161988085597568237566','95780971304118053647396689196894323976171195136475134','191561942608236107294793378393788647952342390272950270','383123885216472214589586756787577295904684780545900542','766247770432944429179173513575154591809369561091801086','1532495540865888858358347027150309183618739122183602174','3064991081731777716716694054300618367237478244367204350','6129982163463555433433388108601236734474956488734408702','12259964326927110866866776217202473468949912977468817406','24519928653854221733733552434404946937899825954937634814','49039857307708443467467104868809893875799651909875269630','98079714615416886934934209737619787751599303819750539262','196159429230833773869868419475239575503198607639501078526','392318858461667547739736838950479151006397215279002157054','784637716923335095479473677900958302012794430558004314110','1569275433846670190958947355801916604025588861116008628222','3138550867693340381917894711603833208051177722232017256446','6277101735386680763835789423207666416102355444464034512894','12554203470773361527671578846415332832204710888928069025790','25108406941546723055343157692830665664409421777856138051582','50216813883093446110686315385661331328818843555712276103166','100433627766186892221372630771322662657637687111424552206334','200867255532373784442745261542645325315275374222849104412670','401734511064747568885490523085290650630550748445698208825342','803469022129495137770981046170581301261101496891396417650686','1606938044258990275541962092341162602522202993782792835301374','3213876088517980551083924184682325205044405987565585670602750');
var
i:longint;
begin
read(i);
write(a[i]);
end.

易极feng @ 2016-10-26 19:08:52

好！
ZRainY @ 2016-10-26 19:10:56

好！
lrj124 @ 2016-11-17 11:01:18

打表大法好
Jack01 @ 2017-07-26 16:03:45

牛

0

liuyiah LV 10 @ 2016-08-09 23:09:03

#include <cstdio>
#include <cstring>
int main()
{
    int n,ans[250],len;
    scanf("%d",&n);
        memset(ans,0,sizeof(ans));
        ans[0] = 1;
        len = 1;
        for(int i=0;i < n+1;++i)
        {
            for(int j = 0;j < len;++j)
                ans[j] *= 2;
            for(int j = 0;j < len;++j)
            {
                if(ans[j] > 9)
                {
                    ans[j + 1] += ans[j]/10;
                    ans[j] %= 10;
                }
            }
            if(ans[len]) len++;
        }
        ans[0] -= 2;
        while(!ans[len]) len --;
        for(int i = len;i >= 0;i--)
            printf("%d",ans[i]);
    return 0;
}

高精度而已。。不必当真

0

tuochax LV 8 @ 2014-04-10 17:55:37

type
arrl=array of longint;
var
a:longint;
function gjd(x:longint):arrl;
var
i:longint;
begin
setlength(gjd,trunc(ln(x)/ln(10))+3);
i:=x;
gjd[0]:=0;
while i>0 do
begin
inc(gjd[0]);
gjd[gjd[0]]:=i mod 10;
i:=i div 10;
end;
end;
procedure jw(var x,y:longint);
begin
x:=x+y div 10;
y:=y mod 10;
end;
function mul(a,b:arrl):arrl;
var
i,j:longint;
begin
setlength(mul,a[0]+b[0]+1);
for i := 1 to a[0] do
for j := 1 to b[0] do
mul[i+j-1]:=mul[i+j-1]+a[i]*b[j];
for i := 1 to a[0]+b[0]-1 do jw(mul[i+1],mul[i]);
if mul[a[0]+b[0]]>0 then mul[0]:=a[0]+b[0]
else mul[0]:=a[0]+b[0]-1;
end;
function xy(x,y:longint):arrl;
begin
setlength(xy,trunc(ln(x)/ln(10)*y)+3);
if y>1 then if y mod 2=0 then exit(mul(xy(x,y div 2),xy(x,y div 2)))
else exit(mul(mul(xy(x,y div 2),xy(x,y div 2)),gjd(x)))
else exit(gjd(x));
end;
procedure gjdwrite(a:arrl);overload;
var
i:longint;
begin
i:=a[0];
while (i>1) and (a[i]=0) do dec(i);
while i>=1 do
begin
write(a[i]);
dec(i);
end;
end;
function minus(a:arrl):arrl;
begin
setlength(minus,a[0]+1);
minus:=a;
minus[1]:=minus[1]-1;
end;
begin
read(a);
gjdwrite(mul(minus(xy(2,a)),2));
end.

0

940254533 LV 8 @ 2014-01-01 12:01:09

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言共同进步

0

2013new LV 7 @ 2013-11-08 19:53:24

坑在了要用高精度上

0

哥少先队的 LV 9 @ 2013-10-02 16:15:58

好水的题- -
公式2^(n+1)-2
显然2的n+1次方第一位大于等于2
var
a:array[0..200] of integer;
n,i,j,k,x,s:longint;
begin
readln(n);
a[1]:=1;
for i:=1 to n+1 do
for j:=1 to n do begin
x:=(x div 10)+2*a[j];
a[j]:=x mod 10;
end;
a[j+1]:=x div 10;
dec(a[1],2);
i:=200;
while a[i]=0 do dec(i);
for j:=i downto 1 do write(a[j]);
end.

0

hanyi2388 LV 8 @ 2013-08-10 16:25:01

参考程序：
var a:array[0..500] of integer;
n,i,j,k,x,s:longint;
begin
readln(n);
a[1]:=1;
x:=0;
for i:=1 to n+1 do for j:=1 to n do begin
s:=a[j]*2+x;
a[j]:=s mod 10;
x:=s div 10;
end;
a[1]:=a[1]-2;
if a[1]<0 then begin
a[1]:=a[1]+10;
a[2]:=a[2]-1;
end;
i:=100;
while a[i]=0 do dec(i);
for j:=i downto 1 do write(a[j]);
end.
普及题就是水，秒杀！！

0

oimonster LV 8 @ 2013-08-08 17:08:41

公式+高精度

测试数据 #0: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 440 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 444 KiB, score = 10

程序清单：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<mem.h>
using namespace std;
int a[100];
int main(){
int i,j,n,g=0;
scanf("%d",&n);
memset(a,0,sizeof(a));
a[1]=1;
for (i=1;i<=n+1;i++)
for (j=1;j<=100;j++){
a[j]=a[j]*2+g;
g=a[j]/10;
a[j]=a[j]%10;
}
a[1]=a[1]-2;
j=100;
while (a[j]==0)j--;
for (i=j;i>=1;i--) printf("%d",a[i]);
printf("\n");
//system("PAUSE");
return 0;
}

0

丿SEX丶elope LV 8 @ 2012-11-08 21:58:38

关键是找关系式。。真水啊。。。

点这里查看程序源码+详细题解

0

liuyuanzhe05 LV 9 @ 2012-11-04 12:18:03

公式：2^(n+1)-2

单高精度乘法，减法直接减2，因为不可能出现借位情况。

const daxiao=100;

var i,n,j:longint;

ans:array[1..daxiao] of integer;

procedure che(m:integer);

var t,i:integer;

begin

t:=0;

for i:=1 to daxiao do begin

ans[i]:=ans[i]*m+t;

t:=ans[i] div 10;

ans[i]:=ans[i] mod 10;

end;

end;

begin

readln(n);

ans[1]:=1;

for i:=1 to n+1 do che(2);

ans[1]:=ans[1]-2;

for i:=daxiao downto 1 do if ans[i]0 then break;

for j:=i downto 1 do write(ans[j]);

end.

0

雨，纷飞 LV 8 @ 2012-08-03 16:10:53

点击查看代码

0

ChinaLover LV 8 @ 2012-07-24 10:12:19

好吧我承认我今天写程序把头写昏了

但最后还是过了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

var n,i,j:integer;

num:array[1..1000] of integer;

procedure es;

var k,jw,temp:integer;

begin

jw:=0;k:=1;

while num[k]=0 do inc(k);

for j:=1000 downto k-1 do

begin

temp:=num[j];

num[j]:=(num[j]*2 mod 10)+jw;

jw:=0;

if temp*2>9 then jw:=1;

end;

end;

begin

readln(n);

num[1000]:=1;

inc(n);

for i:=1 to n do

es;

j:=1;

num[1000]:=num[1000]-2;

while num[j]=0 do inc(j);

for i:=j to 1000 do write(num[i]);

end.

0

panannan LV 5 @ 2009-11-19 14:23:49

var a:array[1..2000] of longint;

　　 i,j,k,l,m,n:longint;

begin

readln(n); l:=1;

for k:=1 to n do begin inc(a[1]);

for i:=1 to l do

　　 a[i]:=a[i]*2;

for i:=1 to l-1 do begin

　　 inc(a,a[i] div 10);

　　 a[i]:=a[i] mod 10; end;

while a[l]>10 do begin

　　a[l+1]:=a[l] div 10;a[l]:=a[l] mod 10;inc(l);

　　end;

end;

for i:=l downto 1 do write(a[i]);

end

0

refly62 LV 7 @ 2009-11-04 16:27:03

找规律，我AC了

很囧的题目

program hanoihanoi;

var

a:array[0..500] of integer;

n,i,j,k,x,s:longint;

begin

readln(n);

a[1]:=1;

x:=0;

for i:=1 to n+1 do

for j:=1 to n do

begin

s:=a[j]*2+x;

a[j]:=s mod 10;

x:=s div 10;

end;

a[1]:=a[1]-2;

if a[1]

0

小治 LV 8 @ 2009-11-02 22:16:14

征服双塔！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

527971925 LV 10 @ 2009-11-02 08:44:00

我沙茶哦.....

开始一来直接丢了两行的位运算就跑....结果50分

再添了个高精反而0蛋....

才发现忘了减2.....

---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

yatacr LV 5 @ 2009-10-31 15:02:57

program ex1354;

var

prison:array[1..10000]of longint;

i,j,n,s,t,w:longint;

begin

read(n);

t:=1;

prison[1]:=1;

for i:=1 to n+1 do

begin

w:=0;

for j:=1 to t do

begin

s:=prison[j]*2+w;

prison[j]:=s mod 10;

w:=s div 10;

end;

if w>0 then begin inc(t);prison[t]:=w;end;

end;

prison[1]:=prison[1]-2;

for i:=t downto 1 do

begin

write(prison[i]);

end;

end.

题解

132 条题解

Hanoi双塔问题

信息

状态

开发

支持

题解

132 条题解

Hanoi双塔问题

信息

状态

开发

支持

还没有账户？

登录