题解 | 牛客周赛82 Java ABCDEF

题目地址

https://ac.nowcoder.com/acm/contest/103674#question

做题情况

A 题

判断字符串第一个字符和第三个字符是否相等

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
       String str=sc.next();
       if(str.charAt(0)==str.charAt(2)) {
    	   dduoln("YES");
       }else {
    	   dduoln("NO");
       }
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//         t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

B 题

找是否出现相同元素

将元素放到 TreeSet 集合里面

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;
    public static void solve() throws IOException {
        
    	int n=sc.nextInt();
    	TreeSet<Integer>ts=new TreeSet<>();
    	for(int i=0;i<n;i++) {
    		int a=sc.nextInt();
    		ts.add(a);
    	}
    	
    	if(ts.size()!=n) {
    		dduoln("NO");
    		return;
    	}
    	
    	dduoln("YES");
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

C 题

在 B 题的基础上进行结构体排序

按照索引大小的规则来排序元素

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;
    public static void solve() throws IOException {
        
    	int n=sc.nextInt();
    	ArrayList<int[]>l=new ArrayList<>();
    	TreeSet<Integer>ts=new TreeSet<>();
    	for(int i=0;i<n;i++) {
    		int a=sc.nextInt();
    		ts.add(a);
    		l.add(new int[] {i+1,a});
    	}
    	
    	if(ts.size()!=n) {
    		dduoln("NO");
    		return;
    	}
    	
    	dduoln("YES");
    	Collections.sort(l,(a,b) -> {
    		return a[1]-b[1];
    	});
    	
    	for(int p[]:l) {
    		dduo(p[0]+" ");
    	}
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

D 题

首先找规律

我们发现给出的元素只能是递减的

最后一个元素只能是 1

之后我们可以确定的是

如果一个元素与前面这个元素不同这个数就是确定的而后面跟这个数相同的数就都是不确定的

我们只需要统计这段重复的数字和可以填入的数字的排列组合就行

其中可选的数是排列的最大值n - 比重复数字小的数(不能填) -前面有多少数 (注意要把重复的数空下来)

重复的数我们计数出来的

然后组合数 Anm

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
    	int n=sc.nextInt();
    	long arr[]=new long[n];
    	for(int i=0;i<n;i++) {arr[i]=sc.nextLong();}
        
    	long ans=arr[0];
    	long cnt=1;
    	
    	long a=0; // 重复的数
    	
    	for(int i=1;i<n;i++) {
    		if(arr[i]>ans) {
    			dduoln("0");
    			return;
    		}
    		if(arr[i]==ans) {
    			a++;
    		}
    		if(arr[i]<ans) {
    			long b= (n-arr[i-1]) -(i-a) +1; // 可选的数
    			if(b<a) {
    				dduoln("0");
        			return;
    			}else if(a!=0&&b!=0){
    				for(long j=b;j>=b-a+1;j--) {
    					cnt*=j;
    					cnt%=MOD;
    				}
    			}
    			ans=arr[i];
    			a=0;
    		}
    	}
    	
    	if(ans!=1) {
    		dduoln("0");
			return;
    	}
    	
    	for(int i=1;i<=a;i++) {
    		cnt*=i;
			cnt%=MOD;
    	}
    	
    	dduoln(cnt);
    	
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

E 题

使用优先队列来维护状态

优先队列采用的是大顶堆(数值大的元素优先级高)

通过优先队列给数组赋值

对于数组 a 我们维护一个数组

数组的索引i 的值表示的是前 i 个元素最小的 m 个数的和

通过优先队列筛选出前 i 个元素数值大的元素并进行移除

数组 b 反向操作就行

最后跑一遍 n 更新最大值

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        int n = sc.nextInt();
        int m = sc.nextInt();

        long[] a = new long[n+1];
        long[] b = new long[n+1];
        long[] pre = new long[n+1];
        long[] suf = new long[n+1];
        
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }

        for (int i = 1; i <= n; i++) {
            b[i] = sc.nextLong();
        }

        PriorityQueue<Long> q1 = new PriorityQueue<>(Collections.reverseOrder());
        long sum1 = 0;
        for (int i = 1; i <= n; i++) {
            q1.add(a[i]);
            sum1 += a[i];
            if (q1.size() > m) {
                sum1 -= q1.poll();
            }
            if (q1.size() == m) {
                pre[i] = sum1;
            }
        }

        PriorityQueue<Long> q2 = new PriorityQueue<>(Collections.reverseOrder());
        long sum2 = 0;
        for (int i = n; i >= 1; i--) {
            q2.add(b[i]);
            sum2 += b[i];
            if (q2.size() > m) {
                sum2 -= q2.poll();
            }
            if (q2.size() == m) {
                suf[i] = sum2;
            }
        }

        long ans = Long.MAX_VALUE;
        for (int k = m; k <= n - m; k++) {
            ans = Math.min(ans, pre[k] + suf[k + 1]);
        }

        dduoln(ans);
    	
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

F 题

相邻的两个数不能一样

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;
    public static void solve() throws IOException {
        
    	int n = sc.nextInt();

        ArrayList<Integer> a = new ArrayList<>();
        a.add(1);

        int j = 2; 	// 种类数
        while (a.size() < n) {
            a.add(j);
            j++;
            int nn = a.size();
            for (int i = 0; i < nn - 1; i++) {
                a.add(a.get(i));
            }
        }

        System.out.println(j - 1);
        for (int i = 0; i < n; i++) {
            System.out.print(a.get(i) + " ");
        }
    	
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}