【2016常州一中夏令营Day7】

序列（sequence）
【题目描述】
蛤布斯有一个序列，初始为空。它依次将 1-n 插入序列，其中 i插到当前第 ai 个数的右边 (ai=0 表示插到序列最左边)。它希望你帮
它求出最终序列。
【输入数据】
第一行一个整数 n。第二行 n 个正整数 a1~an。
【输出数据】
输出一行 n 个整数表示最终序列，数与数之间用一个空格隔开。
【样例输入】
5
0 1 1 0 3
【样例输出】
4 1 3 5 2
【数据范围】
对于 30%的数据，n<=1000。
对于 70%的数据，n<=100000
对于 100%的数据，n<=1000000，0<=ai<i。

题解

从后往前插入，对于一个数 $i$ ，插入到当前第 $a_i$ 个空格即可。用线段树维护当前第 $a_i$ 个空格的位置下标。

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n;

int a[1000005],ans[1000005];

struct hh

{

    int l,r,val;

    bool flag;

};

hh lt[5000005];

void build(int root,int l,int r)

{

    int mid;

    lt[root].l=l;

    lt[root].r=r;

    if(l==r)

    {

        lt[root].val=1;

        return;

    }

    mid=(l+r)>>1;

    build(root<<1,l,mid);

    build(root<<1|1,mid+1,r);

    lt[root].val=lt[root<<1].val+lt[root<<1|1].val;

}

int query(int root,int now)

{

    int mid;

    if(lt[root].l==lt[root].r) return lt[root].l;

    if(lt[root<<1].val>=now) return query(root<<1,now);

    else return query(root<<1|1,now-lt[root<<1].val);

}

void del(int root,int pre)

{

    if(lt[root].l<=pre&&lt[root].r>=pre) lt[root].val--;

    if(lt[root].l==lt[root].r)

    {

        lt[root].flag=true;

        return;

    }

    if(lt[root<<1].l<=pre&&lt[root<<1].r>=pre) del(root<<1,pre);

    else if(lt[root<<1|1].l<=pre&&lt[root<<1|1].r>=pre) del(root<<1|1,pre);

}

int main()

{

    int i,j,pre;

    freopen("sequence.in","r",stdin);

    freopen("sequence.out","w",stdout);

    scanf("%d",&n);

    for(i=1;i<=n;i++) scanf("%d",&a[i]);

    build(1,1,n);

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

    {

        pre=query(1,a[i]+1);

        ans[pre]=i;

        del(1,pre);

    }

    for(i=1;i<=n;i++) printf("%d ",ans[i]);

    fclose(stdin);

    fclose(stdout);

    return 0;

}

背包（pack）
【题目描述】
蛤布斯有 n 个物品和一个大小为 m 的背包，每个物品有大小和价值，它希望你帮它求出背包里最多能放下多少价值的物品。
【输入数据】
第一行两个整数 n,m。接下来 n 行每行两个整数 xi，wi，表示第 i个物品的大小和价值。
【输出数据】
一行一个整数表示最大价值。
【样例输入】
5 100
95 80
4 18
3 11
99 100
2 10
【样例输出】
101
【数据范围】
对于 20%的数据，xi<=1500。
对于 30%的数据，wi<=1500。
对于 100%的数据，n<=40,0<=m<=10^18,0<=xi,wi<=10^15。

题解

折半搜索+二分查找

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int n,tn,cnt,tot;

long long m,ans=0;

struct hh

{

    long long x,w;

}a[45],q[2000005];

void dfsa(int,long long,long long);

void dfsb(int,long long,long long);

long long search(long long);

bool cmp(hh a,hh b){return a.x==b.x?a.w>b.w:a.x<b.x;}

long long maxx(long long a,long long b){return a>b?a:b;}

int main()

