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 {
        // todo
    	
    	String 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 {
        // todo
    	
    	int 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);
    	
    }
    
    /*
     2
     
	 7
	 4 6 1
	 12 14 2
	 5 11 3
	 1 6 4
	 11 13 4
	 4 7 5
	 3 5 6
	 4 7
	 
	 1
	 0 4 1
	 1 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 {
        // todo
    	
        long 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;
        		// 最后操作y
        		y=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 {
        // todo
    	
    	int 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 36
	1 211
	4 9
	10 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());
    }
}