题解 | 牛客周赛 Round 57 CDEFG Java题解

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

C 小红的双好数（easy）

1在任意进制下都符合，2只能在2进制下，其他数字在2进制和自己进制下符合，时间复杂度O(1)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        System.out.println(n==2?"NO":"YES\n"+2+" "+Math.max(n,3));
    }
}

D 小红的线段

首先把点分为三类，在直线上侧，在下侧，以及在线上，先把上下两侧的尽可能配对，剩下的全部与在线上的配对儿，剩下的点只能同类配对儿了，时间复杂度O(n)

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(),b=sc.nextInt();
        Queue<Integer> more=new LinkedList<>(),equal=new LinkedList<>(),less=new LinkedList<>();
        for(int i=1;i<=n*2;i++){
            int x=sc.nextInt(),y=sc.nextInt();
            long z=(long)k*x+b;
            if(y>z){
                more.add(i);
            }
            else if(y==z){
                equal.add(i);
            }
            else{
                less.add(i);
            }
        }
        if(Math.abs(more.size()-less.size())<=equal.size()){
            System.out.println(n);
            while(!more.isEmpty()&&!less.isEmpty()){
                System.out.println(more.poll()+" "+less.poll()+" Y");
            }
            while(!more.isEmpty()&&!equal.isEmpty()){
                System.out.println(more.poll()+" "+equal.poll()+" Y");
            }
            while(!less.isEmpty()&&!equal.isEmpty()){
                System.out.println(equal.poll()+" "+less.poll()+" Y");
            }
            while(!equal.isEmpty()){
                System.out.println(equal.poll()+" "+equal.poll()+" Y");
            }
        }
        else{
            System.out.println(Math.min(more.size(),less.size())+equal.size());
            while(!more.isEmpty()&&!less.isEmpty()){
                System.out.println(more.poll()+" "+less.poll()+" Y");
            }
            while(!more.isEmpty()&&!equal.isEmpty()){
                System.out.println(more.poll()+" "+equal.poll()+" Y");
            }
            while(!less.isEmpty()&&!equal.isEmpty()){
                System.out.println(equal.poll()+" "+less.poll()+" Y");
            }
            while(!more.isEmpty()){
                System.out.println(more.poll()+" "+more.poll()+" N");
            }
            while(!less.isEmpty()){
                System.out.println(less.poll()+" "+less.poll()+" N");
            }
        }
    }
}

E 小红的双好数（hard）

枚举k2进制的所有符合要求的数字，再判断在k1下是否符合要求，时间复杂度O(能过)

import java.util.*;
public class Main{
    static long max=(long)1e18;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long k1=sc.nextLong(),k2=sc.nextLong(),ans=find(k1,k2);
        System.out.println(ans==0?"NO":"YES\n"+ans);
    }
    static long find(long a,long b){
        long p=(long)(Math.log(max)/Math.log(b));
        for(long i=1;i<=(1L<<(p+1));i++){
            long sum=0;
            for(int j=0;j<=p;j++){
                if((i>>j&1L)==1){
                    sum+=pow(b,j);
                }
            }
            if(sum>1&&sum<=max&&check(sum,a)){
                return sum;
            }
        }
        return 0;
    }
    static long pow(long a,long b){
        long ans=1;
        for(int i=0;i<b;i++){
            ans*=a;
        }
        return ans;
    }
    static boolean check(long a,long b){
        while(a!=0){
            if(a%b>1){
                return false;
            }
            a/=b;
        }
        return true;
    }
}

F 小红的数组操作

用有序映射维护最小值，线段树维护区间最小值，时间复杂度``O(nm+qlog(mn))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[][]=new int[n+5][];
        TreeMap<Integer,Integer> map[]=new TreeMap[n+5];
        for(int i=1;i<=n;i++){
            map[i]=new TreeMap<>();
            int m=sc.nextInt();
            a[i]=new int[m+5];
            for(int j=1;j<=m;j++){
                a[i][j]=sc.nextInt();
                inc(map[i],a[i][j],1);
            }
        }
        SegTree st=new SegTree(1,n);
        build(st,map);
        int q=sc.nextInt();
        for(int w=0;w<q;w++){
            int op=sc.nextInt();
            if(op==1){
                int i=sc.nextInt(),j=sc.nextInt(),x=sc.nextInt();
                inc(map[i],a[i][j],-1);
                a[i][j]=x;
                inc(map[i],x,1);
                modify(st,i,map[i].firstKey());
            }
            else{
                 System.out.println(find(st,1,sc.nextInt()));
            }
        }
    }
    static int find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            return st.min;
        }
        else{
            int mid=(l+r)>>1;
            if(b<=mid){
                return find(st.left,a,b);
            }
            else if(a>mid){
                return find(st.right,a,b);
            }
            return Math.min(find(st.left,a,mid),find(st.right,mid+1,b));
        }
    }
    static void modify(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==r){
            st.min=b;
        }
        else{
            int mid=(l+r)>>1;
            if(a<=mid){
                modify(st.left,a,b);
            }
            else{
                modify(st.right,a,b);
            }
            st.min=Math.min(st.left.min,st.right.min);
        }
    }
    static void build(SegTree st,TreeMap<Integer,Integer> map[]){
        int l=st.l,r=st.r;
        if(l==r){
            st.min=map[l].firstKey();
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,map);
            build(st.right,map);
            st.min=Math.min(st.left.min,st.right.min);
        }
    }
    static void inc(TreeMap<Integer,Integer> map,int a,int b){
        map.put(a,map.getOrDefault(a,0)+b);
        if(map.get(a)==0){
            map.remove(a);
        }
    }
}
class SegTree{
    int l,r,min;
    SegTree left,right;
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

G 小红的双排列构造

分类讨论，时间复杂度O(n)

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();
        if(n==1){
            System.out.println(k==2?"1 1":"-1");
        }
        else if(n==2){
            System.out.println(k==0?"-1":k==1?"1 1 2 2":k==2?"2 1 1 2":"1 2 1 2");
        }
        else if(k==0){
            for(int i=1;i<=n;i++){
                System.out.print(i+" "+i+" ");
            }
        }
        else if(k==1){
            System.out.print("1 ");
            for(int i=1;i<=n;i++){
                System.out.print(i+" ");
            }
            for(int i=2;i<=n;i++){
                System.out.print(i+" ");
            }
        }
        else{
            int ans[]=new int[n*2];
            for(int i=0;i<n*2;i++){
                ans[i]=i%n+1;
            }
            for(int i=0,j=n+1-k;i<j;i++,j--){
                ans[i]^=ans[j];
                ans[j]^=ans[i];
                ans[i]^=ans[j];
            }
            for(int a:ans){
                System.out.print(a+" ");
            }
        }
    }
}