DEF Java版题解

D 小红的子数组排列判断

思路：窗口，判断每个大小为k的窗口是否存在k种数字，并且最大数字是k，实现的时候用有序映射，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),a[]=new int[n],ans=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=0;i<k;i++){
            modify(map,a[i],1);
        }
        ans+=check(map,k);
        for(int i=k;i<n;i++){
            modify(map,a[i-k],-1);
            modify(map,a[i],1);
            ans+=check(map,k);
        }
        System.out.println(ans);
    }
    static void modify(TreeMap<Integer,Integer> map,int a,int b){
        map.put(a,map.getOrDefault(a,0)+b);
        if(map.get(a)==0){
            map.remove(a);
        }
    }
    static int check(TreeMap<Integer,Integer> map,int k){
        return map.size()==k&&map.lastKey()-k==0?1:0;
    }
}

E 小红的平行四边形

把每对儿点可以组成的向量用唯一的标识记录，这里为了避免斜率的精度问题，利用“x差-空格-y差”表示为字符串，分好组后，利用叉积求面积，时间复杂度O(n^2)，实现过程常数较大，接近了运行时限

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),xy[][]=new int[n][];
        for(int i=0;i<n;i++){
            xy[i]=new int[]{sc.nextInt(),sc.nextInt()};
        }
        Map<String,List<Integer>> map=new HashMap<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int dx=xy[j][0]-xy[i][0],dy=xy[j][1]-xy[i][1];
                String s=dx+" "+dy;
                map.putIfAbsent(s,new ArrayList<>());
                map.get(s).add(i);
            }
        }
        long ans=0;
        for(String s:map.keySet()){
            List<Integer> list=map.get(s);
            String t[]=s.split(" ");
            int dx=Integer.parseInt(t[0]),dy=Integer.parseInt(t[1]),minIdx=0,maxIdx=0;
            for(int i=0;i<list.size();i++){
                long cur=crossPro(new int[]{dx,dy},findVec(xy[list.get(0)],xy[list.get(i)])),min=crossPro(new int[]{dx,dy},findVec(xy[list.get(0)],xy[list.get(minIdx)])),max=crossPro(new int[]{dx,dy},findVec(xy[list.get(0)],xy[list.get(maxIdx)]));
                if(cur>max){
                    maxIdx=i;
                }
                if(cur<min){
                    minIdx=i;
                }
            }
            ans=Math.max(ans,Math.abs(crossPro(new int[]{dx,dy},findVec(xy[list.get(minIdx)],xy[list.get(maxIdx)]))));
        }
        System.out.println(ans==0?"-1":ans+".0");
    }
    static int[] findVec(int a[],int b[]){
        return new int[]{b[0]-a[0],b[1]-a[1]};
    }
    static long crossPro(int a[],int b[]){
        return (long)a[0]*b[1]-(long)a[1]*b[0];
    }
}

F 小红小紫画线

分类讨论，首先任取四个点，保证连线有一个公共点的取法只有一种，那么在取点无重合的前提下，利用组合求出总方案数，再减去四点共线以及三点共线的情况，，另外，还有一种情况需要加上，那就是两人取了有一个公共点，实现上是利用的最大公约数化简的方式，时间复杂度O(nlog(sum(a)))

import java.util.*;
public class Main{
    static long mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n];
        long sum=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
        }
        long ans=comb(sum,4);
        //减去四点共线、三点共线：加上有一个共同点：
        for(int b:a){
            ans=(ans+mod*10-comb(b,4)-(sum-b)%mod*comb(b,3)%mod+comb(sum-b,2)*b%mod)%mod;
        }
        System.out.println(ans*2%mod);
    }
    static long gcd(long a,long b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
    static long comb(long a,long b){
        //计算组合数
        if(b>a){
            return 0;
        }
        long ans=1,fac=1;
        for(int i=2;i<=b;i++){
            fac*=i;
        }
        for(int i=0;i<b;i++){
            long gcd=gcd(fac,a-i);
            fac/=gcd;
            ans=ans*((a-i)/gcd%mod)%mod;
        }
        return ans;
    }
}