B-F Java题解 未完待续

B 小红装匣子

容易观察，竖着放两列1x2的块儿等同于横着放两排，而1x3的只能横着放，因此分类讨论有一个竖着放的和没有竖着放的两种情况，在每种前提下，一行需要先尝试用1x3的填满，或者剩余偶数列，剩下的用1x2横向填满，时间复杂度O(T)

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 a=sc.nextInt(),b=sc.nextInt(),n=sc.nextInt();
            System.out.println(check(a,b,n)||a>0&&check(a-1,b,n-1)?"YES":"NO");
        }
    }
    static boolean check(int a,int b,int n){
        for(int i=0;i<2;i++){
            int count=Math.min(n/3,b);
            if((n-count*3)%2==1){
                count--;
            }
            b-=count;
            if(a<(n-count*3)/2){
                return false;
            }
            a-=(n-count*3)/2;
        }
        return true;
    }
}

C 小红的数字对对碰

容易得到，一个数自己异或自己可以得到0而消去，而负数跟任何非负数异或得到的都输负数，因此非负数之间可以自我消化，剩下的非负数可以用负数去消除，这样下来，假如非负数剩余，那么就剩下这些数，负数剩余的话，他们可以两两求和消去，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count=0;
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            if(a>=0){
                if(!set.add(a)){
                    set.remove(a);
                }
            }
            else{
                count++;
            }
        }
        System.out.println(count>=set.size()?n%2:set.size()-count);
    }
}

D 小红的最大字典序

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Queue<String> q=new PriorityQueue<>((s1,s2)->s2.compareTo(s1));
        for(int i=0;i<n;i++){
            q.add(sc.next());
        }
        while(!q.isEmpty()){
            String s=q.poll();
            System.out.print(s.charAt(0));
            if(s.length()>1){
                q.add(s.substring(1));
            }
        }
    }
}

E 小红的图上加边

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),a[]=new int[n+5],min=(int)2e9;
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        long ans=0;
        boolean has[]=new boolean[n+5];
        for(int i=1;i<=n;i++){
            if(!has[i]){
                Queue<Integer> q=new LinkedList<>();
                q.add(i);
                int max=a[i];
                while(!q.isEmpty()){
                    int b=q.poll();
                    for(int c:path[b]){
                        if(!has[c]){
                            has[c]=true;
                            q.add(c);
                            max=Math.max(max,a[c]);
                        }
                    }
                }
                ans+=max;
                min=Math.min(min,max);
            }
        }
        System.out.println(ans-min);
    }
}

F 小红的括号串

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count1=0,count2=0;
        if(n%2==1){
            System.out.println("0");
        }
        else{
            for(char c:sc.next().toCharArray()){
                if(c=='('){
                    count1++;
                }
                else if(c==')'){
                    count2++;
                }
            }
            System.out.println(comb(n-count1-count2,(n-count1-count2-Math.abs(count1-count2))>>1));
        }
    }
    static long comb(int a,int b){
        return a<b||b<0?0:fac(a)*pow(fac(b)*fac(a-b)%mod,mod-2)%mod;
    }
    static long fac(int a){
        return a==0?1:fac(a-1)*a%mod;
    }
    static long pow(long a,int b){
        long ans=1;
        while(b!=0){
            if(b%2==1){
                ans=ans*a%mod;
            }
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
}