解题报告 P1759 通天之潜水

题目内容

P1759

在猴王的帮助下,小 A 终于走出了这篇荒山,却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船,但好在小 A 有 n 个潜水工具。由于他还要背重重的背包,所以他只能背 m 重的工具,又因为他的力气并不是无限的,河却很宽,所以他只能背有 v 阻力的工具。但是这条河下有非常重要的数据,所以他希望能够停留的时间最久。于是他找到了你,让你告诉他方案。

大意:0-1 背包,两层限制条件,要求输出方案

解题思路

乍一看,是一个二维的背包问题,还要求输出他的方案,天哪好难,但实际上这题并不难(毕竟是黄题)。思路和榨取 kkksc03 那道题基本类似,唯一不同的是需要记录方案,而且要求字典序尽量的小

回忆:在进行前面的背包问题的时候,是如何判断选与不选的:f[j-w[i]]+c[i] 说明是要选这个物品,而我们现在既然要记录方案,那就只需要在当 f[j-w[i]]+c[i] 更大时记录一下,这个容量下的第 x 个物品被选择了,然后最后输出的时候递推回去就可以了。

这个问题里面,令 g[i][m][v]i 个物品在当前重量为 m,阻力为 v 的时候有没有选,然后最后判断的时候倒序递推,正序输出。

int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])//如果当前状态选了
        {
            ans[cnt++]=i;//记录
            m-=a[i];//回溯上一个状态的 m
            v-=b[i];//回溯上一个状态的 v
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);

还有一点要注意的是需要输出字典序尽可能小的物品,所以在 if(f[j-a[i]][k-b[i]]+c[i]>f[j][k]) (判断选不选物品)的时候必须是大于号,这样才能保证尽量选前面的物品。

#include <cstdio>

int n,m,v,a[105],b[105],c[105],f[205][205];//f 用来进行 dp
bool g[105][205][205];//存储物品的选择
int ans[105];

int main()
{
    scanf("%d %d %d",&m,&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",a+i,b+i,c+i);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)//常规二维 0-1 背包
            for(int k=v;k>=b[i];k--)
                if(f[j-a[i]][k-b[i]]+c[i]>f[j][k])//注意必须是大于号,否则 WA#2
                    f[j][k]=f[j-a[i]][k-b[i]]+c[i],g[i][j][k]=1;//如果选这个物品可以更优,则进行更新并记录方案
    printf("%d\n",f[m][v]);//先把最优结果输出
    int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])
        {
            ans[cnt++]=i;
            m-=a[i];
            v-=b[i];
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);
    return 0;
}

解题报告 P1164 小 A 点菜

题目内容

P1164

一个餐馆,n 种菜,每种菜只有一份,价值为 a_i 元,求刚好花完 m 元的方案总数。

解题思路

具体的思路就是,可以通过前面一个状态转移

f(i,x) 表示选了前 i 个物品后当前钱为 x 的方案个数,则有状态转移方程

f(i,x)=f(i-1,x)+f(i-1,x-a_i)

就是当前状态的方案数,可以选,可以不选,假设不选,那就有 f(i-1,x) 个方案,如果要选,那就有 f(i-1,x-a_i) 个方案,只需要两个方案数加起来即可,初始值 f(0,0) 设为 1 即可,然后第一维是可以滚动掉的,所以最终的转移方程是 f[j]+=f[j-a[i]]

#include <cstdio>

int n,m,a[105],f[10005];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    f[0]=1;//赋初始值
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)//同样需要从大到小进行循环
            f[j]+=f[j-a[i]];//进行递推
    printf("%d\n",f[m]);//输出最终结果
    return 0;
}

解题报告 P1757 通天之分组背包

题目内容

P1757

大意:多组物品,每组中只能选一个,求最大价值

解题思路

一个裸的分组背包,只需每组分别枚举,然后统计答案即可,这里存储每组物品的数据使用的是 vector 和 pair 配合。

注意枚举物品的循环要在枚举容量的循环之内,因为每组中只能取一个物品,所以每次都只找出每组中对应容量选哪个物品能达到最大。就是一层一层的枚举组数,然后开始从大到小枚举容量(否则会重复),再然后枚举这一对应容量只选一个物品能达到的最大价值。

