草庐IT

CCF- CSP 202209-2 何以包邮？ 两种方法 dfs+离散化 满分题解

只须一笑不须愁X 2023-04-05 原文

CCF- CSP 202209-2 何以包邮？ 两种方法 dfs+离散化 满分题解

题目链接：202209-2 何以包邮？

思路1（离散化）:

  • n最大为30，a最大为104，所以最大价格为3e5
  • 将所有组合的价格映射到f上，从x开始向大进行查找，直到找到第一个大于等于x的价格(存在此组合)
  • 技巧在于求各种组合的价格，也是采用离散化的思想，将每一个价格和组合映射到f上，每次从M开始遍历整个f，找到加入当前price后，此price和之前的组合形成的新组合所对应的值

代码如下：

#include<iostream>
using namespace std;
const int N = 50, M = 3e5 + 10;//M的范围得大
int n,x;
int price[N];//价格
int f[M];//存储离散化后的点
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>price[i];
    }
    
    //得到各种组合后的价格
    f[0]=1;//初始化
    for(int i=1;i<=n;i++)
    {
        for(int j=M;j>=price[i];j--)
        {
            if(f[j-price[i]])
            {
                f[j]=1;
            }
        }
    }
    
    int out = x;//起始位置
    while(1)
    {
        if(f[out])break;//找到第一个大于等于x的价格
        else
        {
            out++;
        }
    }
    cout<<out<<endl;
    return 0;
}

思路2（dfs不剪枝70分）:

  • 对于每本书，都有选和不选两种方案，可以对应一棵完全二叉树
  • 遍历所有书的两种方案，找到最小值，采用dfs算法

70分代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50;
int n,x;
int price[N];
int ans = 1e9;
void dfs(int k,int sum)
{
    
    if(sum>=x)
    {
        ans = min(sum,ans);//更新最小值
    }
    if(k>n)
    {
        return;
    }
    dfs(k+1, sum+price[k]);//选择这本书
    dfs(k+1,sum);//不选择这本书
}
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>price[i];
    }
    dfs(1,0);//从第一本书开始
    cout<<ans<<endl;
}

思路三（dfs+剪枝100分）：

  • 在思路二的基础上，对二叉树进行剪枝
  • 剪枝思路：当前节点sum加上剩余节点的所有值之和已经小于x了，进行剪枝
  • 求剩余节点的所有值，可以采用前缀和的思想

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50;
int n,x;
int price[N];//价格
int sum_price[N];//前缀和
int ans = 1e9;
void dfs(int k,int sum)
{
    
    if(sum+sum_price[n]-sum_price[k-1]<x)//sum_price[n]-sum_price[k-1]为剩余节点的所有值的和
    {
        return;
    }
    if(sum>=x)
    {
        ans = min(sum,ans);//更新最小值
    }
    if(k>n)
    {
        return;
    }
    dfs(k+1,sum+price[k]);//选择这本书
    dfs(k+1,sum);//不选择这本书
}
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>price[i];
        sum_price[i]=sum_price[i-1]+price[i];//前缀和
    }
    dfs(1,0);//从第一本书开始
    cout<<ans<<endl;
}
题解满分spanclasstoken深度优先算法图论

