当前位置： 首页 > article >正文

题解 | 牛客周赛82 Java ABCDEF

article 2025/3/3 19:04:40

目录

题目地址

做题情况

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

牛客竞赛主页

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


http://www.kler.cn/a/569122.html

相关文章：

  • 【51单片机】快速入门
  • 软件工程---基于构件的软件工程
  • 攻防世界WEB（新手模式）18-easyphp
  • node项目前后端密码加密传输及存储方案
  • 【终篇】基于C++的通讯录管理系统（完整源码）
  • 7-1JVMCG垃圾回收
  • 【西瓜书《机器学习》前三章内容通俗理解】
  • Golang语言特性
  • 【零基础C语言】第四节 数组
  • 网页制作09-html,css,javascript初认识のhtml如何使用表单
  • STM32 微控制器库RCC_ClkInitTypeDef结构参数介绍
  • （十一）基于vue3+mapbox-GL实现模拟高德实时导航轨迹播放
  • C# 类库打包dll文件
  • 数据库原理与使用基础教程
  • 安全测试之五：SQL Server注入漏洞几个实例
  • Linux学习笔记1
  • 差分矩阵问题
  • 什么是预训练语言模型下游任务？
  • 创建一个MCP服务器，并在Cline中使用，增强自定义功能。
  • 通俗解释机器学习中的召回率、精确率、准确率