#include <cstdio>
#include <vector>
#include <utility>

std::vector<std::pair<int,int> > group[102];//group[i][j] 表示第 i 组中第 j 个物品
//pair 的第一个元素是重量,第二个元素是价值
int m,n,f[1005];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        group[c].push_back(std::make_pair(a,b));
    }
    for(int k=0;k<102;k++)
        if(!(group[k].size()))
            continue;
        else
            for(int j=m;j>=0;j--)
                for(auto i:group[k])
                    if(j>=i.first)//要防止数组越界
                        f[j]=max(f[j],f[j-i.first]+i.second);
    printf("%d\n",f[m]);
    return 0;
}

解题报告 P1833 樱花

题目内容

P1833

大意:上学路上,看樱花,给出起始时间和终止时间,每棵樱花树都要 t_i 时间看,有 c_i 美学值,最多看 a_i 次(a_i=0 则无限次),求最高美学值。

解题思路

混合背包,将 0-1 背包,完全背包和多重背包混合在了一起,具体的思路还是二进制拆分,只需要将每一个物品拆分成 2^j 的形式即可,然后全部当作 0-1 背包处理即可,当然也可以单独拆分处理,这里没写。

方程还是熟悉的 f[j]=max(f[j],f[j-t[i]]+c[i]);

#include <cstdio>
#define max(a,b) (a>b?a:b)

int T,n,totn,f[1010],t[100010],c[100010];

int main()
{
    int teh,tem,tsh,tsm;
    scanf("%d:%d %d:%d %d",&tsh,&tsm,&teh,&tem,&n);//注意读入数据的处理,使用 scanf 会很方便
    T=(teh-tsh)*60+tem-tsm;//计算时间
    int tt,cc,a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&tt,&cc,&a);
        if(!a)
            a=999999;//如果是完全背包的话,可以先将次数令为无限大
        int cnt=0;
        for(int j=1;j<=a && cnt<=T;j<<=1)//常规二进制拆分
        {
            cnt+=j;
            a-=j;
            t[++totn]=tt*j,c[totn]=cc*j;
        }
        if(a && cnt<=T)
            t[++totn]=tt*a,c[totn]=cc*a;
    }
    for(int i=1;i<=totn;i++)
        for(int j=T;j>=t[i];j--)
            f[j]=max(f[j],f[j-t[i]]+c[i]);
    printf("%d\n",f[T]);
    return 0;
}

解题报告 P1776 宝物筛选

题目内容

P1776

多重背包模板

解题思路

裸的多重背包,考虑像完全背包那样将每个物品进行二进制拆分,然后当作 0-1 背包一样处理即可。(不用单调队列优化是因为我太菜了不会)

主要的核心就是如何进行二进制拆分,即把每个物品拆分为诸如 2^j 个物品,可以将处理每个物品的时间复杂度降到 log 级别。

之后就是常规 0-1 背包

#include <cstdio>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=1e5+10;
int totn,W,n,v[maxn],w[maxn],f[(int)4e4+10];

int main()
{
    totn=0;
    scanf("%d %d",&n,&W);
    register int vv,ww,m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&vv,&ww,&m);
        for(int j=1;j<=m;j<<=1)
        {
            m-=j;
            v[++totn]=vv*j,w[totn]=ww*j;
        }
        if(m)
            v[++totn]=vv*m,w[totn]=ww*m;
    }
    for(int i=1;i<=totn;i++)
        for(int j=W;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("%d\n",f[W]);
    return 0;
}

解题报告 P1855 榨取 kkksc03

题目内容

P1855

大意:有 n 个需要时间为 t_i,金钱为 m_i 的愿望,一共有 M 元钱,T 时间,求最多能完成多少愿望

解题思路

这还是一个背包问题,只不过维度增加了一维,开到了二维,但总体的 0-1 背包思路是不变的。

f(n,i,j) 表示放入前 n 个物品,金钱容量为 i,时间容量为 j 的“背包”最多能装下的愿望个数,即最多能满足的愿望个数,然后枚举即可。

