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
做不出来,看了题解还没完全清楚。。

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxn*2];
int head[maxn],cnt;
bool visit[maxn];
int n,m,num;
int c[maxn],d[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
typedef struct Node{
    int begin,end;
}Node;
Node node[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);

    }
    node[cur].end=num;
    return;
}
typedef struct Q{
    int l,r,id,count,g;
}Q;
Q q[maxn];
int cn[maxn],ans[maxn];
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
/**
int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[id];
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
**/
//树状数组部分
int cc[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add2(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=cc[i];
	return sum;
}
//区间询问转移
void del(int x)
{
    if(cn[d[x]]) {add2(cn[d[x]],-1);cn[d[x]]--;}

    if(cn[d[x]]) add2(cn[d[x]],1);
}
void insert(int x)
{
    if(cn[d[x]]) add2(cn[d[x]],-1);
    cn[d[x]]++;
    if(cn[d[x]]) add2(cn[d[x]],1);
}

void scan(int &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()
{
    int i,j;
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(cn,0,sizeof(cn));
        //memset(sum,0,sizeof(sum));
        memset(cc,0,sizeof(cc));
        for(i=1;i<=n;i++) scan(c[i]);
        for(i=1;i<=n-1;i++) {scan(a);scan(b);add(a,b);}
        dfs(1);
        for(i=1;i<=n;i++) d[node[i].begin]=c[i];
        int x,y;
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=m;i++)
        {
            scan(x);scan(y);
            q[i].l=node[x].begin;
            q[i].r=node[x].end;
            q[i].id=i;
            q[i].count=y;
            q[i].g=q[i].l/len+1;
        }
        sort(q+1,q+1+m,cmp);
        int curl=0,curr=0;
        for(i=1;i<=m;i++)
        {
            int l=q[i].l,r=q[i].r;
            while(curr<r)
            {
                curr++;
                insert(curr);
            }
            while(curr>r)
            {
                del(curr);
                curr--;
            }
            while(curl<l)
            {
                if(curl) del(curl);
                curl++;
            }
            while(curl>l)
            {
                curl--;
                insert(curl);
            }
            if(q[i].count>n) ans[q[i].id]=0;
            else ans[q[i].id]=getsum(n)-getsum(q[i].count-1);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}
/*
10 1
82 48 59 48 32 83 34 46 47 79
2 1
3 1
4 3
5 4
6 1
7 2
8 3
9 2
10 2
4 1
*/