滴滴-2026.03.08
这套滴滴题是很典型的“两道题都要先把问题压扁”的组合。
第一题表面上是在问很多个阈值下的统计结果，真正该抓的是“最终到底出现了哪些正高度”；第二题表面上是三元组计数，真正该做的是固定前两个量后一次算完第三个量的贡献。
题目 1：仓储层位观测
这题的关键不在于把每个 都算出来，而在于意识到答案只和“出现过多少种正高度”有关。
一旦把这一点想清楚，后面就是标准的区间加离散化：把所有会改变高度的端点抠出来，再在压缩后的坐标上做差分。
题目 2：三路投放方案统计
真正的突破口是把三层枚举降成两层。固定 之后， 的可选范围可以直接由两个上界取最小值。
难点主要在复杂度判断。看到 的上界大约是 以后，就知道总枚举次数是一段调和级数，这题就落回了可做范围。
1. 仓储层位观测
问题描述
K 小姐在整理一条很长的仓储通道。通道里一共有 个货位，编号为 到 。一开始，每个货位上都没有箱子。
接下来会有 批补货。第 批补货会把 个相同的箱子，同时加到编号位于 的每一个货位上。于是，所有补货结束后，每个货位都会得到一个最终高度。
现在定义函数 表示：最终高度 大于等于 的货位有多少个。
K 小姐不关心 的具体变化过程，她只想知道：当 从 一直取到很大的值时， 一共会出现多少种不同的取值。
输入格式
第一行输入两个整数 和 ，分别表示货位数量与补货批次数。
接下来有 行，每行输入三个整数 、、，表示这一批补货会让区间 中的每个货位高度增加 。
输出格式
输出一个整数，表示 这一长串数值里，不同取值的总个数。
样例输入
10 4
7 8 5
5 7 5
1 2 1
3 5 3
样例输出
6
数据范围
| |
|---|
| 最终高度依次为 。正高度只有 这 种，所以 会出现 种不同取值，最后那个 来自所有货位都不够高时的 。 |
题解
真正麻烦的地方，不是去算某一个固定的 ，而是要看它一共会变化出多少个不同答案。
先盯住“什么时候会变”。假设某个货位的最终高度是 ，那么当阈值 从小到大增加时，这个货位会在 的那一刻从统计里消失。在别的位置，它对 没影响。于是， 只会在“跨过某个真实出现过的正高度”时发生变化。
这就得到一个非常关键的结论：答案其实等于“最终所有货位里，正高度有多少种不同取值”再加上 。多出来的这个 ，对应的是阈值继续升高后，所有货位都被删空，此时 。
所以题目被改写成：想办法找出所有 出现过的不同正高度。
问题又来了， 最大能到 ，显然不可能真的把每个货位都算出来。这里要利用区间加的结构：所有变化只会发生在每次补货的左端点 ，以及右端点后一位 。把这些位置和边界 全部收集起来、排序去重后，相邻两个坐标之间的整段货位，最终高度一定相同。这样一来，本来可能有 个位置，现在只剩下不超过 个关键分界点。
接着在压缩后的坐标上做差分。对一条操作 加上 ，只需要在 对应的位置加上 ，在 对应的位置减去 。最后扫一遍前缀和，就能得到每个压缩段的真实高度。
扫的过程中，不需要记录整段有多长，因为题目只问“出现过哪些高度”，而不是每个高度出现了多少次。只要某一段的高度大于 ，就把这个高度丢进集合里。集合大小记为 ，最终答案就是 。
为什么这样做一定正确？原因分两步：
第一，坐标压缩不会丢信息。因为任意两个相邻关键点之间，再也没有操作端点穿过，所以这一整段货位经历的所有补货完全一样，最终高度当然也完全一样。
第二，答案和不同正高度的个数一一对应。若正高度从小到大是 $h_1<h_2<\cdots<h_k$，那么当阈值依次跨过 $h_1,h_2,\dots,h_k$="" 时，至少会有一批货位退出统计，$f(x)$="" 会严格下降；而在两个相邻高度之间，满足“高度至少为="" $x$”的货位集合并不会变化。因此，$f(x)$="" 的不同取值正好是这="" $k$="" 次下降形成的="" 个值，再加上最后的="" $0$，总数就是="" $k+1$。<="" p="">
复杂度方面，坐标数不超过 。排序和每次二分定位的总复杂度是 ，扫前缀和是 ，空间复杂度也是 。在 的范围内完全可以通过。
参考代码
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()
#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;
}
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
数据范围
| |
|---|
| |
| 当 时，虽然 很大，但乘积约束已经把绝大多数方案卡掉了，所以答案仍然只有 。 |
题解
这题最容易写成三重枚举，但真正没必要把 也一个个试出来。
关键观察是：当 和 固定以后， 的可行范围可以直接算。
先看乘积约束：
把和 有关的部分提出来：
于是得到：
再看总和约束：
所以对于固定的 ，合法的 个数就是：
这样第三层循环就被消掉了。
接下来还要把第二层循环的范围压小。因为 至少要等于 ，所以必须满足：
整理后就是：
所以：
同时， 还要求：
也就是：
因此固定 以后， 只需要枚举到：
这就是整道题的核心范围。
为什么复杂度能过？
对固定的 ， 的上界大约是 量级，所以总枚举次数近似于一段调和级数：
再结合题目给出的“所有测试用例的 之和不超过 ”，这套做法完全够用。
复杂度分析
参考代码
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()
#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;
}
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());
}
}
