题解 | 牛客周赛82 Java ABCDEF

目录

题目地址

做题情况

A 题

B 题

C 题

D 题

E 题

F 题

牛客竞赛主页

题目地址

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

做题情况

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());}
}

牛客竞赛主页

她说喜欢是装的的比赛主页