f(n,i,j)=\max(f(n,i,j),f(n-1,i-m_i,j-t_i)+1)

同样的,数组的第一维可以滚动掉

代码细节:

  • 因为我很蠢,所以一开始 f 数组的容量没有开够,是需要以最大时间和最大空间来开的,而不是已物品数量(RE了两回)
  • 转移方程部分代码较长,容易打错(错了一次)

代码:

#include <cstdio>

int n,M,T,m[105],t[105];
int f[205][205];

inline int max(int _a,int _b)
{
    return _a>_b?_a:_b;
}

int main()
{
    scanf("%d %d %d",&n,&M,&T);
    for(int i=1;i<=n;i++)
        scanf("%d %d",m+i,t+i);
    for(int i=1;i<=n;i++)
        for(int j=M;j>=m[i];j--)//倒序枚举
            for(int k=T;k>=t[i];k--)//倒序枚举
                f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1);
    printf("%d\n",f[M][T]);
    return 0;
}

解题报告 P1064 金明的预算方案【NOIP2006TGT2】

题目内容

P1064

大意:金明有 N 元,想买 M 种物品,每个物品有价格 v_i 和重要度 p_i,有些物品是附件,必须要买主件才能买附件,求最大的 \sum v_ip_i

解题思路

“暴力”的正解

在这里问题的本质是不变的,仍是一个 0-1 背包问题,但不同的是加上了从属条件,也就是有依赖的背包问题。

由于一个主件最多有 2 个附件,因此可以考虑递推的时候暴力枚举。

开两个二维数组 v_{i,j} 表示第 i 个物品的第 j 个附件的价格(j=0 即为主件),p_{i,j} 表示第 i 个物品的第 j 个附件的重要程度。读入的时候进行处理即可。

然后当递推的时候,就存在 5 种选择:
1. 不选
2. 只要主件
3. 主+附件1
4. 主+附件2
5. 都要

根据当前枚举到的背包容量是否够即可。然后由于书写量太大容易出错,所以这里使用 lambda 表达式,具体见代码,转移方程与 0-1 背包的并无多大差别

#include <cstdio>
#include <algorithm>
using std::max;

int f[32010],v[70][3],p[70][3],aux[70],n,m;
//f 为递推数组, v,p 见上述,aux[i] 表示第 i 个物品拥有的附件个数

int main()
{
    scanf("%d %d",&n,&m);
    int _v,_p,q;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&_v,&_p,&q);
        if(!q)//如果是主件
            v[i][0]=_v,p[i][0]=_p;//直接搞
        else//否则是附件
            v[q][++aux[q]]=_v,p[q][aux[q]]=_p;//加到对应主件的后面去
    }
    for(int i=1;i<=m;i++)//开始递推
        for(int j=n;j>=v[i][0];j--)//熟悉的 0-1 背包
        {
            auto cost=[i](int x){return v[i][0]+v[i][x];};
            auto cost3=[i](){return v[i][0]+v[i][1]+v[i][2];};
            auto pdc=[i](int x){return v[i][x]*p[i][x];};
            //cost(x) 表示主件与第 x 个附件的价格之和
            //cost3() 表示主件与所有附件的价格之和
            //pdc(x) 表示第 x 个附件(0为主件)的价格与重要度的乘积
            f[j]=max(f[j],f[j-v[i][0]]+pdc(0));//第一个
            if(j>=cost(1))//如果可选第一个附件
                f[j]=max(f[j],f[j-cost(1)]+pdc(0)+pdc(1));//判断哪个更大
            if(j>=cost(2))//如果可选第二个附件
                f[j]=max(f[j],f[j-cost(2)]+pdc(0)+pdc(2));//同理
            if(j>=cost3())//如果都可以要
                f[j]=max(f[j],f[j-cost3()]+pdc(0)+pdc(1)+pdc(2));//那么都要
        }
    printf("%d\n",f[n]);//输出即可
    return 0;
}

真正正解(背包九讲)

刚才的方法很不错,但显然,当附件的数量多起来(刚才最多 2 个),数据变大之后,第一种方法就 gg 了,所以这里引出了背包九讲种使用的正解做法

解题报告 几道背包水题 P1060 P1048 P1049 P1616

