PDD提前批08-03笔试 题解 分享

本文题解仅用于个人学习与分享，不代表任何公司立场。

由于缺少线上评测环境，题解可能无法保证完全正确，但整体思路应当是可行的。

如果内容对您有所帮助，欢迎点个赞支持！

目前拼多多2026年校园招聘已经开启 欢迎通过如下链接投递

https://careers.pddglobalhr.com/campus/grad?t=6U8PSGz529

幸运年份

思路

首先 先看数据范围 最大数据量是1e7 因此可以直接暴力 暴力的思路直接枚举判断即可

接下来考虑构造的解法

1. 首先 判断一下能不能是不是已经符合条件 （要注意这里要的是大于 因此传参要+1）
2. 对于不符合条件的位置 即第一个出现重复的位置 考虑对其进行加操作来尝试构造一个
   1. 尝试对当前位置加来构造一个 当前位及之前位都不重复的数字
   2. 如果不行 一直往前推 直到找到
      1. 如果找不到 证明当前位数不能构造出目标的数据 需要增加一位 这样结果就确定了 根据要求从 1023456789 这串数字中取前几位作为结果
      2. 找到了 开始从高到低 从0-9依次填充剩余位数 要记得不能跟高位数字相同

代码

暴力做法

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int year = in.nextInt();
            year++;
            for(;year<=1234567;++year){
                if(check(year)){
                    System.out.println(year);
                    break;
                }
            }
        }
    }
    private static boolean check(int year){
        int[] cnt = new int[10];
        while(year>0){
            cnt[year%10]++;
            if(cnt[year%10]>1){
                return false;
            }
            year/=10;
        }
        return true;
    }
    private static int bf(int year){
        while(true){
            int temp = year;

        }
    }
}

构造

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class A {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int year = in.nextInt();
            System.out.println(cal(year + 1));
        }
    }

    private static int cal(int year) {
        List<Character> list = new ArrayList<>();
        int temp = year;
        // 分解
        while (temp > 0) {
            list.add((char) ('0' + (temp % 10)));
            temp /= 10;
        }
        int n = list.size();
        // 检查
        int needAddIndex = n;
        int[] cnt = new int[10];
        for (int i = n - 1; i >= 0; i--) {
            char c = list.get(i);
            ;
            if (cnt[c - '0'] > 0) {
                needAddIndex = i;
                cnt[c - '0']++;
                break;
            }
            cnt[c - '0']++;
        }
        // 如果符合条件 直接返回
        if (needAddIndex == n) {
            return year;
        }
        // 不符合条件 尝试构造
        for (; needAddIndex < n; ++needAddIndex) {
            int d = list.get(needAddIndex) - '0';

            while (d < 10 && cnt[d] > 0) {
                ++d;
            }
            if (d < 10) {
                list.set(needAddIndex, (char) ('0' + d));
                break;
            }
            cnt[list.get(needAddIndex) - '0']--;

        }
        // 构造不出来 增加1位
        if (needAddIndex == n) {
            n = n + 1;
            int ans = 10;
            if (n == 2) {
                return ans;
            }
            for (int i = 3; i <= n; ++i) {
                ans = ans * 10 + i - 1;
            }
            return ans;
        }
        int ans = 0;
        cnt = new int[10];
        // 可以构造 先填充高位
        for (int i = n - 1; i >= needAddIndex; --i) {
            ans = ans * 10 + (list.get(i) - '0');
            cnt[list.get(i) - '0']++;
        }
        int base = 0;
        // 填充低位
        for (int i = needAddIndex - 1; i >= 0; --i) {
            while (cnt[base] > 0) {
                ++base;
            }
            ans = ans * 10 + base;
            cnt[base]++;
            base++;
        }
        return ans;
    }
}

能源站开启

思路

算一下数据范围 大概是bfs 1e6 可以暴力 直接暴力枚举选取点 然后暴力bfs计算最大能开启多少能源站即可 别忘了开long

