题解 - Vijos

1

!TNT! LV 8 @ 2017-05-26 20:56:55

#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>   
#include <algorithm>  
using namespace std;  
const int MAXN = 500;  
struct bign  
{  
    int len, s[MAXN];  
    bign ()  
    {  
        memset(s, 0, sizeof(s));  
        len = 1;  
    }  
    bign (int num) { *this = num; }  
    bign (const char *num) { *this = num; }  
    bign operator = (const int num)  
    {  
        char s[MAXN];  
        sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
    }  
    bign operator = (const char *num)  
    {  
        for(int i = 0; num[i] == '0'; num++) ;
        len = strlen(num);  
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';  
        return *this;  
    }  
    bign operator + (const bign &b) const
    {  
        bign c;  
        c.len = 0;  
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)  
        {  
            int x = g;  
            if(i < len) x += s[i];  
            if(i < b.len) x += b.s[i];  
            c.s[c.len++] = x % 10;  
            g = x / 10;  
        }  
        return c;  
    }  
    bign operator += (const bign &b)  
    {  
        *this = *this + b;  
        return *this;  
    }  
    void clean()  
    {  
        while(len > 1 && !s[len-1]) len--;  
    }  
    string str() const 
    {  
        string res = "";  
        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;  
        return res;  
    }  
};  
   
istream& operator >> (istream &in, bign &x)  
{  
    string s;  
    in >> s;  
    x = s.c_str();  
    return in;  
}  

ostream& operator << (ostream &out, const bign &x)  
{  
    out << x.str();  
    return out;  
}  
int main(){
    bign f[3]; int n; cin>>n;
    f[1]=1; f[2]=2;
    for(int i=3;i<=n;++i) f[i%3]=f[(i-1)%3]+f[(i-2)%3]+f[(i-2)%3]+1;
    cout<<f[n%3];
}

1

notblack LV 10 @ 2009-09-23 12:58:29

f[n]=2*f[n-2]+f[n-1]+1

高精加法

1

zhh1993 LV 10 @ 2009-08-13 08:16:10

f[n]表示将n连环拿下来的步数，则有

f[n]=2*f[n-2]+f[n-1]+1

(n连环的最优解按题意自然是先把前n-2环拿下，再将第n环拿下，然后将前n-2环放回来，然后将前n-1环一起拿去，所以便有了这个式子)

本题需要高精，所以可以用滚动数组a,b分别记录f[n-2]和f[n-1]的进行循环计算.....

0

刷题者 LV 8 @ 2013-10-05 20:27:29

###**JAVA万岁**

import java.util.Scanner;
import java.math.BigInteger;

public class Main
{
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
int n=cin.nextInt();
BigInteger m=new BigInteger("2");
BigInteger t=new BigInteger("2");
m=m.pow(n+1);
t=t.pow(1-n%2);
m=m.subtract(t);
try
{
m=m.divide(BigInteger.valueOf(3));
}
catch(ArithmeticException e)
{
System.out.println("nani");
}
System.out.println(m);
}
}

0

夜未央 LV 10 @ 2013-10-02 16:11:55

测试数据 #0: Accepted, time = 0 ms, mem = 8652 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8652 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 8652 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 8652 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
Accepted, time = 0 ms, mem = 8652 KiB, score = 100

const
modnum=10;
type
arraytype=array[1..1000000] of longint;
var
x1,x2,x3:arraytype;
i,j,l1,l2,l3,n:longint;
s1,s2:ansistring;

procedure c1(var a,b,c:arraytype; var a1,b1,c1:longint);
var
i,j,k,x:longint;
begin
i:=1; x:=0;
while (i<=a1)or(i<=b1) do
begin
c[i]:=a[i]+b[i]+x;
x:=c[i] div modnum;
c[i]:=c[i] mod modnum;
inc(i);
end;
if x>0 then begin
c1:=i;
c[i]:=x;
end
else c1:=i-1;
end;

procedure cc(var a:arraytype; var a1:longint; k:longint);
var
i,j,x:longint;
begin
x:=0;
for i:=1 to a1 do
begin
a[i]:=a[i]*k+x;
x:=a[i] div modnum;
a[i]:=a[i] mod modnum;
end;
while x>0 do
begin
inc(a1);
a[a1]:=x mod modnum;
x:=x div modnum;
end;
end;

begin
readln(n);
if (n=1)or(n=2)then
begin
writeln(n);
halt;
end;
l1:=1;
x1[1]:=1;
l2:=1;
x2[1]:=2;
i:=3;
repeat
cc(x1,l1,2);
inc(x1[1],1);
c1(x1,x2,x1,l1,l2,l1);
if i=n then
begin
for j:=l1 downto 1 do
write(x1[j]);
halt;
end;
inc(i);
cc(x2,l2,2);
inc(x2[1],1);
c1(x2,x1,x2,l2,l1,l2);
if i=n then
begin
for j:=l2 downto 1 do
write(x2[j]);
halt;
end;
inc(i);
until false;
end.

