[CSP-S 2024] 超速检测（官方数据）
题目描述
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L L L 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。
这个周末，主干道上预计出现 n n n 辆车，其中第 i i i 辆车从主干道上距离最南端 d i d_i di 的位置驶入，以 v i v_i vi 的初速度和 a i a_i ai 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 v i > 0 v_i > 0 vi>0，但 a i a_i ai 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 L L L 的位置）或速度降为 0 0 0（这只可能在 a i < 0 a_i < 0 ai<0 时发生）时，我们认为该车驶离主干道。
主干道上设置了 m m m 个测速仪，其中第 j j j 个测速仪位于主干道上距离最南端 p j p_j pj 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 V V V，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 n n n 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 n n n 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。
由于 n n n 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。
如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。
输入格式
输入的第一行包含一个正整数 T T T，表示数据组数。
接下来包含 T T T 组数据，每组数据的格式如下：
第一行包含四个整数 n , m , L , V n, m, L, V n,m,L,V，分别表示车辆数量、测速仪数量、主干道长度和道路限速。
接下来 n n n 行：
第 i i i 行包含三个整数 d i , v i , a i d_i, v_i, a_i di,vi,ai 描述一辆车。
最后一行包含 m m m 个整数 p 1 , p 2 , … , p m p_1, p_2, \dots , p_m p1,p2,…,pm 描述道路上所有测速仪的位置。
输出格式
对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数量。
样例 #1
样例输入 #1
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
样例输出 #1
3 3
提示
【样例 1 解释】
在该组测试数据中，主干道长度为 15 15 15，限速为 3 3 3，在距离最南端 2 , 5 , 8 , 9 , 15 2, 5, 8, 9, 15 2,5,8,9,15 的位置各设有一个测速仪。
- 第一辆车在最南端驶入，以 3 3 3 的速度匀速行驶。这辆车在整个路段上都没有超速。
- 第二辆车在距离最南端 12 12 12 的位置驶入，以 4 4 4 的速度匀速行驶。在最北端驶离主干道时，它会被距离最南端 15 15 15 的测速仪判定为超速。
- 第三辆车在距离最南端 1 1 1 的位置驶入，以 1 1 1 的初速度、 4 4 4 的加速度行驶。其在行驶了 3 2 − 1 2 2 × 4 = 1 \frac{3^2-1^2}{2\times 4}=1 2×432−12=1 的距离，即到达 2 2 2 的位置时，速度变为 3 3 3，并在之后一直超速。因此这辆车会被除了距离最南端 2 2 2 的测速仪以外的其他测速仪判定为超速。
- 第四辆车在距离最南端 5 5 5 的位置驶入，以 5 5 5 的初速度、 − 2 -2 −2 的加速度行驶。其在行驶了 3 2 − 5 2 2 × ( − 2 ) \frac{3^2-5^2}{2\times (-2)} 2×(−2)32−52 的距离，即到达 9 9 9 的位置时，速度变为 3 3 3。因此这辆车在距离最南端 [ 5 , 9 ) [5, 9) [5,9) 时超速，会被距离最南端 5 5 5 和 8 8 8 的两个测速仪判定为超速。
- 第五辆车在距离最南端 6 的位置驶入，以 4 的初速度、−4 的加速度行驶。在其行驶了 3 2 − 4 2 2 × ( − 4 ) = 7 8 \frac{3^2-4^2}{2\times (-4)}=\frac{7}{8} 2×(−4)32−42=87 的距离后，即这辆车到达 6 7 8 6\frac{7}{8} 687 的位置时，其速度变为 3 3 3。因此这辆车在距离最南端 [ 6 , 6 7 8 ) [6,6\frac{7}{8}) [6,687) 时超速，但这段区间内没有测速仪，因此不会被判定为超速。
因此第二、三、四辆车会被判定为超速，输出的第一个数为 3 3 3。
我们可以关闭距离最南端 2 , 8 , 9 2, 8, 9 2,8,9 的三个测速仪，保留 5 5 5 和 15 15 15 的两个测速仪，此时三辆之前被判定为超速的车依然被判定为超速。可以证明不存在更优方案，因此输出的第二个数为 3 3 3。
【样例 2】
见选手目录下的 detect/detect2.in 与 detect/detect2.ans。
该组样例满足 n , m ≤ 10 n, m \leq 10 n,m≤10。
【样例 3】
见选手目录下的 detect/detect3.in 与 detect/detect3.ans。
该组样例满足特殊性质 A，其中前十组测试数据满足 n , m ≤ 3000 n, m \leq 3000 n,m≤3000。
【样例 4】
见选手目录下的 detect/detect4.in 与 detect/detect4.ans。
该组样例满足特殊性质 B，其中前十组测试数据满足 n , m ≤ 3000 n, m \leq 3000 n,m≤3000。
【样例 5】
见选手目录下的 detect/detect5.in 与 detect/detect5.ans。
该组样例满足特殊性质 C，其中前十组测试数据满足 n , m ≤ 3000 n, m \leq 3000 n,m≤3000。
【数据范围】
对于所有测试数据，保证：
- 1 ≤ T ≤ 20 1 \leq T \leq 20 1≤T≤20；
- 1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^5 1≤n,m≤105， 1 ≤ L ≤ 1 0 6 1 \leq L \leq 10^6 1≤L≤106， 1 ≤ V ≤ 1 0 3 1 \leq V \leq 10^3 1≤V≤103；
- 0 ≤ d i < L 0 \leq d_i < L 0≤di<L， 1 ≤ v i ≤ 1 0 3 1 \leq v_i \leq 10^3 1≤vi≤103， ∣ a i ∣ ≤ 1 0 3 |a_i| \leq 10^3 ∣ai∣≤103；
- 0 ≤ p 1 < p 2 < ⋯ < p m ≤ L 0 \leq p_1 < p_2 < \dots < p_m \leq L 0≤p1<p2<⋯<pm≤L。
| 测试点 | n , m ≤ n,m\leq n,m≤ | 特殊性质 |
|---|---|---|
| 1 1 1 | 10 10 10 | 无 |
| 2 2 2 | 20 20 20 | 无 |
| 3 3 3 | 3000 3000 3000 | A |
| 4 4 4 | 1 0 5 10^5 105 | A |
| 5 5 5 | 3000 3000 3000 | B |
| 6 6 6 | 1 0 5 10^5 105 | B |
| 7 7 7 | 3000 3000 3000 | C |
| 8 8 8 | 1 0 5 10^5 105 | C |
| 9 9 9 | 3000 3000 3000 | 无 |
| 10 10 10 | 1 0 5 10^5 105 | 无 |
特殊性质 A：保证 a i = 0 a_i = 0 ai=0。
特殊性质 B：保证 a i > 0 a_i > 0 ai>0。
特殊性质 C：保证 a i < 0 a_i < 0 ai<0，且所有车都不在最北端驶离主干道。
【提示】
与加速度有关的定义和公式如下：
- 匀加速运动是指物体在运动过程中，加速度保持不变的运动，即每单位时间内速度的变化量是恒定的。
- 当一辆车的初速度为 v 0 v_0 v0、加速度 a ≠ 0 a\neq 0 a=0，做匀加速运动，则 t t t 时刻后它的速度 v 1 = v 0 + a × t v_1 = v_0 + a \times t v1=v0+a×t，它的位移（即行驶路程） s = v 0 × t + 0.5 × a × t 2 s=v_0\times t+0.5\times a\times t^2 s=v0×t+0.5×a×t2。
- 当一辆车的初速度为 v 0 v_0 v0、加速度 a ≠ 0 a \neq 0 a=0，做匀加速运动，则当它的位移（即行驶路程）为 s s s 时，这辆车的瞬时速度为 v 0 2 + 2 × a × s \sqrt{v_0^2+2\times a\times s} v02+2×a×s 。
- 当一辆车的初速度为 v 0 v_0 v0、加速度 a ≠ 0 a \neq 0 a=0，在它的位移（即行驶路程）为 v 1 2 − v 0 2 2 a \frac{v_1^2-v_0^2}{2a} 2av12−v02 时，这辆车的瞬时速度为 v 1 v_1 v1。
如果你使用浮点数进行计算，需要注意潜在的精度问题。
通过了民间数据。
首先对于每辆车，能够判定它为超速的测速仪肯定是一段区间，如果这段区间不在 1∼m1\sim m1∼m 的范围内，则这辆车不会被判定为超速。否则，我们可以将这段区间看成一个限定条件，即我们在所选出来的测速仪中，对于每一个限定条件 li,ril_i,r_ili,ri，至少有一个测速仪（假设这个测速仪的位置为 xxx）满足 li≤x≤ril_i\le x\le r_ili≤x≤ri，并且我们希望选出来的测速仪尽可能少。
下面进行分类讨论，得出限定区间。
对于每个车子 iii，其超速情况分为以下两种：
-
当 ai>0a_i>0ai>0 时，若 vi>Vv_i>Vvi>V，则这辆车在一开始就超速了，那么限定区间的左端点即为满足 pj>dip_j>d_ipj>di 的最小的 jjj；否则，根据公式，这辆车驶入 di+V2−vi22aid_i+\frac{V^2-v_i^2}{2a_i}di+2aiV2−vi2 这个位置时，其速度会到达 VVV，那么限定区间的左端点即为满足 pj>di+V2−vi22aip_j>d_i+\frac{V^2-v_i^2}{2a_i}pj>di+2aiV2−vi2 的最小的 jjj。而以上情况的区间右端点显然都为 mmm，因为车子的速度是单调递增的。
-
当 ai≤0a_i\le 0ai≤0 时，若 vi≤Vv_i\le Vvi≤V，则代表这辆车的速度永远都不会超过 VVV，所以这辆车不会被判定为超速；反之则代表 vi>Vv_i>Vvi>V，限定区间的左端点即为满足 pj>dip_j>d_ipj>di 的最小的 jjj，再根据公式，二分出最大的满足 vi2+2ai×(pk−di)>V\sqrt{v_i^2+2a_i\times(p_k-d_i)}>Vvi2+2ai×(pk−di) >V 的 kkk，作为限定区间的右端点。
接下来考虑如何选出最少的点使得对于每个限定区间，至少有一个测速仪在该区间内。
首先将所有区间以左端点为第一关键字、右端点为第二关键字排序（左端点按照从小到大的顺序，右端点按照从大到小的顺序排序）。对于两个区间 [li,ri][l_i,r_i][li,ri] 及 [lj,rj][l_j,r_j][lj,rj]，若 li≤lj,ri≥rjl_i\le l_j,r_i\ge r_jli≤lj,ri≥rj，那么 [li,ri][l_i,r_i][li,ri] 这个区间是没有用的，因为一个点若在 [lj,rj][l_j,r_j][lj,rj] 内，它也必定在 [li,ri][l_i,r_i][li,ri] 内，所以对于这样的区间，是可以不考虑的。
那么在处理之后就满足所有区间的左端点、右端点都是按照升序排序的，再每次贪心的选当前区间的右端点，覆盖到不能覆盖的区间为止。
#include <bits/stdc++.h>
using namespace std;
#define double long double
int a[100005], d[100005], v[100005], p[100005];
int del[100005];
struct node {
int ql, qr;
friend bool operator<(node l, node r) {
if (l.ql != r.ql)
return l.ql < r.ql;
return l.qr > r.qr;
}
} s[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m, L, V;
cin >> n >> m >> L >> V;
for (int i = 1; i <= n; i++)
cin >> d[i] >> v[i] >> a[i];
for (int i = 1; i <= m; i++)
cin >> p[i];
int tot = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= 0 && v[i] <= V)
continue;
if (a[i] > 0) {
int wei = V * V - v[i] * v[i];
wei /= (2 * a[i]);
wei += d[i];
if (v[i] > V)
wei = d[i] - 1;
int l = 1, r = m, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (p[mid] > wei) {
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
if (!ans)
continue;
s[++tot].ql = ans, s[tot].qr = m;
} else {
int l = 1, r = m, pos = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (p[mid] >= d[i]) {
r = mid - 1;
pos = mid;
} else
l = mid + 1;
}
if (!pos)
continue;
l = pos, r = m;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
double su = sqrt(v[i] * v[i] * 1.0 + 2.0 * a[i] * (p[mid] - d[i]));
if (su > V) {
l = mid + 1;
ans = mid;
} else
r = mid - 1;
}
if (ans < pos)
continue;
s[++tot].ql = pos, s[tot].qr = ans;
}
}
sort(s + 1, s + tot + 1);
int mr = 1000000000;
for (int i = tot; i >= 1; i--) {
if (mr <= s[i].qr)
del[i] = 1;
mr = min(mr, s[i].qr);
}
int ans = 0, fu = 0;
for (int i = 1; i <= tot; i++) {
// cout << s[i].ql << " " << s[i].qr << " " << del[i] << endl;
if (del[i]) {
del[i] = 0;
continue;
}
if (fu < s[i].ql) {
ans++;
fu = s[i].qr;
}
}
cout << tot << " " << m - ans << "\n";
}
}Upd on 2024.11.4
附上考场代码。
Solution
个人感觉这个 T2 还是蛮板子的。
我们可以将所有车的 aaa 按正负分为两部分，a=0a=0a=0 归在正数那一类（不然后面会出现除以 000 的情况）。
先考虑 aaa 非负的情况，此时车的瞬时速度 vvv 单调不降，所以若在某一时刻 v>Vv>Vv>V，则对于后面任意时刻都同样有 v>Vv>Vv>V，满足要求的测速仪区间就形如 [i,m][i,m][i,m]，二分即可。
那如果 aaa 为负呢？此时我们就还要考虑减速为 000 的情况了。
我们可以先二分求出每辆车能够行驶超过的最远测速仪 xxx，位置位于车前且最小的测速仪 kkk，满足要求的测速仪就一定处于区间 [k,x][k,x][k,x] 内。
而又因为车的瞬时速度 vvv 单调递减，所以若在某一时刻 v>Vv>Vv>V，则对于前面任意时刻都同样有 v>Vv>Vv>V，满足要求的测速仪区间就形如 [k,i][k,i][k,i]，再写个二分即可。
最后存在多少个取值区间，就有多少车是能够被测出超速的。
这样我们就用 O(nlogn)O(n\log n)O(nlogn) 的时间复杂度附加极大的常数解决了第一问。
下面来看第二问，其实就是个比较经典的贪心模型。
我们考虑将所有区间 [l,r][l,r][l,r] 按 rrr 从小到大排序，维护一个变量 RRR 表示当前拓展到的最右端点，然后按顺序对每个区间 iii 执行以下策略：
-
初始 R=0R=0R=0。
-
若 li≤Rl_i \le Rli≤R，则跳过。
-
否则令 R←riR \leftarrow r_iR←ri，累加答案。
这样做的本质就是尽可能选每个区间最靠右的数（也就是 rir_iri），那么为什么这样做是最优的呢？
假如说枚举到区间 iii，你选择了 ri−1r_i-1ri−1 号测速点，那么这个测速点就可以被之后的若干区间共用，假设为 iii 至 j0j_0j0 号测速点。
若你此时选择了 rir_iri 号测速点，你就会发现能够共用的区间个数变得更多了。若假设为 iii 至 jjj 号测速点，则有 j0≤jj_0\le jj0≤j。
所以选择更靠右的点可以保证答案不劣的同时产生新的贡献，自然也就是最优的。
总体时间复杂度 O(nlogn)O(n\log n)O(nlogn)。
Code
细节还是挺多的，等公示出来后再说吧。
先提醒几个点：
-
二分一定要给左右指针留空位，不然就相当于默认有解。
-
不要用浮点数计算，将所有的除法都乘至一边，同时注意变号。
#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
struct car{
int d,v,a;
}e[N];
struct node{
int l,r;
}d[N];
int n,m,L,V,p[N],l,r,ll,rr,lll,rrr,mid,ans1,ans2,fnt;
int spe(int id,int pos){
if(e[id].d>pos) return -INF;
return 2*e[id].a*(pos-e[id].d)+e[id].v*e[id].v;
}
bool cmp(node x,node y){
return x.r<y.r;
}
void solve(){
cin>>n>>m>>L>>V,ans1=ans2=0;
for(int i=1,d,v,a;i<=n;i++){
cin>>d>>v>>a;
e[i]=car{d,v,a};
}
for(int i=1;i<=m;i++) cin>>p[i];
for(int i=1,k;i<=n;i++){
if(e[i].a>=0){
l=1,r=m+1;
while(l<r){
mid=l+r>>1;
if(spe(i,p[mid])>V*V) r=mid;
else l=mid+1;
}
if(l!=m+1){
d[++ans1]=node{l,m};
}
continue;
}
ll=0,rr=m;
while(ll<rr){
mid=ll+rr+1>>1;
if(2ll*p[mid]*e[i].a>=2ll*e[i].d*e[i].a-e[i].v*e[i].v) ll=mid;
else rr=mid-1;
}
if(!ll) continue;
lll=1,rrr=m+1;
while(lll<rrr){
mid=lll+rrr>>1;
if(p[mid]<e[i].d) lll=mid+1;
else rrr=mid;
}
if(lll==m+1) continue;
l=lll-1,r=ll;
while(l<r){
mid=l+r+1>>1;
if(spe(i,p[mid])>V*V) l=mid;
else r=mid-1;
}
if(l==lll-1) continue;
d[++ans1]=node{lll,l};
}
cout<<ans1<<" ";r=0;
sort(d+1,d+ans1+1,cmp);
for(int i=1;i<=ans1;i++){
if(r>=d[i].l) continue;
ans2++,r=d[i].r;
}
cout<<m-ans2<<'\n';
}
signed main(){
int T; cin>>T;
while(T--) solve();
return 0;
}