bzoj 1002

表示我这种蒟蒻面对这种递推第一思想显然是打表啊

先贴个用来打表的暴力：

#include <cstdio>

struct node

{

    int l,r;

}p[];

bool used[];

int f[];

int n,cnt,cct;

int findf(int x)

{

    if(x==f[x])

    {

        return x;

    }

    return f[x]=findf(f[x]);

}

bool check()

{

    for(int i=;i<=n+;i++)

    {

        f[i]=i;

    }

    for(int i=;i<=cct;i++)

    {

        if(used[i])

        {

            int f1=findf(p[i].l);

            int f2=findf(p[i].r);

            f[f2]=f1;

        }

    }

    int ff=;

    for(int i=;i<=n+;i++)

    {

        int f1=findf(i);

        if(!ff)

        {

            ff=f1;

        }else if(ff!=f1)

        {

            return ;

        }

    }

    return ;

}

void dfs(int dep,int tot)

{

    if(dep==cct+)

    {

        if(tot==n)

        {

            if(check())

            {

                cnt++;

            }

        }

        return;

    }

    used[dep]=;

    dfs(dep+,tot+);

    used[dep]=;

    dfs(dep+,tot);

}

int main()

{

    scanf("%d",&n);    

    for(int i=;i<=n+;i++)

    {

        p[++cct].l=;

        p[cct].r=i;    

    }

    for(int i=;i<=n+;i++)

    {

        if(i==n+)

        {

            p[++cct].l=i;

            p[cct].r=;

        }else

        {

            p[++cct].l=i;

            p[cct].r=i+;

        }

    }

    dfs(,);

    printf("%d\n",cnt);

    return ;

}

/*

1 1

2 5

3 16

4 45

5 121

6 320

*/

实测这个打表程序是正确的（可以获得30分）

接下来是本人心路历程：

观察一下：1-1,2-5,3-16,4-45...找一下前后项吧！

观察前后项的倍数关系应该在2~3之间，那先定一个基础表达式

f[i]=2f[i-1]+...或f[i]=3f[i-1]+...

如果系数用2，发现剩下的部分长这样啊...

f[3]=2f[2]+6

f[4]=2f[3]+13

f[5]=2f[4]+31

...

好像后面的没啥规律...

那换系数用3！

f[4]=3f[3]-3

f[5]=3f[4]-14

...

好像也没啥啊...

等一下！

-3=-5+2

-14=-16+2

如果下面再写下来，应该是-43=-45+2！

这不就找出来了吗！

f[i]=3f[i-1]-f[i-2]+2!

于是敲个高精度这题就结束了...

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

struct Bignum

{

	int a[10005];

	int ilen;

}f[105],zero;

int n;

Bignum add(Bignum x)

{

	Bignum ret=x;

	ret.a[1]+=2;

	int i=1;

	while(ret.a[i]>=10)

	{

		ret.a[i+1]+=ret.a[i]/10;

		ret.a[i]%=10;

		i++;

	}

	if(ret.a[ret.ilen+1])

	{

		ret.ilen++;

	}

	return ret;

}

Bignum mul(Bignum x)

{

	Bignum ret=zero;

	for(int i=1;i<=x.ilen;i++)

	{

		ret.a[i]+=3*x.a[i];

		ret.a[i+1]+=ret.a[i]/10;

		ret.a[i]%=10;

	}

	ret.ilen=x.ilen;

	while(ret.a[ret.ilen+1])

	{

		ret.ilen++;

	}

	return ret;

}

Bignum sub(Bignum x,Bignum y)

{

	Bignum ret=zero;

	for(int i=1;i<=y.ilen;i++)

	{

		ret.a[i]+=x.a[i]-y.a[i];

		if(ret.a[i]<0)

		{

			ret.a[i]+=10;

			ret.a[i+1]--;

		}

	}

	for(int i=y.ilen+1;i<=x.ilen;i++)

	{

		ret.a[i]+=x.a[i];

	}

	ret.ilen=x.ilen;

	while(!ret.a[ret.ilen]&&ret.ilen>1)

	{

		ret.ilen--;

	}

	return ret;

}

int main()

{

	scanf("%d",&n);

	f[1].a[1]=1;

	f[1].ilen=1;

	f[2].a[1]=5;

	f[2].ilen=1;

	f[3].a[1]=6;

	f[3].a[2]=1;

	f[3].ilen=2;

	for(int i=4;i<=n;i++)

	{

		f[i]=mul(f[i-1]);

		f[i]=add(f[i]);

		f[i]=sub(f[i],f[i-2]);

	}

	for(int i=f[n].ilen;i>=1;i--)

	{

		printf("%d",f[n].a[i]);

	}

	printf("\n");

	return 0;

}

巴特西

bzoj 1002

最新文章

热门文章