题解 | 牛客周赛 Round 109 CDEF Java题解

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

C 小红的整数三角形

对于向量(x1,y1)和(x2,y2)围成的三角形，其面积为abs(x1y2-x2y1)/2，并且数值不能为0，，不妨将其中那个的x坐标对称到另一个点x坐标的对称位置，此时可以保证面积是整数，但是面对两点x或者y坐标相同的情况，需要相应维度上额外增加2，时间复杂度O(1)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long x1=sc.nextInt(),y1=sc.nextInt(),x2=sc.nextInt(),y2=sc.nextInt();
        System.out.println((x1*2-x2+(x1==x2?2:0))+" "+(y2+(y1==y2?2:0)));
    }
}

D 小红的马

用哈希表模拟计数即可，时间复杂度O(n)

import java.util.*;
public class Main{
    static int move[][]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        Set<String> set=new HashSet<>();
        Map<String,Integer> map=new HashMap<>();
        for(int i=sc.nextInt();i!=0;i--){
            set.add(find(sc.nextInt(),sc.nextInt()));
        }
        for(String s:set){
            int idx1=Integer.parseInt(s.substring(0,s.indexOf(" "))),idx2=Integer.parseInt(s.substring(s.indexOf(" ")+1));
            for(int mo[]:move){
                int x=idx1+mo[0],y=idx2+mo[1];
                if(x>0&&y>0&&!set.contains(find(x,y))){
                    map.put(find(x,y),map.getOrDefault(find(x,y),0)+1);
                }
            }
        }
        String ans="";
        for(String s:map.keySet()){
            if(map.get(s)>map.getOrDefault(ans,0)){
                ans=s;
            }
        }
        System.out.println(ans);
    }
    static String find(int x,int y){
        return x+" "+y;
    }
}

E 小红的好矩形

分别枚举横边和纵边为1的配对情况，最后减去单位正方形的数量，时间复杂度O(n)

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][];
        Set<String> set=new HashSet<>();
        for(int i=0;i<n;i++){
            xy[i]=new int[]{sc.nextInt(),sc.nextInt()};
            set.add(find(xy[i][0],xy[i][1]));
        }
        Map<Integer,Integer> map=new HashMap<>();
        long ans=0;
        for(int a[]:xy){
            if(set.contains(find(a[0]+1,a[1]))){
                ans+=find(map,a[0]);
            }
        }
        map.clear();
        for(int a[]:xy){
            if(set.contains(find(a[0],a[1]+1))){
                ans+=find(map,a[1]);
            }
        }
        for(int a[]:xy){
            if(set.contains(find(a[0],a[1]+1))&&set.contains(find(a[0]+1,a[1]+1))&&set.contains(find(a[0]+1,a[1]))){
                ans--;
            }
        }
        System.out.println(ans);
    }
    static int find(Map<Integer,Integer> map,int a){
        map.put(a,map.getOrDefault(a,0)+1);
        return map.get(a)-1;
    }
    static String find(int a,int b){
        return a+" "+b;
    }
}

F 小红的线下查询

整理一下可知，y-x<k1 且 x+y<k2，因此先把x+y离散化，再按照y-x排序，在处理询问的时候，用树状数组计数，按照k1升序小处理，时间复杂度O(nlogn+qlogq)

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=new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken()),xy[][]=new int[n][],count[]=new int[n+5],query[][]=new int[q][],ans[]=new int[q];
        TreeSet<Integer> set=new TreeSet<>();
        set.add(-(int)2e9-1);
        for(int i=0;i<n;i++){
            st=new StringTokenizer(bf.readLine());
            int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken());
            xy[i]=new int[]{y-x,x+y};
            set.add(x+y);
        }
        Map<Integer,Integer> map=new HashMap<>();
        for(int a:set){
            map.put(a,map.size());
        }
        for(int i=0;i<q;i++){
            st=new StringTokenizer(bf.readLine());
            query[i]=new int[]{i,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
        }
        Arrays.sort(xy,(a,b)->Integer.compare(a[0],b[0]));
        Arrays.sort(query,(a,b)->Integer.compare(a[1],b[1]));
        for(int i=0,j=0;j<q;j++){
            while(i<n&&xy[i][0]<query[j][1]){
                for(int k=map.get(xy[i][1]);k<=n;k+=k&-k){
                    count[k]++;
                }
                i++;
            }
            for(int k=map.get(set.lower(query[j][2]));k!=0;k-=k&-k){
                ans[query[j][0]]+=count[k];
            }
        }
        for(int a:ans){
            bw.write(a+"\n");
        }
        bw.flush();
    }
}