跳到内容
当前位置:首页>笔试招聘真题>【春招笔试】2026.03.08滴滴真题解析

【春招笔试】2026.03.08滴滴真题解析

  • 2026-11-14 23:09:55
【春招笔试】2026.03.08滴滴真题解析

滴滴-2026.03.08

这套滴滴题是很典型的“两道题都要先把问题压扁”的组合。

第一题表面上是在问很多个阈值下的统计结果,真正该抓的是“最终到底出现了哪些正高度”;第二题表面上是三元组计数,真正该做的是固定前两个量后一次算完第三个量的贡献。

题目 1:仓储层位观测

这题的关键不在于把每个  都算出来,而在于意识到答案只和“出现过多少种正高度”有关。

一旦把这一点想清楚,后面就是标准的区间加离散化:把所有会改变高度的端点抠出来,再在压缩后的坐标上做差分。


题目 2:三路投放方案统计

真正的突破口是把三层枚举降成两层。固定  之后, 的可选范围可以直接由两个上界取最小值。

难点主要在复杂度判断。看到  的上界大约是  以后,就知道总枚举次数是一段调和级数,这题就落回了可做范围。

1. 仓储层位观测

问题描述

K 小姐在整理一条很长的仓储通道。通道里一共有  个货位,编号为  到 。一开始,每个货位上都没有箱子。

接下来会有  批补货。第  批补货会把  个相同的箱子,同时加到编号位于  的每一个货位上。于是,所有补货结束后,每个货位都会得到一个最终高度。

现在定义函数  表示:最终高度 大于等于 的货位有多少个。

K 小姐不关心  的具体变化过程,她只想知道:当  从  一直取到很大的值时, 一共会出现多少种不同的取值。

输入格式

第一行输入两个整数  和 ,分别表示货位数量与补货批次数。

接下来有  行,每行输入三个整数 、、,表示这一批补货会让区间  中的每个货位高度增加 。

输出格式

输出一个整数,表示  这一长串数值里,不同取值的总个数。

样例输入

10 4
7 8 5
5 7 5
1 2 1
3 5 3

样例输出

6

数据范围

  • >

    。

  • >

    。

  • >

    。

  • >

    。

样例
解释说明
样例 1
最终高度依次为 。正高度只有  这  种,所以  会出现  种不同取值,最后那个  来自所有货位都不够高时的 。

题解

真正麻烦的地方,不是去算某一个固定的 ,而是要看它一共会变化出多少个不同答案。

先盯住“什么时候会变”。假设某个货位的最终高度是 ,那么当阈值  从小到大增加时,这个货位会在  的那一刻从统计里消失。在别的位置,它对  没影响。于是, 只会在“跨过某个真实出现过的正高度”时发生变化。

这就得到一个非常关键的结论:答案其实等于“最终所有货位里,正高度有多少种不同取值”再加上 。多出来的这个 ,对应的是阈值继续升高后,所有货位都被删空,此时 。

所以题目被改写成:想办法找出所有 出现过的不同正高度。

问题又来了, 最大能到 ,显然不可能真的把每个货位都算出来。这里要利用区间加的结构:所有变化只会发生在每次补货的左端点 ,以及右端点后一位 。把这些位置和边界 、 全部收集起来、排序去重后,相邻两个坐标之间的整段货位,最终高度一定相同。这样一来,本来可能有  个位置,现在只剩下不超过  个关键分界点。

接着在压缩后的坐标上做差分。对一条操作  加上 ,只需要在  对应的位置加上 ,在  对应的位置减去 。最后扫一遍前缀和,就能得到每个压缩段的真实高度。

扫的过程中,不需要记录整段有多长,因为题目只问“出现过哪些高度”,而不是每个高度出现了多少次。只要某一段的高度大于 ,就把这个高度丢进集合里。集合大小记为 ,最终答案就是 。

为什么这样做一定正确?原因分两步:

第一,坐标压缩不会丢信息。因为任意两个相邻关键点之间,再也没有操作端点穿过,所以这一整段货位经历的所有补货完全一样,最终高度当然也完全一样。

第二,答案和不同正高度的个数一一对应。若正高度从小到大是 $h_1<h_2<\cdots<h_k$,那么当阈值依次跨过 $h_1,h_2,\dots,h_k$="" 时,至少会有一批货位退出统计,$f(x)$="" 会严格下降;而在两个相邻高度之间,满足“高度至少为="" $x$”的货位集合并不会变化。因此,$f(x)$="" 的不同取值正好是这="" $k$="" 次下降形成的="" 个值,再加上最后的="" $0$,总数就是="" $k+1$。<="" p="">

复杂度方面,坐标数不超过 。排序和每次二分定位的总复杂度是 ,扫前缀和是 ,空间复杂度也是 。在  的范围内完全可以通过。

参考代码

  • >
    Python
import sys
from bisect import bisect_left

input = lambda: sys.stdin.readline().strip()


defmain():
    n, m = map(int, input().split())

# 收集所有会改变高度的关键位置。
    pos = [1, n + 1]
    ops = []