有关CCF- CSP 202209-2 何以包邮？ 两种方法 dfs+离散化 满分题解的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  3. ruby - 如何以编程方式删除实例上的 "singleton information"以使其编码(marshal)？ - 2

    我创建了一个由于“在运行时执行的单例元类定义”而无法编码的对象(这段代码的描述是否正确？)。这是通过以下代码执行的:#defineclassXthatmyusesingletonclassmetaprogrammingfeatures#throughcallofmethod:break_marshalling!classXdefbreak_marshalling!meta_class=class我该怎么做才能使对象编码正确？是否可以从对象instance_of_x的classX中“移除”单例组件？我真的需要一个建议，因为我们的一些对象需要通过Marshal.dump序列化机制进行缓存。

  4. ruby - 如何以编程方式检查证书是否已被吊销？ - 2

    我正在开发一个xcode自动构建系统。在执行一些预构建验证时，我想检查指定的证书文件是否已被撤销。我了解securityverify-cert验证其他证书属性但不验证吊销。我如何检查撤销？我正在用Ruby编写构建系统，但我对任何语言的想法都持开放态度。我阅读了这个答案(Openssl-Howtocheckifacertificateisrevokedornot)，但指向底部的链接(DoesOpenSSLautomaticallyhandleCRLs(CertificateRevocationLists)now?)进入的Material对我的目的来说有点过于复杂(用户上传已撤销的证书是一

  5. ruby - 如何以表格格式快速打印 Ruby 哈希值？ - 2

    有没有办法快速将表格格式的ruby​​哈希打印到文件中？如:keyAkeyBkeyC...1232343451253474456...其中散列的值是不同大小的数组。还是使用双循环是唯一的方法？谢谢 最佳答案 试试我写的这个gem(在表中打印散列、ruby对象、ActiveRecord对象):http://github.com/arches/table_print 关于ruby-如何以表格格式快速打印Ruby哈希值？，我们在StackOverflow上找到一个类似的问题：

  6. ruby - 如何以编程方式将 mp3 转换为 itunes 可播放的 aac/m4a 文件？ - 2

    我一直在寻找一种以编程方式或通过命令行将mp3转换为aac的方法，但没有成功。理想情况下，我有一段代码可以从我的Rails应用程序中调用，将mp3转换为aac。我安装了ffmpeg和libfaac，并能够使用以下命令创建aac文件:ffmpeg-itest.mp3-acodeclibfaac-ab163840dest.aac当我将输出文件的名称更改为dest.m4a时，它无法在iTunes中播放。谢谢! 最佳答案 FFmpeg提供AAC编码功能(如果您已编译它们)。如果您使用的是Windows，则可以从here获取完整的二进制文件。

  7. ruby-on-rails - 如何以递归方式将 YAML 文件扁平化为 JSON 对象，其中键是点分隔的字符串？ - 2

    例如，如果我有YAML文件en:questions:new:'NewQuestion'other:recent:'Recent'old:'Old'这最终会变成一个json对象，例如{'questions.new':'NewQuestion','questions.other.recent':'Recent','questions.other.old':'Old'} 最佳答案 由于问题是关于在Rails应用程序上使用YAML文件进行i18n，因此值得注意i18ngem提供了一个辅助模块I18n::Backend::Flatten完全像

  8. ruby - 如何以编程方式使用 Rugged 创建提交？ - 2

    我正在尝试使用Rugged以编程方式创建对现有存储库的提交(libgit2的Ruby绑定(bind))。我已尝试遵循RuggedREADME中提供的文档，但我认为它与代码库的当前状态不太匹配。当我尝试运行以下代码时，我不断收到错误消息:require'rugged'#Createaninstanceoftheexistingrepositoryrepo=Rugged::Repository.new('/full/path/to/repo')#grabthecurrentTimeobjectfornowcurr_time=Time.now#writeanewblobtothereposi

  9. ruby-on-rails - 如何以一种形式编辑多个模型？ - 2

    我从教练那里接到了任务。我想以一种形式编辑两个模型。例如，我们有两个实体学生和地址。在新学生部分，我想添加学生详细信息和地址。我如何通过ruby​​onrails中的脚手架实现这一目标？ 最佳答案 您可以使用accepts_nested_attributes_for和fields_for建立一个表格来同时创建两个模型，所以你也可以编辑它们。这种形式称为嵌套形式。这里有一个关于Nestedform的引用给你,. 关于ruby-on-rails-如何以一种形式编辑多个模型？，我们在Stack

  10. ruby - 我如何以编程方式查询 Vagrant 的配置状态？ - 2

    目标我正在尝试有条件地运行vagrant-berkshelf插入。默认情况下，启用该插件会导致Berkshelf在每个vagrantup(这是一个相对昂贵的操作)上解析和供应商说明书，即使当前的vagrant操作不是配置运行。例如，我希望Berkshelf在我运行时运行:vagrantup第一次，或者当我执行vagrantreload--provision时。Thesourceimplies应该有一种方法可以查询Vagrant本身以确定它是否是配置运行。具体来说，应该有一种方法可以挂接到@env[:provision_enabled]或vagrant.actions.vm.provis

随机推荐