I 建通道

链接:https://ac.nowcoder.com/acm/contest/3003/I

在无垠的宇宙中,有 n 个星球,第 i 个星球有权值 v_ivi​。
由于星球之间距离极远,因此想在有限的时间内在星际间旅行,就必须要在星球间建立传送通道。
任意两个星球之间均可以建立传送通道,不过花费并不一样。第 i 个星球与第 j 个星球的之间建立传送通道的花费是 \text{lowbit}(v_i\oplus v_j)lowbit(vi​⊕vj​),其中 \oplus⊕ 为二进制异或,而 \text{lowbit}(x)lowbit(x) 为 x 二进制最低位 1 对应的值,例如 \text{lowbit}(5)=1,\text{lowbit}(8)=8lowbit(5)=1,lowbit(8)=8。特殊地,\text{lowbit}(0)=0lowbit(0)=0。
牛牛想在这 n 个星球间穿梭,于是――你需要告诉 牛牛,要使这 n 个星球相互可达,需要的花费最少是多少。

输入描述:

第一行,一个正整数 n 。
第二行,n 个非负整数 v_1,v_2,\dots,v_nv1​,v2​,…,vn​ 。
保证 1\leq n\leq 2\times 10^51≤n≤2×105,0\leq v_i < 2^{30}0≤vi​<230。

输出描述:

输出一行,一个整数表示答案。

示例1

输入

复制

2
1 2

输出

复制

1

说明

\text{}1、21、2 号点之间建立通道,v_1 \oplus v_2=3, \text{lowbit}(3)=1v1​⊕v2​=3,lowbit(3)=1

代码:

#include<bits/stdc++.h>
using namespace std;
long long a[200005],n;
map<long long,long long>vis;
int main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if (vis[a[i]]) i--,n--;
        vis[a[i]]=1;
    }
    long long ans,c=1;
    if (n==1){
        cout<<"0"<<endl;
        return 0;
    }
    for (int i=1;;i++){
        long long vis0=0,vis1=0;
        for (int j=1;j<=n;j++){
            long long tmp=a[j]&1;
            a[j]/=2;
            if (tmp==0) vis0=1;
            if (tmp==1) vis1=1;
        }
        if (vis0&&vis1) 
        {
            ans=c*(n-1);
            break;
        }
        c=c*2;
    }
    printf("%lld\n",ans);
    return 0;
}

 

全部评论

相关推荐