P1060 开心的金明【NOIP2006PJ】

题目内容

P1060

大意:给定 m 件价格分别为 v_i,重要度为 w_i 的物品,求总钱数不超过 N 时最大的 \sum v_iw_i

解题思路

裸的 0-1 背包,直接求解即可,由于这是我写的第一个背包,所以用的是二维数组,也会方便理解一些。

#include <cstdio>

int n,m,v[30],p[30],f[30][30000];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d",&n, &m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&v[i], &p[i]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(v[i]>j)
                f[i][j]=f[i-1][j];
            else
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]);
        }
    printf("%d\n",f[m][n]);
}

P1048 采药【NOIP2005PJ】

题目内容

P1048

大意:给出若干株草药采摘需要的时间以及他们对应的价值,求在给定时间内能采集到的最大价值,每种草药只有一株

解题思路

还是裸的 0-1 背包,但使用了滚动数组优化空间,注意第二层的循环顺序是从大到小即可。

#include <cstdio>

int f[1005],t,m,w[105],c[105];
inline int max(int x,int y){return x>y?x:y;}

int main()
{
    scanf("%d %d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&w[i],&c[i]);
    for(int i=1;i<=m;i++)
        for(int j=t;j>=w[i];j--)
            f[j]=max(f[j-w[i]]+c[i],f[j]);
    printf("%d\n",f[t]);
    return 0;
}

P1049 装箱问题【NOIP2001PJ]

题目内容

P1049

大意:给定一个容积为 V 的箱子,以及 n 个物品,每个物品有对应的体积,求如何选择能使得剩余空间最小,求剩余空间

解题思路

注意读题:这个是在 n 个物品中选,是 0-1 背包,不是完全背包,一开始我当成完全背包做了半天。

一样的 0-1 背包,只不过在这里所谓的价格和权值相等了都是对应的体积罢了。

#include <cstdio>

int f[20005],v,n,p[35];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d\n%d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
        for(int j=v;j>=p[i];j--)
            f[j]=max(f[j],f[j-p[i]]+p[i]);
    printf("%d\n",v-f[v]);
    return 0;
}

P1616 疯狂的采药

题目内容

P1616

大意:和采药一样,只不过每种草药可以取无限多个

解题思路

看了背包九讲之后,知道了这是一个完全背包问题,解决他我使用了两种方法。

第一种是使用二进制优化,将一个物品拆成费用为 c_i2^k ,价值为 w_i2^k 的物品,其中 k\in{c_i2^k\leq V\mid k\in\N}。这样就成功将处理一个物品变为处理 O(\log\frac V{c_i}) 个物品,这样就可以使用 0-1 背包解决问题了。

#include <cstdio>

int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d", &t ,&m);
    totm=1;
    for(int i=1;i<=m;i++)
    {
        int ww, cc;
        scanf("%d %d", &cc, &ww);//cc is time, ww is value
        for(int j=0;(1<<j)*cc<=t;j++)//读入的时候就要进行处理
        {
            w[totm]=ww*(1<<j);//位运算可香了
            c[totm++]=cc*(1<<j);
        }
    }
    for(int i=1;i<=totm;i++)//然后就是和 0-1 背包一模一样的处理
        for(int j=t;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d\n",f[t]);
    return 0;
}

第二种就是常规的完全背包,就是将 0-1 背包的内层循环改了顺序而已,代码如下:

#include <cstdio>

int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&c[i],&w[i]);
    for(int i=1;i<=m;i++)
        for(int j=c[i];j<=t;j++)//注意这里的顺序
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d\n",f[t]);
    return 0;
}

解题报告 P1045 麦森数【NOIP2003PJ】

题目内容

P1045

大意:求 2^p-1 的位数和最后 500 位

解题思路

嗯,我的第一思路是爆算(不可能)

蒟蒻发现了求位数可以这样搞:由于 2^p 的各位不可能为 0,所以 2^p 的位数与 2^p-1 的位数相同。又由于一个数的位数为 \lg x+1 ,对 \lg(2^p)+1 进行变换可得

\lg(2^p)+1=p\lg2+1

然后于是第一问 O(1) 解决

