9.17 滴滴笔试

1、dfs（80%）

没找出问题在哪

小昱做了很久的实验得到了一个用正整数表示的实验数据，并记录在了纸上。但是由于做完实验太过激动，他一不小心把墨水打翻溅在了纸上，导致数据中一些位置上的数字看不清楚。他仍记得这个数据有以下三个特征：

这个数是正整数，且没有前导零（即数的最高位不是0）
这个数任意两个相邻数位的数字不同
这个数可以被3整除

他现在很关心在满足以上特征的条件下，这个数字最小为多少。

输入：
?12?0?9??
输出：
212101902

import java.util.Scanner;
public class Main {
    static String num;
    static final int base = 3;
    static char[] ans;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        num = scanner.next();
        n = num.length();

        ans = new char[n];
        dfs(0, 0, '#');
        System.out.println(new String(ans));
    }

    static boolean dfs(int start, int remain, char front) {
        if (start == n) {
            return remain == 0;
        }
        char ch = num.charAt(start);
        remain *= 10;
        if (ch != '?') {
            ans[start] = ch;
            return dfs(start + 1, (ch - '0' + remain) % base, ch);
        } else {
            for (char c = '0'; c <= '9'; ++c) {
                if (start == 0 && c == '0') {
                    continue;
                }
                char back = start < n - 1 ? num.charAt(start + 1) : '#';
                if (c != front && c != back) {
                    ans[start] = c;
                    if (dfs(start + 1, (c - '0' + remain) % base, c)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

2、差分数组（0%）

一直在写线段树，没写出来。结果可以用差分,下来写了一下，不知道对不对

小明正在刷栅栏。为了使得栅栏在经过风吹雨打后依然不掉色，需要用两种不同的油漆刷栅栏。
栅栏被按顺序编号为1到1000000000。每一段栅栏需要至少刷 p 遍的1号油漆和 q 遍的2号油漆后才能保证长时间不掉色。
每次刷漆都会使用某种类型的油漆，并将编号属于某个区间内的栅栏都刷上这种油漆。
现在给出每次刷漆的栅栏编号范围和油漆种类，请你求出有多少段栅栏能够长时间不掉色。 * 输入描述
第一行有三个正整数n,p,q(1<=n<=100000,1<=p,q<=n)，代表刷漆的次数，以及两个参数 p 和 q。
第二到四行给出了一个大小为3*n的矩阵，第 i 列的三个数从上到下记为l,r,t(1<=l,r<=1000000000,1<=t<=2)， * 代表第i次刷漆将编号在 l 到 r 之间的栅栏刷了一遍 t号油漆。
测试用例：

输入：
5 2 2
1 1 2 3 2
3 5 4 5 4
1 2 1 1 2
输出：
3

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main3 {
    static final int N = (int) 1e10;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int p = scanner.nextInt();
        int q = scanner.nextInt();
        int[] l = new int[n];
        int[] r = new int[n];
        int[] type = new int[n];
        // N很大，采用离散化
        Map<Integer, Integer> ones = new HashMap<>();
        Map<Integer, Integer> twos = new HashMap<>();
        getInput(l, scanner);
        getInput(r, scanner);
        getInput(type, scanner);
        for (int i = 0; i < n; i++) {
            if (type[i] == 1) {
                ones.put(l[i], ones.getOrDefault(l[i], 0) + 1);
                ones.put(r[i] + 1, ones.getOrDefault(r[i] + 1, 0) - 1);
            } else {
                twos.put(l[i], ones.getOrDefault(l[i], 0) + 1);
                twos.put(r[i] + 1, ones.getOrDefault(r[i] + 1, 0) - 1);
            }
        }
        int ans = 0;
        int oneSum = 0, twoSum = 0;
        for (int i = 1; ; i++) {
            oneSum += ones.getOrDefault(i, 0);
            twoSum += twos.getOrDefault(i, 0);
            if (oneSum >= p && twoSum >= q) {
                ans++;
            }
            if (i == N) {
                break;
            }
        }
        System.out.println(ans);
    }

    static void getInput(int[] nums, Scanner scanner) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = scanner.nextInt();
        }
    }
}

#滴滴##滴滴笔试##滴滴校招#