请选择 进入手机版 | 继续访问电脑版

codeforces 1466F. Euclid‘s nightmare

[复制链接]
谢世民 发表于 2021-1-2 19:42:44 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
传送门
n个含两位1的向量,每个向量为1的维度相互连边,在不构成环的情况下,有2^n种大概(2^(n+1)个维度),在这个根本上只要加一条含一位1且该维度已出现过1,则可使|T|最大到达2^(n+1); 因此连边后每个连通块最多可包罗一个只有一个1的向量并使答案翻倍, 所以可以把含一个1的向量看作连向m+1的边,然后用并查集找出所有边的条数即为答案
[code]#include using namespace std;typedef long long int LL;const int N = 5e5 + 7;const int MX = 1e9 + 7;int n, m;int rep[N];int Find(int a) {        if (rep[a] == a)                return a;        return rep[a] = Find(rep[a]);}bool Union(int a, int b) {        a = Find(a);        b = Find(b);        rep[a] = b;        return a != b;}int main() {        scanf("%d %d", &n, &m);        for (int i = 1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )