icontofig | 发布于 2019-08-20 22:02:02 | 阅读量 338 | 思维题
发布于 2019-08-20 22:02:02 | 思维题

题目大意

给n个数,两个数如果能取并运算不为0则又一条边相连,求长度至少为3的最小环的长度,若没有环,输出-1。

题解

md这题我挂了7发,真是sb……

首先我们先从大到小排序,把0去掉,因为0不会和任何数连边。

然后我们考虑二进制并运算,只有两个数某个二进制位相同时,两个数才会连边。

而如果有至少三个数二进制的第i位同时为1时,这些点互相之间都会连边,那么一定会形成环,最小环的长度为3。

所以我们可以对所有非0数进行二进制分解,记录每个二进制位上会出现多少次,如果其中有一个大于等于3,则说明最小环的长度为3。

那么如果没有以上的点就一定答案为-1吗?并不是。

那该怎么做?

如果我们仔细观察,所有数进行二进制分解以后,最多不会超过64位。

所以我们可以根据鸽巢原理得出结论:如果非0的数字超过128个一定会出现长度为3的最小环。

所以说如果我们二进制位检查未能检查出答案,那么只有非0数字在128个及以下的时候,有可能还会存在环。

如果出现这种情况,我们直接暴力建边然后dfs求出最小环(tarjan也可以,不过注意是无向图),如果还是求不出环的话,那么就说明不存在环,直接输出-1。

这个题思路还是蛮巧妙的。其实竞赛中还是有不少的题目是分数据个数搞不同做法的。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
typedef long long ll;
ll a[maxn];
int p[105];
const int INF = 1e9;
void work(ll x){
    int cnt = 0;
    while(x > 0){
        if(x % 2 == 1)p[cnt]++;
        x /= 2;
        cnt++;
    }
    return;
}
const int maxm = 1e3+5;
vector<int>g[maxm];
int vis[maxm];
int tag[maxm];
int ans = 0;
int tot = 0;
int pre[maxm];
void dfs(int now,int fa){
    vis[now] = 1;
    for(int i = 0;i < g[now].size();++i){
        int v = g[now][i];
        if(v == fa)continue;
        if(!vis[v]){
            pre[v] = now;
            dfs(v,now);
        }
        else if(!tag[v]){
            int cnt = 1;
            int t = now;
            tag[t] = 1;
            while(t != v){
                cnt++;
                t = pre[t];
            }
            ans = min(ans,cnt);
        }
    }
    return;
}
bool cmp(ll x,ll y){
    return x > y;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
    }
    sort(a+1,a+n+1,cmp);
    ans = INF;
    memset(p,0,sizeof(p));
    for(int i = 1;i <= n;++i){
        if(a[i] == 0)break;
        tot++;
    }
    for(int i = 1;i <= tot;++i){
        work(a[i]);
    }
    for(int i = 0;i <= 70;++i){
        if(p[i] >= 3){
            cout << 3 << endl;
            return 0;
        }
    }
    for(int i = 1;i <= tot;++i){
        vis[i] = 0;
        tag[i] = 0;
        for(int j = i+1;j <= tot;++j){
            if((a[i] & a[j]) == 0)continue;
            g[i].push_back(j);
            g[j].push_back(i);
        }
    }
    for(int i = 1;i <= tot;++i){
        if(!vis[i]){
            dfs(i,i);
        }
    }
    if(ans == INF){
        cout << -1 << endl;
    }
    else cout << ans << endl;
    return 0;
}

 


内容更新于: 2019-08-20 22:02:27
链接地址: http://blog.leanote.com/post/icontofig/Codeforces-Round-580div2

上一篇: HDU 6703 CCPC 2019 网络赛 1002 array 可持久化线段树(主席树) + set

下一篇: CCPC 2017-2018 Finals HDU 6252 Subway Chasing 差分约束系统

338 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航