代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class B {
    public static long[][] map;
    public static int[] x;
    public static int[] y;
    public static long[] r;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            map = new long[n][n];
            x = new int[n];
            y = new int[n];
            r = new long[n];
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
                r[i] = sc.nextLong();
                r[i] *= r[i];
            }
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    long d = (long) (x[i] - x[j]) * (x[i] - x[j]) + (long) (y[i] - y[j]) * (y[i] - y[j]);
                    map[i][j] = map[j][i] = d;
                }
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans = Math.max(ans, bfs(i, n));
            }
            System.out.println(ans);

        }
    }

    private static int bfs(int x, int n) {
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        queue.add(x);
        visited[x] = true;
        while (!queue.isEmpty()) {
            ++cnt;
            int top = queue.poll();
            for (int i = 0; i < n; ++i) {
                if (map[top][i] <= r[top] && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
        return cnt;
    }
}

单峰序列

思路

考虑枚举每一位置作为峰顶的花费 从中取最小值 但是看数据范围 暴力肯定是不行的 因此考虑维护四个数组来优化时间

minValueFromLeft 表示从左边开始 如果要满足单调递增序列 当前位置最小值是多少

costFromLeft 表示从左边开始 如果要满足单调递增序列 最小花费是多少

minValueFromRight 和 costFromRight 也是同理

那么 当前位置作为峰顶的花费就是

其中 就是当前值作为峰顶的最小花费

代码

import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextLong();
        }
        long[] minValueFromLeft = new long[n];
        long[] minValueFromRight = new long[n];
        long[] costFromLeft = new long[n];
        long[] costFromRight = new long[n];

        minValueFromLeft[0] = a[0];
        for (int i = 1; i < n; ++i) {
            if (a[i] > minValueFromLeft[i - 1]) {
                minValueFromLeft[i] = a[i];
                costFromLeft[i] = costFromLeft[i - 1];
            } else {
                minValueFromLeft[i] = minValueFromLeft[i - 1] + 1;
                costFromLeft[i] = costFromLeft[i - 1] + minValueFromLeft[i] - a[i];
            }
        }
        minValueFromRight[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (a[i] > minValueFromRight[i + 1]) {
                minValueFromRight[i] = a[i + 1];
                costFromRight[i] = costFromRight[i + 1];
            } else {
                minValueFromRight[i] = minValueFromRight[i + 1] + 1;
                costFromRight[i] = costFromRight[i + 1] + minValueFromRight[i] - a[i];
            }
        }
        long ans = Long.MAX_VALUE;

        for (int i = 1; i < n - 1; ++i) {
            long cost = Math.max(0, Math.max(minValueFromLeft[i - 1], minValueFromRight[i + 1]) + 1 - a[i]);
            ans = Math.min(ans, costFromLeft[i - 1] + cost + costFromRight[i + 1]);
        }
        System.out.println(ans);
    }
}

补给包规划

思路

本题思路是二分+DAG(有向边且保证无环) 首先二分 过程中最多拿多少补给包 然后判断是否可行 可行性判断用了拓扑排序的思想 只不过这里保证有向边起点一定小于终点 可以写的稍微简单一点

代码

import java.util.*;

public class D {
    static int n;
    static int m;
    static long[] supplyPackageNum ;
    static List<List<Node>> map ;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        map = new ArrayList<List<Node>>();
        long R = 0;
        supplyPackageNum = new long[n+1];
        for(int i = 1; i <= n; i++){
            supplyPackageNum[i] = in.nextInt();
            R+=supplyPackageNum[i];
        }
        for(int i = 0; i <= n; i++){
            map.add(new ArrayList<>());
        }
        for(int i = 0;i<m;++i){
            int x = in.nextInt();
            int y = in.nextInt();
            int limit =  in.nextInt();
            map.get(x).add(new Node(y,limit));
        }
        R++;
        long max = R;
        long L = 0;
        while(L<R){
            long mid = (L+R)>>1;
            if(check(mid)){
                R = mid;
            }else{
                L = mid+1;
            }
        }
        if(L==max){
            L = -1;
        }
        System.out.println(L);

    }

    static boolean check(long mid){
        long[] cost = new long[n+1];
        Arrays.fill(cost,-1);
        cost[1] = Math.min(mid,supplyPackageNum[1]);
        for(int i = 1; i <= n; i++){
            if(cost[i] == -1){
                continue;
            }
            long now = cost[i];
            for(int j = 0;j<map.get(i).size();j++){
                Node y = map.get(i).get(j);
                if(now>=y.limit){
                    cost[y.value] = Math.max(cost[y.value],Math.min(now+supplyPackageNum[y.value],mid));
                }
            }
            if(cost[n]>=0){
                return true;
            }
        }
        return false;
    }

}


class Node{
    int value;
    long limit;
    public Node(int value, long limit) {
        this.value = value;
        this.limit = limit;
    }
    public Node() {}
}