HZOI20190803 A，C题

题目链接：https://www.cnblogs.com/Juve/articles/11295333.html

A：

考场上只有70分。。。

发现几个性质：特殊性质1：在两条链上，看它是fib第几项，同为奇数项或偶数项就输出小的，否则输出1

特殊性质2：a==b，输出a，否则输出1

你就70啦：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cmath>

#define MAXN 300005

#define int long long

#define re register

using namespace std;

int m,anc[16][16]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,1,2,1,1,2,1,2,1,1,2,1,1,2,1,2},{0,1,1,3,1,1,1,1,3,1,1,3,1,1,1,1},{0,1,1,1,4,1,1,1,1,1,1,1,4,1,1,1},{0,1,2,1,1,5,1,2,1,1,2,1,1,5,1,2},{0,1,1,1,1,1,6,1,1,1,1,1,1,1,1,1},{0,1,2,1,1,2,1,7,1,1,2,1,1,2,1,2},{0,1,1,3,1,1,1,1,8,1,1,3,1,1,1,1},{0,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1},{0,1,2,1,1,2,1,2,1,1,10,1,1,2,1,2},{0,1,1,3,1,1,1,1,3,1,1,11,1,1,1,1},{0,1,1,1,4,1,1,1,1,1,1,1,12,1,1,1},{0,1,2,1,1,5,1,2,1,1,2,1,1,13,1,2},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,14,1},{0,1,2,1,1,2,1,2,1,1,2,1,1,2,1}};

int fib[65];

signed main(){

	scanf("%lld",&m);

	if(m<=12){

		for(re int i=1,a,b;i<=m;i++){

			scanf("%lld%lld",&a,&b);

			printf("%lld\n",anc[a][b]);

		}

		return 0;

	}

	fib[0]=fib[1]=1;

	for(re int i=2;i<=60;i++){

		fib[i]=fib[i-1]+fib[i-2];

		//cout<<fib[i]<<endl;

		//if(fib[i]>1e12){

		//	cout<<i<<endl;

		//	break;

		//}

	}

	for(re int i=1,a,b;i<=m;i++){

		scanf("%lld%lld",&a,&b);

		if(a==b) printf("%lld\n",a);

		else if(abs(a-b)==1) puts("1");

		else{

			re int aa=0,bb=0;

			for(re int j=1;j<=60;j++){

				if(fib[j]==a){

					aa=j;

				}

				if(fib[j]==b){

					bb=j;

				}

				if(aa*bb!=0) break;

			}

			if((aa&1)==(bb&1)){

				printf("%lld\n",fib[min(aa,bb)]);

			}else puts("1");

		}

	}

	return 0;

}

然而。。。

打正解：

100 分做法：我们来研究一下这个神秘的力量：依次写下兔子们的标号和他们父亲（从 2 开始）： 1 1 1 2 1 2 3 1 2 3 4 5 … 发现其实一定是许多连续段的从 1 开始的序列组合到一起，每段长度依次是斐波那契数列里面的每一项。

于是我们发现，对于$fib(i)<=x<=fib(i+1),father(x)=x-fib(i)$

所以我们可以像lca一样，一个一个向上跳

因为$fib(60)>1e12$，所以复杂度可以接受

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cmath>

#define ll long long

#define re register

using namespace std;

ll m,fib[];

void get_lca(ll a,ll b){

    if(a<b) swap(a,b);

    if(a==b){

        printf("%lld\n",a);

        return ;

    }

    ll aa=lower_bound(fib+,fib++,a)-fib;

    get_lca(b,a-fib[aa-]);

}

signed main(){

    scanf("%lld",&m);

    fib[]=fib[]=;

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

        fib[i]=fib[i-]+fib[i-];

    for(ll i=,a,b;i<=m;i++){

        scanf("%lld%lld",&a,&b);

        get_lca(a,b);

    }

    return ;

}

留坑

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<stack>

#define MAXN 131075

#define MAXM 500005

#define re register

using namespace std;

int n,k,a[MAXN],mx=0,v[MAXM],ans=1,x,y,enemy[MAXM];

bool is_sq[MAXM];

stack<int>sta;

int fa[MAXN];

int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

signed main(){

	scanf("%d%d",&n,&k);

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

		scanf("%d",&a[i]);

		mx=max(mx,a[i]);

	}

	mx=sqrt(2*mx);

	for(int i=2;i<=512;i++)

		is_sq[i*i]=1;

	if(k==1){

        for(int i=n;i>=1;i--){

            for(int j=mx;j>=2&&j*j>a[i];j--)

                if(v[j*j-a[i]]==ans){

                    sta.push(i);

                    ans++;

                    break;

                }

            v[a[i]]=ans;

        }

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

        while(!sta.empty()){

			printf("%d ",sta.top());

			sta.pop();

		}

        puts("");

        return 0;

    }

	for(int i=1;i<=MAXN-3;i++)

		fa[i]=i;

	for(int i=n;i>=1;i--){

        for(int j=mx;j>=2&&j*j>a[i];j--){

            if(v[j*j-a[i]]==sta.size()+1){

                int p=j*j-a[i];

                if(a[i]==p){

                    if(enemy[a[i]]){

                        for(int t=i;t<=(sta.empty()?n:sta.top());t++)

							fa[a[t]]=a[t],enemy[a[t]]=0;

						sta.push(i);

                        break;

                    }else enemy[a[i]]=p;

                }else{

                    if((find(a[i])==find(p)&&a[i]!=p)||enemy[p]==p){

                        for(int t=i;t<=(sta.empty()?n:sta.top());t++)

							fa[a[t]]=a[t],enemy[a[t]]=0;

						sta.push(i);

                        break;

                    }

                    if(enemy[a[i]]){

                        x=find(enemy[a[i]]),y=find(p);

                        fa[x]=y;

                    }else enemy[a[i]]=p;

                    if(enemy[p]){

                        x=find(a[i]),y=find(enemy[p]);

                        fa[x]=y;

                    }else enemy[p]=a[i];

                }

            }

		}

        v[a[i]]=sta.size()+1;

    }

    printf("%d\n",sta.size()+1);

	while(!sta.empty()){

		printf("%d ",sta.top());

		sta.pop();

	}

    puts("");

	return 0;

}

巴特西

HZOI20190803 A，C题

最新文章

热门文章