第二问一看求 2^p-1 的后五百位,快速幂解决即可,每次操作使用 vector 的 resize() 函数来将多余的删掉即可。每次乘法的时候只乘 500 .

坑点:输出要求前导零和分行输出我因为后面那个调了好久

vector 的 resize 的用法:vector<int>::resize(std::size_t __new_size, const int &__x)意思就是将这个 vector 缩减/增加到能容纳 __new_size 个元素,第二个参数就是将增加出来的赋默认值

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef vector<int> bigint;

bigint operator*(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size()>500?500:a.size(),lb=b.size()>500?500:b.size();
    for(int i=0;i<la+lb;i++)
        ans.push_back(0);
    for(int i=0;i<lb;i++)
    {
        for(int j=0;j<la;j++)
        {
            ans[i+j]+=a[j]*b[i];
            if(ans[i+j]>=10)
            {
                ans[i+j+1]+=ans[i+j]/10;
                ans[i+j]%=10;
            }
        }
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        if(ans[i])
            break;
        else
            ans.pop_back();
    }
    if(ans.size()>500)//把多于500的位干掉
        ans.resize(500);
    return ans;
}

bigint ksm(int p)//快速幂
{
    bigint base={2};
    bigint ans={1};
    while(p)
    {
        if(p&1)
            ans=ans*base;
        base=base*base;
        p>>=1;
    }
    ans.resize(500,0);//最后将ans缩到500位并补前导0
    return ans;
}

void print(bigint a)
{
    a[0]--;
    reverse(a.begin(),a.end());
    int j=1;
    for(auto i:a)//c++11 新特性
    {
        printf("%d",i);
        if(j%50==0)//分行输出
            printf("\n");
        j++;
    }
    return;
}

int main()
{
    int p;
    scanf("%d",&p);
    printf("%lld\n",(long long)(p*(double)log10((double)2.0)+1));//搞位数
    bigint ans=ksm(p);
    print(ans);
    return 0;
}

解题报告 P1147 连续自然数和

题目内容

P1147

大意:给定一整数 N ,求所有的区间 [l,r] (l<r) ,使得 l,r\in\mathbb{N}\sum_{i=l}^ri=N

解题思路

这道题就是求连续自然数和等于 N 的所有区间,思路有两种,一种是比较好想的双指针,另一种就是直接枚举 N 的因子。最终双指针更快一些。

双指针:用两个指针 i. j 扫描,求出 [i,j] 的区间和并保持 i\not=j ,当 sum 时,说明少了,将 j 加一,当 sum > N 时,说明多了,将 i 减一,同时记得操作 sum ,如果刚好相等,输出答案并继续枚举。

#include <cstdio>

int main()
{
    int m;
    scanf("%d",&m);
    int sum=1;
    for(int i=0,j=1;i<j&&i<m/2+1;)//只需枚举到m/2即可
    {
        if(sum<m)
            sum+=++j;//小了,j加一,sum同时增加加一后的j
        else if(sum>m)
            sum-=i++;//大了,减一,sum-i然后i加一
        else if(sum==m)
            printf("%d %d\n",i,j),sum-=i++;//打印答案之后记得继续向前枚举
    }
    return 0;
}

枚举因子:由于等差数列可以看作中间项乘以项数,所以完全可以通过枚举 N 的因子判断中间项,然后筛掉不合要求的,项数是偶数时除出来的一定是 .5 结尾的,项数是奇数时一定除得尽。记得特判,具体看代码:

#include <cstdio>
#include <cmath>

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=n;i>1;i--)//i是枚举项数
    {
        if(((!(n%i) && i&1) //如果能整除且项数为奇数
          || (fabs((n/(double)i)-(n/i)-0.5)<1e-5))//或者以.5结尾并且项数为偶数
          && n/(double)i-i/2.0>0)//要求最小项不能越界
        {
            if(fabs((n/(double)i)-(n/i)-0.5)<1e-5)//偶数项
                printf("%d %d\n",n/i-i/2+1,n/i+i/2);//打印左右边界
            else
                printf("%d %d\n",n/i-i/2,n/i+i/2);//奇数项
        }
    }
    return 0;
}