bestcoder#64 div1

还是做出两题。。
1001(hdu5586) Sum
题意:给出n个数,给出函数f(x),现在可以对连续的一段区间的数使用f(x)转换,也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[],得到数组c。对c[]求最大子串和,这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的,那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

#include<stdio.h>
#include<string.h>
int n;
int a[100010],dp[100010];
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            a[i]=(1890*a[i]+143)%10007-a[i];
        }
        dp[1]=a[1];
        int ans=dp[1];
        for(i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]>0?dp[i-1]+a[i]:a[i]);
            if(dp[i]>ans) ans=dp[i];
        }
        if(ans>0) sum+=ans;
        printf("%d\n",sum);
    }


    return 0;
}

1002(hdu5587) Array
题意:第一次操作,数列为{1}。总共做一百次操作,每次都是在原先数列末尾增加一个0,并复制原数列增加在0后面。再将新增加的数全部加1.
给出一系列的m,表示求前m个数之和。m<=10^16
第一次:1
第二次:1 1 2
第三次:1 1 2 1 2 2 3
……
解法:因为题意是递推的,比较容易想到用递归去解。对于给定的m,我们可以二分求出最少几次操作可以使数列长度达到m,设为num.设num次操作得到的数列长度为c[num],数列和为s[num].那么前c[num-1]个数的和就是s[num-1],剩余x-c[num-1]个数可以递归解决(设剩余tmp个数,那么转化为求前(tmp-1)个数的和+tmp-1+1)

#include<stdio.h>
#include<string.h>
typedef long long ll;
int t;
ll m;
ll c[110],s[110];
int bs(ll x)
{
    int l=1,r=63;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(c[m]==x) return m;
        if(x>c[m]) l=m+1;
        else r=m-1;
    }
    return l;
}
ll f(ll x)
{
    int num=bs(x);
    //printf("num:%d\n",num);
    if(num==1) return 1;
    if(c[num]==x) return s[num];
    ll tmp=x-c[num-1];
    if(tmp==1) return s[num-1]+1;
    return s[num-1]+1+f(tmp-1)+tmp-1;
}
int main()
{
    int i,j;
    c[1]=1;
    for(i=2;i<=100;i++) c[i]=2*c[i-1]+1;
    s[1]=1;
    for(i=2;i<=100;i++) s[i]=2*s[i-1]+1+c[i-1];
    //for(i=1;i<=100;i++) printf("c[%d]:%I64d\n",i,c[i]);
    //printf("\n");
    //for(i=1;i<=100;i++) printf("s[%d]:%I64d\n",i,s[i]);
    //printf("\n");
    scanf("%d",&t);
    while(t–)
    {
        scanf("%I64d",&m);
        ll ans=f(m);
        printf("%I64d\n",ans);


    }
    return 0;
}

bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}

int n,k;
BigNum dp[110][110];
int a[110];
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) dp[i][1]=1;
        for(j=2;j<=k;j++)
            for(i=1;i<=n;i++)
                for(t=1;t<=i-1;t++)
                    if(a[i]>a[t]) dp[i][j]=dp[i][j]+dp[t][j-1];
        BigNum ans=0;
        for(i=1;i<=n;i++) ans=ans+dp[i][k];
        cout<<ans<<endl;


    }
    return 0;
}

1002(hdu5569) matrix
也是比较简单的dp题,转移方程容易想到,具体见代码。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n,m;
int a[1010][1010];
int dp[1010][1010];
const int inf=0x3f3f3f3f;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;

}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        dp[1][2]=a[1][1]*a[1][2];
        dp[2][1]=a[1][1]*a[2][1];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i==1) && (j==2)) continue;
                if((i==2) && (j==1)) continue;
                if((i+j)%2==0) continue;
                int tmp1=-1,tmp2=-1,tmp=0;
                if(judge(i,j-1))
                {
                    tmp1=a[i][j]*a[i][j-1];
                    tmp=inf;
                    if(judge(i,j-2)) tmp=dp[i][j-2];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp1+=tmp;
                }
                if(judge(i-1,j))
                {
                    tmp2=a[i][j]*a[i-1][j];
                    tmp=inf;
                    if(judge(i-2,j)) tmp=dp[i-2][j];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp2+=tmp;
                }
                if((tmp1==-1) || (tmp2==-1)) dp[i][j]=max(tmp1,tmp2);
                else dp[i][j]=min(tmp1,tmp2);
            }
        printf("%d\n",dp[n][m]);

    }


    return 0;
}

1003 balls
做不出来,看了题解还没完全清楚。。

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;
}