首页 > 其他分享 >题解:AT_abc236_f [ABC236F] Spices

题解:AT_abc236_f [ABC236F] Spices

时间:2024-12-17 14:10:44浏览次数:11  
标签:int 题解 ABC236F vis maxn 数组 编号 Spices 代价

今天 2024 秋令营 Day1贪心 例题,来解释一下这道题贪心的思路。

首先输入一个整数 \(n\),表示需要处理的数字数量为 \(2^n - 1\),随后输入每个编号的代价,并将代价和编号存储在数组 \(a\) 中。接着,对代价进行排序,以便在后续处理中优先选择代价较小的数字。然后,使用一个 \(vis\) 数组来标记哪些编号已经被选择,对于每个未选择的编号,选择它并将其代价加入总代价中,同时通过异或操作更新 \(vis\) 数组,以标记出可以由当前选择的编号生成的所有编号。最后,程序输出计算得到的最小代价。

最后上一下代码。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn= 1e5+10;
int vis[maxn], n; // vis数组用于记录已选择的编号,n是输入的数字数量
ll ans; // 用于存储最终的最小代价
pair<int,int> a[maxn]; // 数组a存储每个数字的代价和对应的编号

int main() {
    scanf("%d", &n); // 输入n,表示2的n次方
    n = 1 << n; // 计算2^n的值
    for (int i = 1; i < n; i++) {
        scanf("%d", &a[i].first); // 输入代价,存入a数组的first部分
        a[i].second = i; // 将编号存入a数组的second部分
    }
    
    sort(a + 1, a + n); // 按照代价排序,从小到大
    vis[0] = 1; // 初始化vis数组,标记编号0已被选择

    for (int i = 1; i < n; i++) { // 遍历每个数字
        if (vis[a[i].second]) continue; // 如果该编号已被选择,跳过

        ans += a[i].first; // 将当前代价加到总代价中

        for (int j = 0; j < n; j++) { // 更新vis数组
            if (vis[j]) // 如果j编号已被选择
                vis[j ^ a[i].second] = 1; // 将j与当前编号的异或结果标记为已选择
        }
    }

    printf("%lld\n", ans); // 输出最终的最小代价
    return 0;
}

标签:int,题解,ABC236F,vis,maxn,数组,编号,Spices,代价
From: https://www.cnblogs.com/zenoszheng/p/18612304

相关文章

  • 题解:P7020 [NWRRC2017] Boolean Satisfiability
    首先,我们需要明确一个重要的恒等式:\[x\mid\nega=1\]当\(x=1\)时,\(x\mid\negx=1\mid0\)的结果为\(1\)。当\(x=0\)时,\(x\mid\negx=0\mid1\)的结果同样为\(1\)。因此,我们可以得出结论,该式子的结果恒为\(1\)。接下来,我们观察到,当表达式中仅包含......
  • 牛客周赛 Round 72 题解
    牛客周赛Round72题解A小红的01串(一)直接遍历即可#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ strings;cin>>s;intn=s.size();intcnt=0;for(inti=1;i<n;i++){if(s[i]!=s[i-1])cnt++;}......
  • P5773 [JSOI2016] 轻重路径 题解
    Description在二叉树上,不断删除叶子,你要维护其重链剖分后重儿子编号和。如果两个孩子大小相同,在一开始连向左儿子,后面保持修改前的连接。\(n\leq2\times10^5\)。Solution考虑把一个叶子\(x\)删掉会对改变哪些点的重儿子。首先改变的点\(y\)一定在\(x\)到根的链上,同时......
  • YbtOj题解索引
    不想写作业,水篇博客图论:并查集(已完结)最小生成树(已完结)强连通分量(已完结)最短路径(已完结)数据结构:堆(已完结)RMQ问题(未完结)树状数组(未完结)动态规划:数位DP(未完结)......
  • 题解 - 最小的Y
    题目描述程序设计与数学密切相关,所以兴趣小组的辅导老师经常拿一些有趣的数学题来让大家思考。一次课上,辅导老师又拿出了一个有趣的数学问题,题目是这样的:给你两个正整数x和z,求最小的整数y,使得x×y以后再除以z的余数为0。比如x=3,z=6,求最小的y。题目一出,马上有同学说:最小......
  • 2021ICPC EC final B. Beautiful String题解
    今天跟队友vp21年ECfinal,最后可惜计算几何没开出来,以及J题时间不够没做出来,主要就是B做太麻烦了,导致花了太多时间。但是作为串串人,还是非常喜欢字符串题,这里写一下我们的B题做法。题意定义一个好串是能将字符串分为6个部分\(s_1+s_2+s_3+s_4+s_5+s_6\)并且满足\(s_1=s_2=s_5,......
  • NOIP2024 题解
    考场上一直都不知道在想什么,心态也很不好,结果B一直不会,最后会了C还没写完。感觉这个赛季对我来说就已经结束了吧/hsh/wn本来是想退役的,但是学文化课对我来说太痛苦了,而且我还是比较热爱OI的,所以就再试着走一走吧。P11361[NOIP2024]编辑字符串发现限制就是将\(s\)......
  • 洛谷P7911 [CSP-J 2021] 网络连接题解
    普通的模拟题,数据很小,基本排除超时超空间的可能上代码:#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;vector<pair<int,string>>sv;//用于存储Server,sv[i].first代表Server编号,sv[i].second代表Server地址intturn(stringstr){//string转int if(str.......
  • STM32F407ZGT6-UCOSIII笔记2:UCOSIII任务创建实验-Printf 函数卡住 UCOSIII 系统问题解
    今日简单编写熟悉一下UCOSIII系统的任务创建代码,理解一下OS系统:并发现以及解决了Printf函数卡住UCOSIII系统问题解决文章提供测试代码讲解、完整工程下载、测试效果图目录文件结构解释:任务函数文件:目前各个文件任务:#include"main.h"#include"ComTask.h"#includ......
  • [SCOI2016] 幸运数字 题解
    \(xor\)最大值想到线性基,路径想到\(lca\)和树链剖分,由于没有修改用\(lca\)就可以。先用处理\(fa\)数组的方式处理倍增线性基(自然是得用线性基合并的),在求\(lca\)时把所有线性基全部合到一块儿就行。考虑到本题实际上核心在于让路径上的线性基数量\(\leO(\logn)\),所以......