牛客周赛84 题解 Java ABCDEFG AK实录

目录

题目地址

做题情况

A 题

B 题

C / D 题

E 题

F / G 题

题目地址

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

做题情况

A 题

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IOS sc=new IOS();static void solve() throws IOException {int a1=sc.nextInt();int a2=sc.nextInt();int a3=sc.nextInt();dduoln(Math.abs(a1-a2)+Math.abs(a2-a3)==0?"Yes":"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 题

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IOS sc=new IOS();static void solve() throws IOException {int n=sc.nextInt();int arr[]=new int[n];HashMap< Integer , Integer >hm=new HashMap<>();for(int i=0;i<n;i++) {arr[i]=sc.nextInt();hm.put(arr[i], hm.getOrDefault(arr[i], 0)+1);}Arrays.sort(arr);int cnt=0;for(int i=0;i<n-1;i++) {cnt+=Math.abs(arr[i]-arr[i+1]);}if(hm.size()==1) {dduoln("1 "+cnt);}else {dduoln("2 "+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());}
}

C / D 题

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IOS sc=new IOS();static void solve() throws IOException {int n=sc.nextInt();int k=sc.nextInt();String str=sc.next();long arr[]=new long[n-1];for(int i=0;i<n-1;i++) {arr[i]=Math.abs(str.charAt(i+1)-str.charAt(i));}long ans=0;// 双指针int i=0;int j=n-2;long a=1;long cnt=0;if(k>n/2) {k=n-k+1;}else {k--;}while(i<=j) {
//			dduoln(a);if(i==j) {cnt+=arr[i]*a;}else {cnt+=arr[i]*a;cnt+=arr[j]*a;	}if(a<k) {a++;}i++;j--;}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 题

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static int MOD=(int) (1e9+7);static ArrayList< ArrayList<Integer> > list;static long dp[]; // 当前节点往下的陡峭值static int father[]; // 当前节点父节点的值static void solve() throws IOException {int n=sc.nextInt();list = new ArrayList<>();for(int i=0;i<n+5;i++) {list.add(new ArrayList<>());}for(int i=0;i<n-1;i++) {int u=sc.nextInt();int v=sc.nextInt();list.get(u).add(v);list.get(v).add(u);}dp=new long[n+1];father=new int[n+1];dfs(1,0);long min=Long.MAX_VALUE;for(int i=2;i<=n;i++) {long t1=dp[i];long t2=dp[1]-dp[i]-Math.abs(i-father[i]);min=Math.min(min, Math.abs(t1-t2));}dduoln(min);} /*** * @param u 当前节点* @param p 父节点*/static void dfs(int u,int p) {father[u]=p;for(int v:list.get(u)) { // v 相邻节点if(v==p)continue;dfs(v,u);dp[u]+= Math.abs(u-v) + dp[v];}}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(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {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 / G 题

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static void solve() throws IOException {int n=sc.nextInt();long a[]=new long[n];for(int i=0;i<n;i++){a[i]=sc.nextLong();}Arrays.sort(a);long ans=0,sum=0;for(int i=0;i<n;i++){ans+=a[i]*i-sum;sum+=a[i];ans%=mod;sum%=mod;}long fenzi=ans%mod*2%mod;long fenmu=n%mod;dduoln(fenzi%mod*pow(fenmu,mod-2,mod)%mod);} // 计算 q 在模 MOD 下的逆元 public static long modInverse(long q) { return pow(q, mod - 2, mod); } // 快速幂取模函数 public static long pow(long base, long exponent, long mod) { long result = 1; base = base % mod; while (exponent > 0) { if ((exponent & 1) == 1) { result =(long)((long) result * base % mod); } exponent = exponent >> 1; base = (long) ((long) base * base % mod); } return result; } 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(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {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());}
}