20160723数据结构节alexandrali

大坑最后再填。

20160803：心情好回来填啦(5/7)

做的题目是：

poj2970

我们先每个人都不给钱qwq

然后我们发现有一位的工作时间超过了d

那么我们就从以前安排过工作的人里，a最大的，给他加上一定量的x，使得后面的这个超出di的工作者可以在di前完成任务，或者他的工作时间已经为0，则继续找剩下的当中a最大的

这个过程用堆维护，时间复杂度O(nlogn)

struct data{

    int a,b,d;

    bool operator <(const data&b)const {

        return  a<b.a;

    }

};

bool cmp(const data&a,const data&b){

    return a.d<b.d;

}

int n;data a[100005];

priority_queue<data>q;

int main(){

    n=gi;

    FOR1(i,n){

        a[i].a=gi;a[i].b=gi;a[i].d=gi;

    }

    sort(a+1,a+n+1,cmp);

    long long sum=0;

    double ans=0;

    FOR1(i,n){

        sum+=a[i].b;

        q.push(a[i]);

        while(!q.empty()&&sum>a[i].d){

            data c=q.top();q.pop();

            if(sum-c.b>a[i].d){

                ans=ans+(double)c.b/c.a;

                sum=sum-c.b;

            }

            else{

                ans=ans+(double)(sum-a[i].d)/c.a;

                c.b=c.b-sum+a[i].d;

                sum=a[i].d;

                q.push(c);

            }

        }

    }

    printf("%.2f\n",ans);

    return 0;

}

poj2796

首先由于元素非负，sum[l,r]的值随区间长度增长，单调不降

那么我们求出对于每个元素，以它为最小值的区间最左到哪里，最右到哪里即可

我们用单调栈实现，复杂度就是O(n)

int n,a[100005];

ll qzh[100005];

int pr[100005],nx[100005],ds[100005],top;

int main(){

    RI(n);

    FOR1(i,n){

        a[i]=gi;

        qzh[i]=qzh[i-1]+a[i];

    }

    FOR1(i,n){

        while(top&&a[ds[top]]>=a[i])--top;

        pr[i]=top?ds[top]:0;

        ds[++top]=i;

    }

    top=0;

    FORD(i,n,1){

        while(top&&a[ds[top]]>=a[i])--top;

        nx[i]=top?ds[top]:n+1;

        ds[++top]=i;

    }

    ll ans=0;int l=1,r=1;

    FOR1(i,n){

        ll t=(qzh[nx[i]-1]-qzh[pr[i]])*(ll)(a[i]);

        if(t>ans){

            r=nx[i]-1;l=pr[i]+1;

            ans=t;

        }

    }

    cout<<ans<<endl;cout<<l<<' '<<r;

    return 0;

}

ural 1003

考虑前缀和的奇偶性

区间和是奇数的，说明头尾的前缀和奇偶性不同区间和是偶数的，说明头尾的前缀和奇偶性相同

直接使用并查集维护这个关系，回答询问

int l,n,block;

int a[5001],b[5001],f[100006];

char s[5001][6];

int find(int x){

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

}

void uni(int a,int b){

    int p,q;

    p=find(a);

    q=find(b);

    if(q!=p)

        f[q]=p;

}

int main(){

    block=50003;

    while (scanf("%d",&l),l!=-1){

        scanf("%d",&n);

        FOR1(i,n)

            a[i]=gi,b[i]=gi,scanf("%s",s[i]);

        FOR1(i,block*2)f[i]=i;

        f[0]=1;

        int i=1;

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

            int x=(a[i]-1)%block,y=b[i]%block;

            if(s[i][0]=='e'){

                if(find(x)==find(y+block))break;

            uni(x,y);

            uni(x+block,y+block);

            }else{

                if(find(x+block)==find(y+block))break;

                uni(x,y+block);

                uni(x+block,y);

            }

        }

        printf("%d\n",i-1);

    }

}

sgu 180

逆序对裸题，有很多做法，过于简单不贴代码了

ural 1028

【题意】给定多个二维坐标，求每个点左下角的点数

树状数组

poj版需要特判重点

int c[32005];

int lowbit(int x){

    return x &(-x);

}

int sum(int i){

    int s=0;

    while(i>0){

        s=s+c[i];

        i=i-lowbit(i);

    }

    return s;

}

void update(int i,int value){

    while(i<=32005){

        c[i]=c[i]+value;

        i=i+lowbit(i);

    }

}

int level[32005];

int main(){

    int Case;

    scanf("%d",&Case);

    int x,y;

    for(int i=0;i<Case;i++){

        scanf("%d%d",&x,&y);

        int tmp=sum(++x);

        level[tmp]++;

        update(x,1);

    }

    for(int i=0;i<Case;i++)

        printf("%d\n",level[i]);

    return 0;

}

poj2944 、sgu 336

不会做

强烈推荐在vjudge做

巴特西