2024CCPC吉林省赛长春邀请赛 Java 做题记录

目录

I. The Easiest Problem

G. Platform Game

L. Recharge

E. Connected Components

---

I. The Easiest Problem

签到题 直接输出 21 即可

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (998244353);static int n;static int arr[];static boolean visited[];static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();static int map[][];/*** @throws IOException*/private static void solve() throws IOException {// todoString str="Scan the QR code to sign in now.";int cnt=0;for(int i=0;i<str.length();i++) {char c=str.charAt(i);if(c>='a'&&c<='z')cnt++;}dduoln(cnt);}// Java // 判断是不是回文字符串public static boolean isPalindrome(String str) {if (str == null) {return false;}int left = 0;int right = str.length() - 1;while (left < right) {if (str.charAt(left) != str.charAt(right)) {return false;}left++;right--;}return true;}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);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
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());}
}

G. Platform Game

模拟题 自定义比较器

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (998244353);static int n;static int arr[];static boolean visited[];static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();static int map[][];/*** @throws IOException*/private static void solve() throws IOException {// todoint n=sc.nextInt();ArrayList<Long[]>list=new ArrayList<>();for(int i=0;i<n;i++) {long l=sc.nextLong(); // 左端long r=sc.nextLong(); // 右端long y=sc.nextLong(); // 高度list.add(new Long[] {l,r,y});}Collections.sort(list,(o1,o2)->{if(o1[2]==o2[2]) {return Long.compare(o1[0], o2[0]);}else {return Long.compare(o2[2], o1[2]);}});//    	for(Long arr[]:list) {
//    		dduoln(arr[0]+" "+arr[1]+" "+arr[2]);
//    	}long x=sc.nextLong(); // 初始横坐标long h=sc.nextLong(); // 初始高度for(Long arr[]:list) {// 当前平台的高度long height = arr[2];if(height>h)continue;else h=height;// 当前平台的左端点long left = arr[0]; // 当前平台的右端点long right = arr[1];if(x>left&&x<right) {x=right;}else {continue;}}dduoln(x);}/*274 6 112 14 25 11 31 6 411 13 44 7 53 5 64 710 4 11 5* */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);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
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());}
}

L. Recharge

一道贪心模拟

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (998244353);static int n;static int arr[];static boolean visited[];static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();static int map[][];/*** @throws IOException*/private static void solve() throws IOException {// todolong k=sc.nextLong(); // 容量long x=sc.nextLong(); // 小房间long y=sc.nextLong(); // 大房间long cnt=0;if(k==1) {cnt+=x;cnt+=y;dduoln(cnt);return;}if(k%2==0) {// 偶数long a1=k/2; // 需要a1个大房间 正好进行充能//        	dduoln(a1);if(y%a1==0) {// y被全耗尽cnt+=y/a1;// 最后操作yy=0; }else {// y还剩下全耗尽long a2 = y / a1; // 可以充能几组cnt += a2;y -= a2*a1; // 大房间还剩下多少个}// 首先把大房间消耗完long a3=k-y*2; // 需要多少个小房间抵消大房间 //        	dduoln(a3);if(a3>x) {}else {cnt++;x-=a3;cnt+=x/k;}}else if(k%2!=0){// 奇数 较为复杂// 9 4*2+1// 凑最优解// 凑整 long a4=(k-1)/2; // 需要a4个大房间  1个小房间 正好进行充能long min1=x/1;long min2=y/a4;long min=Math.min(min1,min2);cnt+=min;x-=min*1;y-=min*a4;//        	dduoln(x+" "+y);//        	dduoln(cnt);if(y==0) {// 没有大房间了cnt+=x/k;}else if(x==0){// 没有小房间了cnt+=y/(k/2+1);}else {// 大房间 小房间都有// 先凑一个//        		dduoln(x+" "+y);long a5=k-y*2; // 需要a5个小房间凑整if(a5>x) {}else {cnt++;x-=a5;y=0;cnt+=(x/k);}}//        	dduoln(cnt);}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() {System.out.println("");}static <T> void dduoln(T t) {System.out.println(t);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
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());}
}

E. Connected Components

数据结构

单调栈 模版题

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (998244353);static int n;static int arr[];static boolean visited[];static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();static int map[][];/*** @throws IOException*/private static void solve() throws IOException {// todoint n=sc.nextInt();ArrayList<Long []>list=new ArrayList<>();for(int i = 1 ; i<=n ; i++) {long a=sc.nextLong();long b=sc.nextLong();list.add(new Long[]{ (a-i) , (b-i) });}Collections.sort(list,(o1,o2)->{if(o1[0]==o2[0]) {return Long.compare(o2[1], o1[1]);}return Long.compare(o1[0], o2[0]);});//    	for(Long[] arr : list) {
//    		dduoln(arr[0]+" "+arr[1]);
//    	}// 单调栈Stack<Long> stack=new Stack<>();for (int i = 0; i < n; i++) {Long min = (long) -1e18;Long num=list.get(i)[1];int flag = 0;if (!stack.empty()) {min = stack.peek();}if (!stack.empty() && stack.peek() >= num) {flag = 1;stack.pop();}if (flag == 1) {stack.push(min);} else if(flag == 0){stack.push(num);}}dduoln(stack.size());}/**4-6 361 2114 910 8*/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);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
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());}
}