for _ in range(m):
        l, r, d = map(int, input().split())
        rp = r + 1
        ops.append((l, rp, d))
        pos.append(l)
        pos.append(rp)

# 坐标压缩后,相邻关键点之间的整段高度相同。
    pos = sorted(set(pos))
    dif = [0] * (len(pos) + 1)

defidx(val):
# 找到原坐标在压缩数组中的位置。
return bisect_left(pos, val)

for l, rp, d in ops:
        dif[idx(l)] += d
        dif[idx(rp)] -= d

    cur = 0
    seen = set()
for i in range(len(pos) - 1):
# 前缀和就是当前压缩段的真实高度。
        cur += dif[i]
if cur > 0:
# 只关心“出现过哪些正高度”,长度无关紧要。
            seen.add(cur)

# 多出来的 1,对应阈值足够大时的 f(x)=0。
    print(len(seen) + 1)


if __name__ == "__main__":
    main()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

using ll = longlong;

intget_id(constvector<ll>& pos, ll val){
return lower_bound(pos.begin(), pos.end(), val) - pos.begin();
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

    ll n;
int m;
cin >> n >> m;

vector<ll> pos;
    pos.reserve(m * 2 + 2);
    pos.push_back(1);
    pos.push_back(n + 1);

vector<array<ll, 3>> ops;
    ops.reserve(m);

for (int i = 0; i < m; ++i) {
        ll l, r, d;
cin >> l >> r >> d;
        ll rp = r + 1;
        ops.push_back({l, rp, d});
        pos.push_back(l);
        pos.push_back(rp);
    }

// 压缩所有关键坐标,减少需要真正扫描的位置数。
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());

// dif 记录压缩坐标上的差分变化量。
vector<ll> dif(pos.size() + 1, 0);
for (constauto& op : ops) {
int l_id = get_id(pos, op[0]);
int r_id = get_id(pos, op[1]);
        dif[l_id] += op[2];
        dif[r_id] -= op[2];
    }

    ll cur = 0;
set<ll> seen;
for (size_t i = 0; i + 1 < pos.size(); ++i) {
// 每个压缩段里的所有货位,高度完全一致。
        cur += dif[i];
if (cur > 0) {
            seen.insert(cur);
        }
    }

// 不同正高度个数 + 1,就是答案。
cout << static_cast<ll>(seen.size()) + 1 << '\n';
return0;
}
  • >
    Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeSet;

publicclassMain{
staticclassFastScanner{
privatefinal BufferedInputStream in = new BufferedInputStream(System.in);
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

longnextLong()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ');

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
return val * sign;
        }
    }

staticintlowb(long[] arr, int size, long val){
int l = 0;
int r = size;
while (l < r) {
int mid = (l + r) >>> 1;
if (arr[mid] < val) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
return l;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
long n = fs.nextLong();
int m = (int) fs.nextLong();

long[] raw = newlong[m * 2 + 2];
long[] ls = newlong[m];
long[] rs = newlong[m];
long[] ds = newlong[m];

int rc = 0;
        raw[rc++] = 1;
        raw[rc++] = n + 1;

for (int i = 0; i < m; i++) {
long l = fs.nextLong();
long r = fs.nextLong();
long d = fs.nextLong();
long rp = r + 1;

            ls[i] = l;
            rs[i] = rp;
            ds[i] = d;
            raw[rc++] = l;
            raw[rc++] = rp;
        }

// 排序去重后,相邻坐标之间就是等高段。
        Arrays.sort(raw, 0, rc);
long[] pos = newlong[rc];
int pc = 0;
for (int i = 0; i < rc; i++) {
if (i == 0 || raw[i] != raw[i - 1]) {
                pos[pc++] = raw[i];
            }
        }

// dif 记录每个关键点处的高度增减。
long[] dif = newlong[pc + 1];
for (int i = 0; i < m; i++) {
int lId = lowb(pos, pc, ls[i]);
int rId = lowb(pos, pc, rs[i]);
            dif[lId] += ds[i];
            dif[rId] -= ds[i];
        }

long cur = 0;
        TreeSet<Long> seen = new TreeSet<>();
for (int i = 0; i + 1 < pc; i++) {
// 前缀和就是当前整段货位的最终高度。
            cur += dif[i];
if (cur > 0) {
                seen.add(cur);
            }
        }

// 最后的 0 也算一种不同取值。
        System.out.println(seen.size() + 1);
    }
}

2. 三路投放方案统计

问题描述

A 先生要给一场线下活动准备三路独立投放,分别记为 、、。

每一路投放都至少要准备  份物料,所以  都必须是正整数。

为了控制整体风险,这套方案还要同时满足下面两个限制:

  • >

    两两联动带来的总压力不能超过 ,也就是 。

  • >

    三路物料的总份数不能超过 ,也就是 。

现在想统计:一共有多少个满足条件的有序三元组 。

这里“有序”很重要。只要三个位置上的数字排列不同,就算不同方案。例如  和  要分别计数。

输入格式

第一行输入一个整数 ,表示测试用例组数。

