牛客编程巅峰赛S2第10场 - 钻石&王者 做题记录

时隔半个月。。。终于搞懂C题了。。

先上原来写的超时代码 ，卡在90%。

写了一个暴力dfs ， 应该是O(N^2)的
主要是没有用到与运算的性质，没有按位与。 简单粗暴的与运算导致重复走了很多个点。

    long res =0;
    public long solve (int n, int[] u, int[] v, int[] p) {
        Map> book = new HashMap();
        for(int i=0;i<n;++i){
            book.put(i,new ArrayList());
        }
        for(int i=0;i<u.length;++i){
            int start = u[i];
            int end =v[i];
            book.get(start).add(end);
            book.get(end).add(start);
        }
        for(int i=0;i<n;++i){
            //以点i为起点
            long cur =-1;
            boolean[] flag = new boolean[n];
            fun(book,p,cur,flag,i);
        }
        long r=  0;
        for(int pp:p){
            r+= pp;
        }

        return (res -r)/2+r;
    }

    public void fun(Map> book,int[] p,long cur,boolean[] flag,int i){
        if(flag[i] || cur ==0){
            return;
        }
        if(cur ==-1){
            //起点
            cur = p[i];
        }else{
            cur = cur & p[i];
        }
        res += cur;
        flag[i]=true;
        List next = book.get(i);
        for(int n : next){
            fun(book,p,cur,flag,n);
        }
    }

按照与运算+连通块的性质， 写bfs
（按位与 ： 例如 15 = 8+4+2+1 ， 即 fun(15) = fun(1<<3) + fun(1<<2) + fun(1<<1) + fun(1<<0) ）

    public long solve (int n, int[] u, int[] v, int[] p) {
        long res =0;
        List<Integer>[] edges = new ArrayList[n];
        for(int i=0;i<edges.length;++i){
            edges[i] = new ArrayList<>();
        }
        for(int i=0;i<u.length;++i){
            edges[u[i]].add(v[i]);
            edges[v[i]].add(u[i]);
        }

        int base =1;
        for(int i=0;i<20;++i){
            //求当前base的连通块数量
            boolean[] vis = new boolean[n];
            for(int j=0;j<n;++j){
                int cnt = bfs(edges,p,j,base,vis);
                res += ((long)cnt*(cnt+1))/2*base;
            }
            base = base <<1;
        }
        return res;
    }

    public int bfs(List<Integer>[] edges,int[] p ,int cur,int base,boolean[] vis){
        if(vis[cur] || (p[cur]&base) ==0){
            return 0;
        }
        int res =0;
        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(cur);
        while(!queue.isEmpty()){
            cur = queue.pollFirst();
            res ++;
            vis[cur] = true;

            for(int edge : edges[cur]){
                if((p[edge]&base)!=0 && !vis[edge]){
                    queue.offerLast(edge);
                }
            }
        }
        return res;
    }

连通块问题也可以使用并查集：

    public long solve (int n, int[] u, int[] v, int[] p) {
        long res =0;
        //按位与，20位
        int base =1;
        for(int cnt =0;cnt<20;++cnt){
            //初始化并查集
            int[] size = new int[n];
            Arrays.fill(size,0);
            int[] f=new int[n];
            for(int i=0;i<n;++i){
                f[i] = i;
            }

            for(int i=0;i<u.length;++i){
                if( (p[u[i]]&base)!=0 && (p[v[i]]&base)!=0 ){
                    //并u[i] v[i]
                    f[find(f,u[i])] = find(f,v[i]);
                }
            }
            for(int i=0;i<n;++i){
                size[find(f,i)]++;
            }
            ArrayTools.printArray(size);
            for(int i=0;i<n;++i){
                if((p[i]&base) !=0){
                    res += (long)size[i]*(size[i]+1)/2*base;
                }
            }
            base =base <<1;
        }
        return res;
    }

    public int find(int[] f,int x){
        if(f[x] ==x){
            return x;
        }
        f[x]=find(f,f[x]);
        return f[x];
    }