2025-12-16 22:19
已编辑
南昌市第三中学 Java
个人背景:27届本科&nbsp;江西普通一本院校个人经历:小厂->用友->蔚来->美团->腾讯不知不觉已经有了五段实习经历,也快在外面漂泊一年半了,在今年也完成了两年前自己想进大厂的目标,可能在别人看来确实就是一段比较传奇的过程,一步一步都在向上走,也会有很多人来问我相关学习实习的一些问题,我看到了也会尽量去回复,但现在我想给大家说的并不是千篇一律的学习路线,而是我认为更为重要的——勇气与抉择。下面我来分享一下这些年的心路历程最初学习背景:我跟很多人一样,都是刚进入大学才开始接触计算机,也刚刚拥有自己的电脑,在刚开始学习的过程没有任何人来帮助我,给予我相关的指导,完全是自己摸索出来的一条学习路线,不会有如今这样有很多完善好的速成路线,而家里人都在想让我考研,似乎本科以我的学历就业是不现实的。我也很早意识到了学历对于我的限制,所以萌生出了大一就开始实习的想法,但这个想法在当时基本上是不存在。所有人都在抨击我(这里感兴趣的话可以看我最早发的帖子),有的人说本科想进大厂痴人说梦,有的人劝我以我的学历考研才是上策,有的人说我屁都不懂就来卷,总之我很难说去看到有支持的。我大一的时候还没卷成如今这样很多大一实习,当我想找到是否有跟我一样下定决心一步一步往上走的人,我当时是没有找到的,要么是秋招的哀嚎,要么就直接是零实习进大厂(现在我知道,这里所谓的普通学历0实习进大厂的水分有很多,排除真正意义上的运气和实力,其他基本上全是造假作弊,大家自己心知肚明,也要放平心态)这就导致了一个没有先例的情况,很多人也都是拿没有先例来抨击我,包括家里人也不支持我去实习,可能很多人的积极性就会下降,但我从来不会信所谓的不可能,如果没有先例,那我就会是第一个,他们不行,是因为他们没能力,他们坚持不下去。勇气是很重要的,当你发现你身边没有人像你一样,就很少会有人相信你,看好你,但好在,我不在乎。最初实习阶段:在最初3000沟通只有零星几个面试的时候,那感觉确实很不好受,沉没成本太大,得到的正反馈却太少,当时基本上都是一天学八个小时从来不间断,没有周末没有节假日,甚至过年我都在学习,这就导致我现在都会因为我周末偶尔休息的时候会有负罪感,我感觉已经是种病了,我也知道我也可以休息会但控制不了。当时我出去实习口袋里有1w块(这是我高中三年加大一一年存下来的,基本上是很抠很抠,一个月生活费有时候有一千多有时候就五六百,但也算得上是成功攒了一点钱)但第一次总会是很害怕,担心租房被骗,担心工作能力不行,担心被公司坑,担心学校原因导致不能实习等等,基本上在前面几段实习是根本不攒钱的,代课已经花了一万多,加上租房来回,基本上只能说堪堪不负支出,后来远赴北京,作为一个南方人,有很多不适应的地方,但现在回过头来一想,已经在北京呆了一年多了。我知道很多人要么担心学校因素,要么担心赚的还没花的多,种种因素导致了实习的困难,我也很害怕,我的钱会不会最终全部打水漂,学校会不会爆雷,我以后还能顺利实习吗等等。但对于我来说,我能对自己狠下心,我能接受通勤时间一个半小时只为节省那么几百块的房租钱,我能控制自己的消费的欲望,我能每个月大把大把把钱给代课,这可能就是我能够初期实习顺利的原因,这需要勇气,也需要对自己狠。实习中的抉择:在有了两段实习经历后,我的目标就朝着大厂进发,在去蔚来的中途,我oc了七八家中小厂公司,这里面不乏一些待遇极其优越的公司(有一家我真的差点就去了),但我最终还是都拒了,因为我清楚的明白想往上走的,只有公司title会帮你说话,没有人有义务理解你的困难你的坚持,好在最后去了蔚来,也算如愿以偿。从蔚来到美团倒是没有过多纠结,因为在最开始的梦中情厂就是美团,但从美团去腾讯这个决定或许是我人生中的转折点。美团多次挽留我,帮我沟通问hr,基本上就是一定能转暑期然后成功转正,仿佛这年薪40w的工作已经触手可得,所以在拿到腾讯offer的那一刻并没有多高兴,因为我意识到这可能是我此生最接近大厂的一次机会,可能大部分人都会选择留在美团,我也认为这一定是一个好的选择。我能够走到如今,是永远相信自己的判断,我的每一步都是在赌一个好的未来,只不过,这次赌注大了点而已,或许未来我再也进不了这些所谓的大厂,但我赌的不是选择错对,我赌我不后悔。所谓信念支撑:都说人要为自己而活,但我或许做不到,毕竟我身处人情社会,有许多爱我的人在等着我成长,我也不能接受因为能力而再次放弃一段感情,最近喜欢一段歌词:爱我的人相信我我一直在努力改变所有失败为你们而存在爱我的人感谢你你们的爱就算人生不是精彩我也要勇敢的姿态最后的最后,我想给大家传递的从来都不是一个普通学历进入大厂的意气风发,我想给大家传递的,是一股相信自己能够向上的信念和可能性。在没有打比赛能力,没有开源能力,没有学历等各个限制下,我帮大家试出了一条能够向上的路。如果没有先例,那我会是第一个。我们不需要弄虚作假,只靠自己一步一步脚踏实地,哪怕慢一点,不赌自己是否成功,只赌自己不后悔,问心无愧。最后送给大家,也送给自己一段话结束2025:生活可能没你想的那么好,也不会像你想的那么糟,人的脆弱和坚强,都超乎了你的想象,有时候可能脆弱的一句话就泪流满面,有时候你发现自己咬咬牙已经走了很长的路了
等闲_:感觉咱们双非的同学都有一个共性,想证明双非也是能进大厂的,我之前所有的标签都喜欢带着双非,仿佛这样可以像别人证明自己的实力,现在我却不再想证明双非到底能不能进大厂,我的生活的所有者是我自己,享受生活,接受结果
2025年终总结
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务