接下来有  组数据。每组数据输入两个整数  和 ,含义与题面一致。

输出格式

对于每组测试数据,输出一行一个整数,表示满足条件的有序三元组数量。

样例输入

4
6 9
5 50
66 6
11451 419198

样例输出

4
4
20
2386336

数据范围

  • >

    。

  • >

    。

  • >

    所有测试用例的  之和不超过 。

  • >

    所有测试用例的  之和不超过 。

样例
解释说明
样例 1 的第 1 组
当  时,合法方案恰好是 、、、,所以答案为 。
样例 1 的第 2 组
当  时,虽然  很大,但乘积约束已经把绝大多数方案卡掉了,所以答案仍然只有 。

题解

这题最容易写成三重枚举,但真正没必要把  也一个个试出来。

关键观察是:当  和  固定以后, 的可行范围可以直接算。

先看乘积约束:

把和  有关的部分提出来:

于是得到:

再看总和约束:

所以对于固定的 ,合法的  个数就是:

这样第三层循环就被消掉了。


接下来还要把第二层循环的范围压小。因为  至少要等于 ,所以必须满足:

整理后就是:

所以:

同时, 还要求:

也就是:

因此固定  以后, 只需要枚举到:

这就是整道题的核心范围。


为什么复杂度能过?

对固定的 , 的上界大约是  量级,所以总枚举次数近似于一段调和级数:

再结合题目给出的“所有测试用例的  之和不超过 ”,这套做法完全够用。

复杂度分析

  • >

    单组时间复杂度为 。

  • >

    额外空间复杂度为 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


defsolve_one(n, x):
# a 至少还要给 b、c 各留出 1 个位置。
    a_max = min(n, x - 2)
if a_max < 1:
return0

    ans = 0
for a in range(1, a_max + 1):
# c >= 1 时,对 b 的两个上界。
        b1 = (n + 1) // (a + 1) - 1
        b2 = x - a - 1
        b_max = b1 if b1 < b2 else b2
if b_max < 1:
continue

        ab = a

# apb 始终表示 a + b,这样可以少做一次加法。
for apb in range(a + 1, a + b_max + 1):
            c1 = (n - ab) // apb
            c2 = x - apb
            ans += c1 if c1 < c2 else c2
            ab += a

return ans


defmain():
    t = int(input())
    out = []
for _ in range(t):
        n, x = map(int, input().split())
        out.append(str(solve_one(n, x)))
    print("\n".join(out))


if __name__ == "__main__":
    main()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

using ll = longlong;

static ll solve_one(ll n, ll x){
// a 至少还要给 b、c 各留出 1。
    ll a_max = min(n, x - 2);
if (a_max < 1) {
return0;
    }

    ll ans = 0;
for (ll a = 1; a <= a_max; ++a) {
// c >= 1 时,对 b 的两个上界。
        ll b1 = (n + 1) / (a + 1) - 1;
        ll b2 = x - a - 1;
        ll b_max = min(b1, b2);
if (b_max < 1) {
continue;
        }

        ll ab = a;

// apb 表示 a + b,循环里少做一次加法。
for (ll apb = a + 1; apb <= a + b_max; ++apb) {
            ll c1 = (n - ab) / apb;
            ll c2 = x - apb;
            ans += min(c1, c2);
            ab += a;
        }
    }

return ans;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;
while (t--) {
        ll n, x;
cin >> n >> x;
cout << solve_one(n, x) << '\n';
    }
return0;
}
  • >
    Java
import java.io.BufferedInputStream;
import java.io.IOException;

publicclassMain{
staticclassFastScanner{
privatefinal BufferedInputStream in = new BufferedInputStream(System.in);
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buffer[ptr++];
        }

longnextLong()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ');

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long value = 0;
while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
return value * sign;
        }
    }

staticlongsolveOne(long n, long x){
// a 至少还要给 b、c 各留出 1。
long aMax = Math.min(n, x - 2);
if (aMax < 1) {
return0;
        }

long ans = 0;
for (long a = 1; a <= aMax; a++) {
// c >= 1 时,对 b 的两个上界。
long b1 = (n + 1) / (a + 1) - 1;
long b2 = x - a - 1;
long bMax = Math.min(b1, b2);
if (bMax < 1) {
continue;
            }

long ab = a;

// apb 表示 a + b。
for (long apb = a + 1; apb <= a + bMax; apb++) {
long c1 = (n - ab) / apb;
long c2 = x - apb;
                ans += Math.min(c1, c2);
                ab += a;
            }
        }

return ans;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
int t = (int) fs.nextLong();
        StringBuilder sb = new StringBuilder();

for (int i = 0; i < t; i++) {
long n = fs.nextLong();
long x = fs.nextLong();
            sb.append(solveOne(n, x)).append('\n');
        }

        System.out.print(sb.toString());
    }
}
微信咨询 微信客服二维码微信扫一扫 · 添加人工客服 QQ QQ咨询 QQ咨询二维码QQ扫一扫 · 添加人工客服 帮助手册