import java.util.*;

/**

 * 正整数，没有前导0

 * 相邻的数字不能相同

 * 可以被3整除

 * 输入：?12?0?9??

 * 输出：212101902

 */

public class Main {

    static List<Integer> idxs = new ArrayList<>();  // 记录'?'字符的下标

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String line = sc.nextLine();

        char[] s = line.toCharArray();

        int bitSum = 0; // 记录每一位的和

        for (int i = 0; i < s.length; i++) {

            char c = s[i];

            if (c == '?') {

                idxs.add(i);

            } else {

                bitSum += c - '0';

            }

        }

        dfs(s, 0, bitSum);

        System.out.println(String.valueOf(s));

    }

    private static boolean dfs(char[] s, int index, int bitSum) {

        if (index == idxs.size()) {  // 遇到最后一个'?'

            if (bitSum % 3 == 0) {

                return true;

            } else {

                return false;

            }

        }

        int i = idxs.get(index);

        for (int k = 0; k <= 9; k++) {

            if (i == 0 && k == 0) continue; // 第一个元素不能为0

            if (i-1 >= 0 && s[i-1] - '0' == k) continue;  // 元素不能和左右元素相邻

            if (i+1 < s.length && s[i+1] - '0' == k) continue;// 元素不能和左右元素相邻

            s[i] =(char)(k + '0');

            if (dfs(s, index + 1, bitSum + k)) {

                return true;

            }

            s[i] = '?';

        }

        return false;

    }

}

作者：AWeiii

链接：https://www.nowcoder.com/discuss/1055125?type=post&order=recall&pos=&page=0&ncTraceId=&channel=-1&source_id=search_post_nctrack&gio_id=B56220295BC9488455FA8FAE9D10BC82-1663405034525

来源：牛客网

每段栅栏要刷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

思路：差分

91%

#include <bits/stdc++.h>

using namespace std;

vector<long long> F;

vector<long long> S;

int main()

{

    int n, p, q;

    cin >> n >> p >> q;

    vector<long long> l(n);

    vector<long long> r(n);

    vector<long long> t(n);

    long long maxn = 0;

    for (int i = 0; i < n; ++i)

    {

        cin >> l[i];

    }

    for (int i = 0; i < n; ++i)

    {

        cin >> r[i];

        maxn = max(r[i], maxn);

    }

    for (int i = 0; i < n; ++i)

    {

        cin >> t[i];

    }

    F.resize(maxn+2);

    S.resize(maxn+2);

    for (int i = 0; i < n; ++i) {

        if(t[i] == 1) {

            ++F[l[i]];

            --F[r[i]+1];

        } else {

            ++S[l[i]];

            --S[r[i]+1];

        }

    }

    int res = 0;

    for (int i = 2; i < maxn+2; ++i)

    {

        F[i] += F[i - 1];

        S[i] += S[i - 1];

        if(F[i] >= p && S[i] >= q) {

            ++res;

        }

    }

    cout << res;

    return 0;

}

// 需要离散化

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(); int p=sc.nextInt(); int q=sc.nextInt();
sc.nextLine();
int[][] a=new int[n][3];
a[0]=Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
a[1]=Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
a[2]=Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Map<Integer,int[]> map=new HashMap<>();
for(int i=0;i<n;i++){
int[] tmp1=map.getOrDefault(a[0][i]-1, new int[2]);
int[] tmp2=map.getOrDefault(a[1][i], new int[2]);
tmp1[a[2][i]-1]--;
tmp2[a[2][i]-1]++;
map.put(a[0][i]-1, tmp1);
map.put(a[1][i], tmp2);
}
List<Map.Entry<Integer,int[]>> list=new ArrayList<>();
for(Map.Entry<Integer,int[]> v:map.entrySet()){
list.add(v);
}
Collections.sort(list,(x, y)->{
return y.getKey()-x.getKey();
});
// System.out.println(list.size());
int res=0;
int curp=0, curq=0;
int lastk=-1;
for(Map.Entry<Integer,int[]> v : list){
int tmpk=v.getKey();
//System.out.println(tmpk);
int[] tmpv=v.getValue();
if(lastk==-1){
curp+=tmpv[0];
curq+=tmpv[1];
lastk=tmpk;
}else{
if(curp>=p&&curq>=q){
res+=lastk-tmpk;
}
curp+=tmpv[0];
curq+=tmpv[1];
lastk=tmpk;
}
}
System.out.println(res);
}
}