题解 | 牛客小白月赛108 CDEF Java题解

C~F Java题解，代码已去除冗余~~~

C 小T数星星

对于每一组内的数字，必须是全都一样的，且数量为奇数，遍历计数即可，时间复杂度O(Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),ans=0;
            Map<Integer,Integer> map=new HashMap<>();
            for(int j=0;j<n;j++){
                int a=sc.nextInt();
                map.put(a,map.getOrDefault(a,0)^1);
            }
            for(int a:map.values()){
                ans+=2-a;
            }
            System.out.println(ans);
        }
    }
}

D 小A弹吉他

对于某个固定的最大的数的数量值，较大的数频次越小，才能保证和最小，而这个和随着最大值的增加而增加，因此，二分得到最大的可以的数字即可，时间复杂度O(TlogC)，其中C==2e6

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            long m=sc.nextLong();
            int l=1,r=(int)2e6;
            while(l<r){
                int mid=(l+r)>>1;
                if(sum(mid)<=m){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
                if(l==r-1){
                    if(sum(r)<=m){
                        l=r;
                    }
                    break;
                }
            }
            System.out.println(l);
        }
    }
    static long sum(long p){
        return p*(p+1)*(p-1)/6;
    }
}

E 小M种树

改变一个节点的颜色只会对改点的祖先节点造成影响，因此可以进行两次神搜，第一次统计每个点子树的节点颜色数量，第二次计算改变每个节点颜色会对祖先节点造成什么样的变化，时间复杂度O(Tn)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            int n=Integer.parseInt(bf.readLine()),pre[][][]=new int[n+5][][],ans[]=new int[n];
            String s=bf.readLine();
            List<Integer> path[]=new List[n+5];
            for(int j=1;j<=n;j++){
                path[j]=new ArrayList<>();
            }
            for(int j=0;j<n-1;j++){
                st=new StringTokenizer(bf.readLine());
                int u=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken());
                path[u].add(v);
                path[v].add(u);
            }
            find(1,path,pre,s);
            find(1,path,new boolean[n+5],pre,ans,s);
            for(int a:ans){
                bw.write(String.valueOf(a));
            }
            bw.newLine();
        }
        bw.flush();
    }
    static int[] find(int k,List<Integer> path[],int pre[][][],String s){
        pre[k]=new int[2][2];
        int count[]=new int[2];
        count[s.charAt(k-1)=='R'?0:1]++;
        for(int a:path[k]){
            if(pre[a]==null){
                int b[]=find(a,path,pre,s);
                count[0]+=b[0];
                count[1]+=b[1];
            }
        }
        //0：R变小，1：R变大，2:B变小，3：B变大
        for(int i=0;i<2;i++){
            if(count[i]-count[i^1]>=2){
                pre[k][i][0]++;
            }
            else if(count[i]-count[i^1]<1){
                pre[k][i][1]++;
            }
        }
        return count;
    }
    static void find(int k,List<Integer> path[],boolean has[],int pre[][][],int ans[],String s){
        has[k]=true;
        int color=s.charAt(k-1)=='R'?0:1;
        ans[k-1]=pre[k][color][0]>pre[k][color][1]?1:0;
        for(int a:path[k]){
            if(!has[a]){
                for(int j=0;j<4;j++){
                    pre[a][j/2][j%2]+=pre[k][j/2][j%2];
                }
                find(a,path,has,pre,ans,s);
            }
        }
    }
}

F 小H算数

对每种数字按照下标集合在一起，并预处理出每个坐标前边的大于它的数字的个数（树状数组统计），之后再遍历每种数字的下标，分奇偶下标按照贡献法统计，时间内复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[n+1],pre[]=new int[n+5];
        List<Integer> idx[]=new List[n+5];
        for(int i=1;i<=n;i++){
            idx[i]=new ArrayList<>();
        }
        for(int i=1;i<=n;i++){
            int a=sc.nextInt();
            idx[a].add(i);
            update(count,a);
            pre[i]=i-get(count,a);
        }
        long ans=0;
        for(int i=1;i<=n;i++){
            long sum1[]=new long[2],sum2[]=new long[2];
            for(int a:idx[i]){
                ans+=pre[a]*(sum1[a&1]*2+sum1[a&1^1])-(sum2[a&1]*2+sum2[a&1^1]);
                sum1[a&1^1]++;
                sum2[a&1^1]+=pre[a];
            }
        }
        System.out.println(ans);
    }
    static void update(int count[],int a){
        for(int i=a;i<count.length;i+=i&-i){
            count[i]++;
        }
    }
    static int get(int count[],int a){
        int ans=0;
        for(int i=a;i!=0;i-=i&-i){
            ans+=count[i];
        }
        return ans;
    }
}