HLOJ-DAY 7

Posted on By 张, 高畅 HLOJ-DAY 7无评论

什么已经一周了吗？

什么今天为什么是DP？

数据结构不会还可以水一水。

DP不会可真的是要命。

所以先把数据结构再处理一下吧。

[G]

原题

不是哪个小朋友能喝 10^{18} 升的果汁？

饮料仙人是吧

首先如果这题只有一个询问，是很显然的。我们只需要二分答案，然后暴力就可以了。

但是对于多组询问，我们就只能整体二分/想办法优化暴力过程。

由于整体二分后仍然要使用线段树/multiset，所以我们直接选择第二种方案。

我们考虑将美味度可持久化做一棵主席树，以价格为下标。

寻找答案的过程，事实上就是在主席树上二分。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+5;
typedef long long LL;
int n,m,tot;
int root[N];
struct J
{
    int d,p,l;
}q[N];
int cmp(J a,J b){return a.d<b.d;}
struct node
{
    int ls,rs;
    LL sum,w;
}tr[N<<5];
void pushup(int u)
{
    tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum;
    tr[u].w=tr[tr[u].ls].w+tr[tr[u].rs].w;
}
void modify(int root,int &u,int l,int r,int x,LL s,LL w)
{
    tr[u=++tot]=tr[root];
    if(l==r)
    {
        tr[u].sum+=s;
        tr[u].w+=w;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(tr[root].ls,tr[u].ls,l,mid,x,s,w);
    else modify(tr[root].rs,tr[u].rs,mid+1,r,x,s,w);
    pushup(u);
}
LL query(int u,int l,int r,LL s)
{
    if(l==r)return 1LL*s*l;
    int mid=l+r>>1;
    if(s<=tr[tr[u].ls].sum)return query(tr[u].ls,l,mid,s);
    else return tr[tr[u].ls].w+query(tr[u].rs,mid+1,r,s-tr[tr[u].ls].sum);
}
int check(int D,LL P,LL s)
{
    return (s<=tr[root[D]].sum&&query(root[D],0,M,s)<=P);
}
void work()
{
    LL G,L;
    scanf("%lld%lld",&G,&L);
    int l=0,r=n;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid,G,L))l=mid;
        else r=mid-1;
    }
    printf("%d\n",(!l?-1:q[l].d));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&q[i].d,&q[i].p,&q[i].l);
    sort(q+1,q+n+1,cmp);
    for(int i=n;i;i--)modify(root[i+1],root[i],0,M,q[i].p,1LL*q[i].l,1LL*q[i].p*q[i].l);
    while(m--)work();
    return 0;
}

然后我们DP吧。

[A]

没有原题。
题目描述：

马路上一共有 n 大株青草，每株青草所在的位置坐标为 pos_i，Kano 一开始在坐标 x 处，每分钟可以向前或向后移动一个单位距离。不过，青草太新鲜了，每株青草每分钟都会损失一单位的青草量。请你告诉他该怎样来回跑动，才能在损失最小的情况下收集完这条路上所有的青草。

非常好的区间DP，使我的大脑旋转。
由于收集不需要时间，因此所采的草是一个区间。
设 f_{l,r,0/1} 代表采完 [l,r] 的草后，来到左端点/右端点。
注意计算时需要整体计算损耗值。
然后愉快的DP。
CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1005,INF=0x3f3f3f3f;
int n,X,a[N],f[N][N][2];
vector<int>pos;
int get(int l,int r){return abs(pos[r]-pos[l]);}
int main()
{
    memset(f,0x3f,sizeof f);
    scanf("%d%d",&n,&X);
    pos.push_back(X);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        pos.push_back(x);
    }
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    n=pos.size();
    int t=lower_bound(pos.begin(),pos.end(),X)-pos.begin();
    f[t][t][0]=f[t][t][1]=0;
    for(int k=1;k<=n;k++)
    {
        for(int l=0;l+k-1<n;l++)
        {
            int r=l+k-1;
            if(f[l][r][0]<INF)
            {
                if(l!=0)f[l-1][r][0]=min(f[l-1][r][0],f[l][r][0]+get(l-1,l)*(n-k));
                if(r!=n-1)f[l][r+1][1]=min(f[l][r+1][1],f[l][r][0]+get(l,r+1)*(n-k));
            }
            if(f[l][r][1]<INF)
            {
                if(l!=0)f[l-1][r][0]=min(f[l-1][r][0],f[l][r][1]+get(l-1,r)*(n-k));
                if(r!=n-1)f[l][r+1][1]=min(f[l][r+1][1],f[l][r][1]+get(r,r+1)*(n-k));
            }
        }
    }
    printf("%lld",min(f[0][n-1][0],f[0][n-1][1]));
    return 0;
}

[B]/[C]

原题/原题
两题实际上是一题。
由置换的性质，实际上就是求正整数 n 拆分使拆分的 lcm=k，sum \leq n
于是我们质数筛一下，然后滚动数组滚掉一维，就可以了。
CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
int primes[N],st[N],cnt;
typedef long long LL;
LL f[N];
int main()
{
    scanf("%d",&n);
    if(n==1)
    {
        puts("1");
        return 0;
    }
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
    f[0]=1;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=n;j>=primes[i];j--)
        {
            for(int t=primes[i];t<=j;t*=primes[i])f[j]+=f[j-t];
        }
    }
    LL res=1;
    for(int i=1;i<=n;i++)res+=f[i];
    printf("%lld\n",res);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,mod;
int primes[N],st[N],cnt;
typedef long long LL;
LL f[N];
int main()
{
    scanf("%d%d",&n,&mod);
    if(n==1)
    {
        puts("1");
        return 0;
    }
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
    f[0]=1;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=n;j>=primes[i];j--)
        {
            for(int t=primes[i];t<=j;t*=primes[i])f[j]=(f[j]+(1LL*f[j-t]*t)%mod)%mod;
        }
    }
    LL res=1;
    for(int i=1;i<=n;i++)res=(res+f[i])%mod;
    printf("%lld\n",res);
    return 0;
}

[D]

原题
考虑对每一个二进制位进行DP（状压DP）
由于直接DP有一些困难，所以我们只需要统计 cnt，在最后计算答案。
欧拉函数可以使用质数筛求取。

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
typedef long long LL;
const LL mod=1e9+7;
int n,m,Max,a[N];
int primes[N],st[N];
LL phi[N],f[N],b[N];
void init(int n)
{
    phi[1]=1;
    int cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=1LL*(i-1);
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=(1LL*phi[i]*primes[j])%mod;
                break;
            }
            phi[primes[j]*i]=1LL*phi[i]*(primes[j]-1)%mod;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        Max=max(Max,x);
        a[x]++;
    }
    while((1<<m)<=Max)m++;
    init(1<<m);
    b[0]=0;
    f[0]=1LL;
    for(int i=1;i<(1<<m);i++)
    {
        b[i]=b[i>>1]<<1|1;
        if(a[i])
        {
            int S=b[i]^i;
            for(int state=S;;state=(state-1)&S)
            {
                f[state|i]=(f[state|i]+(1LL*f[state]*a[i]%mod))%mod;
                if(!state)break;
            }
        }
    }
    LL res=0;
    for(int i=0;i<(1<<m);i++)res=(res+(1LL*f[i]*phi[i+1])%mod)%mod;
    for(int i=0;i<a[0];i++)res=(res<<1)%mod;
    printf("%lld",res);
    return 0;
}
训练日志

发表回复