0

talent123 LV 9 @ 2009-11-06 17:22:27

第149题...

0

在水一方 LV 8 @ 2009-10-29 20:01:36

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

谢谢下面一哥们的提醒

当N为800时结果有两百多位！

0

cyr LV 9 @ 2009-10-12 21:23:22

~~100 AC 留念~~

~~奋斗ing也是一种幸福~~

~~O(∩_∩)O~~

0

zouxiang2 LV 7 @ 2009-10-11 09:34:32

高精+公式=AC

0

lgxcgd LV 10 @ 2009-10-07 17:06:15

水

F：=F+F+F+1

勿忘高精加

0

jh8180129 LV 8 @ 2009-09-19 08:35:42

公式：f=（a^(n+1)-2）/3;(n为偶数)

f=（a^(n+1)-1）/3;(n为奇数)

再加高精

0

upvc LV 6 @ 2009-08-23 21:35:13

额

0

李肥888 LV 10 @ 2009-08-19 21:49:27

这题高精不用压缩位数也能秒杀。。。

0

嘻哈ぽET LV 8 @ 2009-08-13 15:08:25

啥意思嘛？

看不懂啊。。

0

littlewhite LV 8 @ 2009-08-06 10:37:18

var

n,l,i:longint;

f:array[1..500] of integer;

procedure run(a:longint);

var

i,j:longint;

begin

for i:=1 to l do

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

if a mod 2=1 then inc(f[1]);

for i:=1 to l do

if f[i]>9 then

begin

inc(f);

dec(f[i],10);

end;

if f>0 then l:=l+1;

end;

begin

readln(n);

f[1]:=1;

l:=1;

for i:=2 to n do

run(i);

for i:=l downto 1 do

write(f[i]);

end.

还是用的下面某牛写的递推公式

先乘2 若当前数为奇则末位加1

0

aylcx LV 7 @ 2009-07-21 11:34:56

program lt;

var s: array [1..1000] of longint;

a,b,c,d,i,j,k,l,m,n: longint;

begin for i:=1 to 1000 do s[i]:=0;

readln(a);

s[1]:=1;

l:=1;

for b:=2 to a do

begin

for i:=1 to l do

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

s[1]:=s[1]+b mod 2;

for i := 1 to l do

begin

s:=s+s[i] div 10;

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

end;

if s[l+1]>0 then l:=l+1;

end;

for i:=l downto 1 do

write(s[i]);

end.

0

飓风音速 LV 10 @ 2009-07-19 11:39:07

f[i]=f*2+f+1

0

尖端才子 LV 10 @ 2009-07-05 18:39:03

囧……还有公式……我可写的递推+高精啊……

f[n]=f[n-2]*2+f[n-1]+1；

ORZ……怎么推得公式？

不过这题确实水……

{————————————————————————————————————}

type

arr=array[0..10000]of integer;

var

n,i:integer;

a,b,c:arr;

procedure suan;

var

i:integer;

begin

if a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0];

for i:=1 to c[0] do

c[i]:=a[i]*2+b[i];

inc(c[1]);

for i:=1 to c[0] do

begin

c:=c+c[i] div 10;

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

end;

while c[c[0]+1]0 do

begin

inc(c[0]);

c[c[0]+1]:=c[c[0]+1]+c[c[0]] div 10;

c[c[0]]:=c[c[0]] mod 10;

end;

end;

begin

readln(n);

if n=1 then begin write(1); halt; end;

if n=2 then begin write(2); halt; end;

a[1]:=1;

b[1]:=2;

a[0]:=1;

b[0]:=1;

for i:=3 to n do

begin

fillchar(c,sizeof(c),0);

suan;

a:=b;

b:=c;

end;

for i:=c[0] downto 1 do write(c[i]);

end.

0

gsrq LV 10 @ 2009-06-29 09:03:45

var

n,i,k,j:integer;

a:array [1..10000] of integer;

begin

read(n);

a[1]:=1;

k:=1;

for j:=1 to n+1 do

begin

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

for i:=2 to k do

begin

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

a[i]:=a[i]+a div 10;

a:=a mod 10;

end;

while a[k]>=10 do

begin

k:=k+1;

a[k]:=a[k-1] div 10;

a[k-1]:=a[k-1] mod 10;

end;

end;

j:=0;

for i:=k downto 1 do

begin

a[i]:=a[i]+j*10;

j:=a[i] mod 3;

a[i]:=a[i] div 3;

end;

while a[k]=0 do k:=k-1;

for i:=k downto 1 do

write(a[i]);

end.

0

200853349 LV 8 @ 2009-06-10 19:39:29

真是脑子不好使了。。。

写高精的时候小心在每一位都+1了。。

调了半天又。。

题解

60 条题解

宁静与九连环

信息

状态

开发

支持

题解

60 条题解

宁静与九连环

信息

状态

开发

支持

还没有账户？

登录