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

D 气球谜题

考虑012的各种分组顺序，对每个气球的每种颜色下的涂色成本算出前缀和，对于某一中饭分组顺序，可以确定第一个分界点，再右边找到使得当前操作之和最小的另一个分界点，这里可以利用优先队列优化，时间复杂度O(6nlogn)

import java.util.*;
public class Main{
    static int permutation[][]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String s=sc.next();
        long pre[][]=new long[n+1][3],ans=(long)1e18;
        for(int i=1;i<=n;i++){
            int a=s.charAt(i-1)-'0',t=sc.nextInt();
            pre[i]=pre[i-1].clone();
            for(int j=0;j<3;j++){
                if(j!=a){
                    pre[i][j]+=t;
                }
            }
        }
        for(int p[]:permutation){
            ans=Math.min(ans,find(pre,p));
        }
        System.out.println(ans);
    }
    static long find(long pre[][],int p[]){
        long ans=(long)1e18;
        Queue<long[]> q=new PriorityQueue<>((a,b)->Long.compare(a[1],b[1]));
        for(int i=0;i<pre.length;i++){
            q.add(new long[]{i,pre[i][p[1]]-pre[i][p[2]]});
        }
        for(int i=0;i<pre.length;i++){
            while(q.peek()[0]<i){
                q.poll();
            }
            ans=Math.min(ans,pre[i][p[0]]-pre[i][p[1]]+pre[pre.length-1][p[2]]+q.peek()[1]);
        }
        return ans;
    }
}

E 三角谜题

每种长度的边的数量用有序映射保存，考虑枚举腰的长度，面积当底边最接近腰长根号2倍的时候最大，因此找到上下两种底长计算即可，时间复杂度O(nlogn)

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));
        int t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            int n=Integer.parseInt(bf.readLine());
            double ans=0;
            TreeMap<Integer,Integer> map=new TreeMap<>();
            for(int j=0;j<n;j++){
                String arr[]=bf.readLine().split(" ");
                int l=Integer.parseInt(arr[0]),a=Integer.parseInt(arr[1]);
                map.put(l,Math.min(3,map.getOrDefault(l,0)+a));
            }
            for(int a:map.keySet()){
                int b=map.get(a);
                if(b>=2){
                    Integer p=map.higherKey((int)(a*Math.sqrt(2)));
                    if(p!=null){
                        ans=Math.max(ans,Heron(a,a,p));
                    }
                    p=map.floorKey((int)(a*Math.sqrt(2)));
                    if(p-a==0&&b==2){
                        p=map.lowerKey(p);
                    }
                    if(p!=null){
                        ans=Math.max(ans,Heron(a,a,p));
                    }
                }
            }
            bw.write(ans==0?"-1\n":ans+"\n");
        }
        bw.flush();
    }
    static double Heron(double a,double b,double c){
        double p=(a+b+c)/2;
        return Math.sqrt(Math.max(0,p)*Math.max(0,p-a)*Math.max(0,p-b)*Math.max(0,p-c));
    }
}

F 变化的数组

考虑每个a的变化，与m的与运算结果，最低置为最多操作30次即可消失，这也是需要处理的最大次数，在a不再变化的时候，手动处理即可，，需要预处理组合数，时间复杂度O((nlogk+35^2)log(mod))

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(),m=sc.nextInt(),k=sc.nextInt();
        long ans=0,comb[]=new long[35];
        for(int i=0;i<35;i++){
            comb[i]=1;
            for(int j=1;j<=i;j++){
                comb[i]=comb[i]*(k-j+1)%mod*pow(j,mod-2)%mod;
            }
        }
        for(int i=0;i<n;i++){
            long a=sc.nextInt(),sum=pow(2,k);
            for(int j=0;j<=k&&j<35;j++){
                ans=(ans+a%mod*comb[j])%mod;
                sum=(sum+mod-comb[j])%mod;
                if((a&m)==0){
                    break;
                }
                a+=a&m;
            }
            ans=(ans+a%mod*sum)%mod;
        }
        System.out.println(ans*pow(2,(long)k*(mod-2))%mod);
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}