UOJ 176 新年的繁荣

Wesley13
• 阅读 461

挺妙的解法。

发现边权很小,我们可以考虑从大到小枚举边权来进行$kruskal$算法,这样子对于每一个边权$i$,我们只要枚举$0 \leq j < m$,找到一个点使它的点权为$i | 2^j$,尝试连边即可。

另外,如果同一个点权重复出现,一定有办法使这个边权连满,这样子直接累加到答案里就可以了。

时间复杂度$O(m * 2^m)$,再套一个并查集的复杂度。

Code:

UOJ 176 新年的繁荣 UOJ 176 新年的繁荣

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 18;

int n, m, a[1 << N], ufs[1 << N];
ll ans = 0LL;

inline void read(int &X) {
    X = 0; char ch = 0; int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op; 
}

inline int find(int x) {
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

inline bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy) return 0;
    ufs[fx] = fy;
    return 1;
}

int main() {
//    freopen("Sample.txt", "r", stdin);
    
    read(n), read(m);
    for(int x, i = 1; i <= n; i++) {
        read(x);
        if(a[x]) ans += 1LL * x;
        else a[x] = x;
    }
    
    for(int i = 1; i < (1 << m); i++) ufs[i] = i;
    for(int i = (1 << m) - 1; i >= 0; i--) {
        for(int j = 0; j < m && (!a[i]); j++)
            a[i] = a[i | (1 << j)];
        for(int j = 0; j < m; j++)
            if(a[i | (1 << j)] && merge(a[i], a[i | (1 << j)]))
                ans += 1LL * i;
    }
    
    printf("%lld\n", ans);
    return 0;
}

View Code

点赞
收藏
评论区
推荐文章
小天 小天
1年前
图数据库简介
概况图数据库(Graphdatabase,GDB)是一个使用图结构进行语义查询的数据库,它使用节点、边和属性来表示和存储数据。该系统的关键概念是图,它直接将存储中的数据项,与数据节点和节点间表示关系的边的集合相关联。图形数据库应用场景非常
Stella981 Stella981
2年前
Codeforces 862B (二分图染色)
<题目链接(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fvjudge.net%2Fproblem%2FCodeForces862B)\题目大意:给出一个有n个点的二分图和n1条边,问现在最多可以添加多少条边使得这个图中不存在自环,重边,并且此图还是一个二
Stella981 Stella981
2年前
Github和Azure DevOps的代码同步
【前言】Github和AzureDevOps都提供了Git代码库功能,那么有没有办法将两边的代码库进行同步呢,答案是肯定的。这里的操作我都是用AzureDevOps的Pipelines功能来完成的,当然用Github的Actions应该也能达到类似的效果,其他小伙伴们不妨尝试一下。 【从AzureDevOps到Github】
Stella981 Stella981
2年前
Docker 入门终极指南!边学边用
点击上方“民工哥技术之路”,选择“设为星标”回复“1024”获取独家整理的学习资料!!(https://oscimg.oschina.net/oscnet/5cc8ef8e99d84510ba7abce9d47c57ff.jpg)(https://www.oschina.net/action/GoToLink?urlhttps%3A
Stella981 Stella981
2年前
HDU 3416 Marriage Match IV (Dijkstra+最大流)
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的ST的最短路有多少条。分析:首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢?可以这样:先对起点S,跑出最短路;对于每条边e(u,v,w),若d\u\wd\v\。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两
Stella981 Stella981
2年前
Codeforces 1208F Bits And Pieces 位运算 + 贪心 + dp
题意:给你一个序列a,问a\i\^(a\j\&a\k\)的最大值,其中i<j<k。思路:我们考虑对于每个a\i\求出它的最优解。因为是异或运算,所以我们从高位向低位枚举,如果这一位a\i\是0,我们就在a\i\的右边找两个位置让它们按位与起来这位是1。那么,我们贪心的保留可以通过按位与凑出某个二进制数的最靠右的两
Stella981 Stella981
2年前
Docker 入门终极指南:边学边用
点击关注上方“杰哥的IT之旅”,后台回复“Python自动化(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzAwMjg1NjY3Nw%3D%3D%26mid%3D2247491317%26id
Wesley13 Wesley13
2年前
C++核心准则边译边学
!(https://oscimg.oschina.net/oscnet/84b9c4254c4d4d43b1a748d276e344cd.jpg)In.not:Nonaims(目标之外)Therulesarenotintendedtobeminimalor
Stella981 Stella981
2年前
Dijkstra算法
引言Dijkstra算法主要应用在寻找带正边权的图中顶点之间的最短路径。这种例子在生活中非常多,比如导航软件自动规划路径,路径最短或用时最少的路径总是作为最优路径返回给你;又比如我大天朝最常见的找人办事,有的时候我们没法直接找到可以帮忙的人,就需要再找别人帮忙,又或者关系不够铁,找人花的代价很大,我们总是潜意识里找关系最铁并中转最少的人去帮忙。
Stella981 Stella981
2年前
Canvas2D实现对图片进行网格变换
最近一直在补线代的理论,边学边用代码实现里面的知识点。但是学习知识的目的总归是为了运用到工作和生活中去,为了不让这个过程太枯燥,试着利用目前复习的线代基础知识,做一个小demo。思考良久,决定实现一下Spine、live2D、龙骨这些工具的网格变换功能。开干!效果图如下:!(https://oscimg.oschina.net/oscnet/up