{

    int i,j;

    freopen("pack.in","r",stdin);

    freopen("pack.out","w",stdout);

    scanf("%d%lld",&n,&m);

    tn=n>>1;

    for(i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].w);

    dfsa(1,0,0);tot=1;

    sort(q+1,q+cnt+1,cmp);

    for(i=2;i<=cnt;i++)

        if(q[i].x!=q[i-1].x) q[++tot]=q[i];

    for(i=1;i<=tot;i++)

        if(q[i].w<q[i-1].w) q[i].w=q[i-1].w;

    dfsb(tn+1,0,0);

    printf("%lld",ans);

    fclose(stdin);

    fclose(stdout);

    return 0;

}

void dfsa(int pre,long long xx,long long ww)

{

    if(pre>tn)

    {

        q[++cnt]=(hh){xx,ww};

        return;

    }

    dfsa(pre+1,xx,ww);

    if(xx+a[pre].x<=m) dfsa(pre+1,xx+a[pre].x,ww+a[pre].w);

}

void dfsb(int pre,long long xx,long long ww)

{

    long long temp;

    if(pre>n)

    {

        temp=search(m-xx);

        ans=maxx(ans,ww+temp);

        return;

    }

    dfsb(pre+1,xx,ww);

    if(xx+a[pre].x<=m) dfsb(pre+1,xx+a[pre].x,ww+a[pre].w);

}

long long search(long long xx)

{

    int l,r,mid;

    if(xx<q[1].x) return 0;

    l=1;r=tot;

    while(l<r)

    {

        mid=l+r+1>>1;

        if(q[mid].x<=xx) l=mid;

        else r=mid-1;

    }

    return q[l].w;

}

线段树（segment）
【题目描述】
重新定义一个线段树，根结点仍然表示[1,n]，但[l,r]的左右儿子分别表示[l,k]和[k+1,r]，这里的 k 可以在[l,r)中任取。
每次访问从根结点开始，而且只有在当前结点是叶子结点时才会直接结束访问，否则一定会向下访问。
蛤布斯将对 m 个区间[ai,bi]进行访问，你需要帮他为每个结点选取合适的 k，输出每次访问的结点个数最小和。
【输入数据】
第一行两个整数 n，m，接下来 m 行每行两个整数 ai，bi。
【输出数据】
一行一个整数表示答案。
【样例输入】
6 6
1 4
2 6
3 4
3 5
2 3
5 6
【样例输出】
40
【数据范围】
对于 20%的数据，n<=50，m<=100。
对于 40%的数据，n<=200。
对于 70%的数据，n<=1000。
对于 100%的数据，n<=5000，m<=100000。

题解

$f[i,j]$ 表示结点 $[i,j]$ 的子树中被访问的最小次数， $w[i,j]$ 表示结点 $[i,j]$ 被访问的次数，即与 $[i,j]$ 相交的区间数。
f[i,j]=min{f[i,k]+f[k+1,j]}+w[i,j] (i<=k<j)
首先预处理出 w，那么这个 dp 复杂度是 O(n^3)，用四边形不等式可以优化到 O(n^2)

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m;

int l[5005],r[5005],f[5005][5005],w[5005][5005];

int main()

{

    int i,j,k,x,y;

    freopen("segment.in","r",stdin);

    freopen("segment.out","w",stdout);

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

    for(i=1;i<=m;++i)

    {

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

        l[x]++;r[y]++;

    }

    for(i=1;i<=n;++i) r[i]+=r[i-1];

    for(i=n;i>=1;i--) l[i]+=l[i+1];

    memset(f,9999999,sizeof f);

    for(i=1;i<=n;i++) f[i][i]=m-r[i-1]-l[i+1];

    for(i=1;i<=n;i++) w[i][i]=i;

    for(k=1;k<=n-1;k++)

        for(i=1;i<=n-k;i++)

        {

            for(j=w[i][i+k-1];j<=w[i+1][i+k]&&j+1<=i+k;++j)

                if(f[i][j]+f[j+1][i+k]<f[i][i+k])

                {

                    f[i][i+k]=f[i][j]+f[j+1][i+k];

                    w[i][i+k]=j;

                }

            f[i][i+k]+=(m-r[i-1]-l[i+k+1]);

        }

    printf("%d",f[1][n]);

    fclose(stdin);

    fclose(stdout);

    return 0;

}

巴特西

【2016常州一中夏令营Day7】

最新文章

热门文章