#牛客春招刷题训练营# + https://www.nowcoder.com/discuss/726480854079250432

题目地址

https://www.nowcoder.com/practice/1221ec77125d4370833fd3ad5ba72395?channelPut=w25springcamp

https://www.nowcoder.com/practice/49e772ab08994a96980f9618892e55b6?channelPut=w25springcamp

https://www.nowcoder.com/practice/74cb703f25dc4956acb3b08028a1f4b4?channelPut=w25springcamp

字符个数统计

喜欢切数组的红

很经典的 dp

爬楼梯

递推写法

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        long dp[]=new long[31+5];
        dp[1]=1;
        dp[2]=1;
        dp[3]=2;
        for(int i=4;i<31+5;i++){
            dp[i]=dp[i-2]+dp[i-1];
        }
        int a=in.nextInt();
        System.out.println(dp[a]);
    }
}

高精度整数加法

直接使用高精度类 BigInteger

import java.math.BigInteger;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
            BigInteger b1=new BigInteger(in.next());
            BigInteger b2=new BigInteger(in.next());
            System.out.println(b1.add(b2));
    }
}

喜欢切数组的红

可以存一下前缀和为 3 的集合

再存一下后缀和为 3 的集合

然后遍历

看情况符合

跑了 500ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        long arr[] = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
            sum += arr[i];
        }
        if (sum % 3 != 0) {
            System.out.println("0");
            return;
        }
//        System.out.println(sum/3);
        int cnt = 0;
        long k = sum / 3; // 要达到的数
//        System.out.println(k);

        ArrayList<Integer>list1 =new ArrayList<>(); // 前
        ArrayList<Integer>list2 =new ArrayList<>(); // 后

        long ans1=0;
        boolean judge1=false;
        for(int i=0;i<n;i++){
            if(judge1==false&&arr[i]>0){
                judge1=true;
            }
            ans1+=arr[i];
            if(ans1==k&&judge1==true){
                list1.add(i);
            }
        }

        long ans2=0;
        boolean judge2=false;
        for(int i=n-1;i>=0;i--){
            if(judge2==false&&arr[i]>0){
                judge2=true;
            }
            ans2+=arr[i];
            if(ans2==k&&judge2==true){
                list2.add(i);
            }
        }

        Collections.sort(list1);
        Collections.sort(list2);

//        for (Integer i : list1) {
//            System.out.print(i+" ");
//        }
//        System.out.println();
//        for (Integer i : list2) {
//            System.out.print(i+" ");
//        }
//        System.out.println();

        for(int i=0;i<list1.size();i++){
            long a1=list1.get(i);
            for(int j=0;j<list2.size();j++){
                long a2=list2.get(j);
                if(a2>a1+1){
                    for(long ii=a1+1;ii<=a2-1;ii++){
                        if(arr[(int) ii]>0){
                            cnt++;
                            break;
                        }
                    }
                }
            }
        }

        System.out.println(cnt);
    }
}