bestcoder#61 div2

1001(hdu5522) Numbers
签到题



#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[110];
bool judge(int x,int y,int z)
{
    if((x+y==z) || (x+z==y) || (y+z==x)) return 1;
    return 0;
}
int main()
{
    int i,j,k;
    int t;
    int n;
    while(~scanf("%d",&n))
    {
        bool flag=0;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                for(k=j+1;k<=n;k++)
                {
                    if(judge(a[i],a[j],a[k])) {flag=1;break;}
                }
                if(flag) break;
            }
            if(flag) break;
        }
        printf("%s\n",flag?"YES":"NO");
    }


    return 0;
}

1002(hdu5523) Game
简单题,考虑s和t的位置,分情况讨论即可



#include<stdio.h>
#include<string.h>
int main()
{
    int i,j;
    int n,s,t;
    while(~scanf("%d%d%d",&n,&s,&t))
    {
        if((s==t) && n>1){printf("-1\n");continue;}
        if(((s==1) && (t==n))||((s==n) && (t==1))){printf("0\n");continue;}
        if(((s==1)||(s==n)) && t!=1 && t!=n)
        {
            printf("1\n");continue;
        }
        if(((t==1)||(t==n)) && s!=1 && s!=n)
        {
            if((s-t==1) || (t-s==1)) {printf("1\n");continue;}
            printf("2\n");continue;
        }
        if((s-t==1) || (t-s==1))
            printf("1\n");
        else
            printf("2\n");
    }


    return 0;
}

1003(hdu5524) Subtrees
我看了下别人的代码,似乎有很简单的做法。。但是我还没研究。我说下自己的解法
问题是问n个结点的完全二叉树有多少种结点个数不同的子树。n是long long 范围
可以递归来做,由于是完全二叉树,所以以根结点的两个儿子为根的两棵子树一定有一棵是满二叉树,而满二叉树有log2(结点总数)种结点数不同的子树,对于另一棵子树,我们递归求解。
这样。递归次数是树高h(=log2(n)),每次递归都要往结果set中加log2(n)个数据,set加一次数据复杂度log2级别,由于set中数据总数很少,所以看成常数。所以复杂度大概O(lg(n)^2)
易错点:算树高h的时候,浮点函数log()精度不够,要用二分去求树高。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
set<ll> num;
ll pow2(ll k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            k--;
            ans*=p;
            continue;
        }
        else
        {
            k/=2;
            p*=p;
        }
    }
    return ans;
}
ll bs(ll n)
{
    if(!n) return 0;
    ll l=0,r=63;
    while(l<=r)
    {
        ll m=l+((r-l)>>1);
        if((pow2(m)-1>=n) && (pow2(m-1)<n)) return m;
        if(pow2(m)-1<n) l=m+1;
        else r=m-1;
    }
    return l;
}
void f(ll n)
{
    ll i;
    if(!n) return;
    if(n==1) {num.insert(1);return;}
    ll l,r;
    ll h=bs(n);
    ll non_ye=pow2(h-1)-1;
    ll ye=n-non_ye;
    ll xh=pow2(h-2);
    num.insert(n);
    if(ye<=xh)
    {
        l=(non_ye-1)/2+ye;
        r=(non_ye-1)/2;
        ll hr=bs(r);
        for(i=1;i<=hr;i++)
            num.insert(pow2(i)-1);
        f(l);
    }
    else
    {
        l=(non_ye-1)/2+xh;
        r=n-1-l;
        ll hl=bs(l);
        for(i=1;i<=hl;i++)
            num.insert(pow2(i)-1);
        f(r);

    }
    return;
}
int main()
{
    int i,j;
    ll n;
    while(~scanf("%I64d",&n))
    {
        if(!num.empty()) num.clear();
        f(n);
        printf("%I64d\n",(ll)num.size());
    }


    return 0;
}

1004(hdu5525) Product
不知道为什么TLE,按道理不应该啊。。看了下官方解答,基本思路相同,只是我没用费马小定理。有时间再回来改~
待修改

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll N=100010;
const ll mod=1000000007LL;
ll pr[N],p[N/10];
ll pi[N][20],ki[N][20];
ll cnt,lp;
void gp()
{
	for(int i=2;i<N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	ll num=n;
	memset(ki[num],0,sizeof(ki[num]));
	while(n!=1)
	{
		ll t=pr[n];
        pi[num][++cnt]=t;
        ki[num][cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[num][cnt]++;
        }
	}
	pi[num][0]=cnt;
	return;
}
ll ret;
ll pow(ll p,ll k)
{
    ll ans=1;
    while(k)
    {
        if(k%2) {k--;ans=(ans*p)%mod;}
        k/=2;
        p=(p*p)%mod;
    }
    return ans;
}
ll n,a[100000+10],b[100000+10];
ll zyz[20],cc[20];
void scan(ll &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    ll i,j;
    gp();
    for(i=2;i<=100000;i++) fenjie(i);
    /*debug
    for(i=2;i<=100000;i++)
    {
        printf("%d的约数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",pi[i][j]);
        printf("\n");
        printf("%d的次数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",ki[i][j]);
        printf("\n");
    }
    */
    while(~scanf("%I64d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        memset(b,0,sizeof(ll)*(n+2));
        ret=1;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=pi[i][0];j++)
                b[pi[i][j]]+=ki[i][j]*a[i];
        }
        ll cn=0;
        for(i=2;i<=n;i++)
        {
            if(!b[i]) continue;
            zyz[++cn]=i;
            cc[cn]=b[i];
        }
        for(i=1;i<=cn;i++)
        {
            ll tmp=pow(zyz[i],cc[i]*(cc[i]+1)/2);
            for(j=1;j<=cn;j++)
            {
                if(i==j) continue;
                tmp=pow(tmp,1+cc[j]);
            }
            ret=(ret*tmp)%mod;
        }
        printf("%I64d\n",ret);



    }
    return 0;
}