NightTide @ 2024-11-05 14:29:07
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
struct sec{ double l, r; };
bool operator < (sec a, sec b){ return a.l < b.l; }
bool operator > (sec a, sec b){ return a.l > b.l; }
int t, n, m, len, lim, ans1, ans2;
int d[MAXN], v[MAXN], a[MAXN];
double p[MAXN];
bool check(double l, double r){
int p1 = lower_bound(p + 1, p + m + 1, l) - p;
int p2 = upper_bound(p + 1, p + m + 1, r) - p - 1;
if(p1 > m || p2 < 1) return false;
if(p1 > p2) return false;
return true;
}
int main(){
scanf("%d",&t);
while(t--){
ans1 = 0; ans2 = 0;
vector<sec> s;
scanf("%d%d%d%d",&n,&m,&len,&lim);
for(int i = 1; i <= n; i++) scanf("%d%d%d",&d[i],&v[i],&a[i]);
for(int i = 1; i <= m; i++) scanf("%lf",&p[i]);
sort(p + 1, p + m + 1);
for(int i = 1; i <= n; i++){
if(a[i] > 0){
int mv = v[i] * v[i] + 2 * a[i] * (len - d[i]);
if(mv <= lim * lim) continue;
else{
double dis = (lim * lim - v[i] * v[i]) / (a[i] * 2.0);
double l = d[i] + dis, r = lim;
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
}else if(a[i] < 0){
if(v[i] <= lim) continue;
else{
double dis = (lim * lim - v[i] * v[i]) / (a[i] * 2.0);
double l = d[i], r = d[i] + dis;
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
}else if(a[i] == 0 && v[i] > lim){
s.push_back((sec){0, (double)len});
ans1++;
}
}
sort(s.begin(), s.end());
for(int i = 0; i < s.size(); ){
double nl = s[i].l, nr = s[i].r;
i++;
while(s[i].l < nr && check(max(nl, s[i].l), min(nr, s[i].r))){
nl = max(nl, s[i].l);
nr = min(nr, s[i].r);
i++;
}
ans2++;
}
printf("%d %d\n",ans1, m - ans2);
}
return 0;
}
/*
3
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
*/WA 10 pts。求助，嘎嘎挂分。
我的思路是对于每辆车处理出超速区间，然后区间按左端点排序，处理区间交。
by qcode_aya @ 2024-11-05 14:53:37
你的个人空间背景好好看耶，可以要一张吗？
没太看懂区间交是什么意思，可以详细说明一下嘛。
不过处理出超速区间后是经典贪心问题，按右端点排序后从左往右枚举区间选可选点集中最靠右的。
by lin_er @ 2024-11-05 15:06:15
我也写的是区间按左端点排序，处理区间交，但没挂啊……是不是你超速区间求错了
by lin_er @ 2024-11-05 15:26:09
@NightTide，事实上超速区间确实求错了，你这种求法考虑不足，首先第32行应该是 len 吧，然后考虑 a[i]>0 时，如果开始就超速的话，你的 dis 会算成负的，显然不对……所以你再想想怎么求。
by lin_er @ 2024-11-05 15:26:20
@NightTide
by NightTide @ 2024-11-05 15:51:03
@lin_er 这些我之前考虑到了，然后试图修改了。现在 60
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
struct sec{ int l, r; };
bool operator < (sec a, sec b){ return a.l < b.l; }
bool operator > (sec a, sec b){ return a.l > b.l; }
int t, n, m, len, lim, ans1, ans2;
int d[MAXN], v[MAXN], a[MAXN], p[MAXN];
pair<int, int> find(double l, double r){
int p1 = lower_bound(p + 1, p + m + 1, l) - p;
int p2 = upper_bound(p + 1, p + m + 1, r) - p - 1;
return make_pair(p1, p2);
}
pair<pair<int, int>, bool> check(double l, double r){
pair<int, int> p = find(l, r);
// printf("%lf %lf %d %d\n",l,r,p.first,p.second);
if(p.first > p.second) return make_pair(p, false);
else if(p.first > len) return make_pair(p, false);
else if(p.second < 0) return make_pair(p, false);
return make_pair(p, true);
}
int main(){
scanf("%d",&t);
while(t--){
ans1 = 0; ans2 = 0;
vector<sec> s;
scanf("%d%d%d%d",&n,&m,&len,&lim);
for(int i = 1; i <= n; i++) scanf("%d%d%d",&d[i],&v[i],&a[i]);
for(int i = 1; i <= m; i++) scanf("%d",&p[i]);
sort(p + 1, p + m + 1);
for(int i = 1; i <= n; i++){
// printf("%d\n",i);
if(a[i] > 0){
int mv = v[i] * v[i] + 2 * a[i] * (len - d[i]);
if(mv <= lim * lim) continue;
else if(v[i] <= lim){
double dis = (lim * lim - v[i] * v[i]) / (a[i] * 2.0);
double l = d[i] + dis, r = len;
pair<pair<int, int>, bool> tmp = check(l, r);
// printf("%lf %lf %d %d\n",l,r,p[tmp.first.first], p[tmp.first.second]);
if(tmp.second){
// printf("*\n");
s.push_back((sec){p[tmp.first.first], p[tmp.first.second]});
if((s.back().l - d[i]) * 2 * a[i] == lim * lim - v[i] * v[i]){
s.back().l = p[tmp.first.first + 1];
}
ans1++;
if(s.back().l > s.back().r){
s.pop_back();
ans1--;
}
}
}else if(v[i] > lim){
double l = d[i], r = len;
pair<pair<int, int>, bool> tmp = check(l, r);
// printf("%lf %lf %d %d\n",l,r,p[tmp.first.first], p[tmp.first.second]);
if(tmp.second){
// printf("*\n");
s.push_back((sec){p[tmp.first.first], p[tmp.first.second]});
ans1++;
}
}
}else if(a[i] < 0){
if(v[i] <= lim) continue;
else{
double dis = (lim * lim - v[i] * v[i]) / (a[i] * 2.0);
double l = d[i], r = d[i] + dis;
pair<pair<int, int>, bool> tmp = check(l, r);
// printf("%lf %lf %d %d\n",l,r,p[tmp.first.first], p[tmp.first.second]);
if(tmp.second){
// printf("*\n");
s.push_back((sec){p[tmp.first.first], p[tmp.first.second]});
if((s.back().r - d[i]) * 2 * a[i] == lim * lim - v[i] * v[i]){
s.back().r = p[tmp.first.second - 1];
}
ans1++;
if(s.back().l > s.back().r){
s.pop_back();
ans1--;
}
}
}
}else if(a[i] == 0 && v[i] > lim){
// printf("*\n");
s.push_back((sec){p[1], p[m]});
ans1++;
}
}
sort(s.begin(), s.end());
// for(int i = 0; i < s.size(); i++){
// printf("[%d, %d]\n",s[i].l,s[i].r);
// }
for(int i = 0; i < s.size(); ){
int nl = s[i].l, nr = s[i].r;
// printf(" + [%d, %d]",s[i].l,s[i].r);
i++;
while(s[i].l <= nr && check(max(nl, s[i].l), min(nr, s[i].r)).second){
nl = max(nl, s[i].l);
nr = min(nr, s[i].r);
// printf(" + [%d, %d]",s[i].l,s[i].r);
i++;
}
// printf("%d %d\n",nl,nr);
ans2++;
}
printf("%d %d\n",ans1, m - ans2);
}
return 0;
}
/*
1
10 10 150307 247
62978 968 -5
51700 883 -3
40408 564 -1
60366 870 -41
35943 797 -7
47476 595 -11
59020 672 -10
81024 964 -11
80637 695 -5
66114 874 -1
46720 48066 57373 60882 68842 72773 82820 116695 122159 150307
*/by NightTide @ 2024-11-05 15:51:37
@lin_er len 那个是纯手贱
by NightTide @ 2024-11-05 15:52:40
@qcode_aya
by lin_er @ 2024-11-05 16:21:22
@NightTide 我把你的代码改过了……但有些面目全非了，主要是把很多 double 改成 int 了，避免精度问题，事实证明你好像确实是超速区间求错了
by lin_er @ 2024-11-05 16:23:29
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
struct sec{ int l, r; };
bool cmp(sec x,sec y){
return x.l<y.l;
}
int t, n, m, len, lim, ans1, ans2;
int d[MAXN], v[MAXN], a[MAXN];
int p[MAXN];
bool check(int l, int r){
int p1 = lower_bound(p + 1, p + m + 1, l) - p;
int p2 = upper_bound(p + 1, p + m + 1, r) - p - 1;
if(p1 > m || p2 < 1) return false;
if(p1 > p2) return false;
return true;
}
int main(){
scanf("%d",&t);
while(t--){
ans1 = 0; ans2 = 0;
vector<sec> s;
scanf("%d%d%d%d",&n,&m,&len,&lim);
for(int i = 1; i <= n; i++) scanf("%d%d%d",&d[i],&v[i],&a[i]);
for(int i = 1; i <= m; i++) scanf("%d",&p[i]);
sort(p + 1, p + m + 1);
for(int i = 1; i <= n; i++){
if(a[i] > 0){
if(v[i]>lim){
int l=d[i],r=len;
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
else{
int dis = (lim * lim - v[i] * v[i]) / (a[i] * 2)+1;
int l = d[i] + dis, r = len;
if(l>r) continue;
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
}else if(a[i] < 0){
if(v[i] <= lim) continue;
else{
int dis = ((lim * lim - v[i] * v[i])%(a[i] * 2)==0?(lim * lim - v[i] * v[i]) / (a[i] * 2)-1:(lim * lim - v[i] * v[i]) / (a[i] * 2));
int l = d[i], r = min(len,d[i] + dis);
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
}
else if(a[i] == 0 && v[i] > lim){
int l=d[i],r=len;
if(check(l, r)){
s.push_back((sec){l, r});
ans1++;
}
}
}
sort(s.begin(), s.end(),cmp);
for(int i = 0; i < s.size(); ){
int nl = s[i].l, nr = s[i].r;
i++;
while(s[i].l <= nr && check(max(nl, s[i].l), min(nr, s[i].r))){
nl = max(nl, s[i].l);
nr = min(nr, s[i].r);
i++;
}
ans2++;
}
printf("%d %d\n",ans1, m - ans2);
}
return 0;
}
/*
3
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
*/by lin_er @ 2024-11-05 16:30:03
至于你新的代码……我现在发现到当 a[i] == 0 && v[i] > lim 时，超速区间不是 p[1], p[m] 吧，应该要计算吧……（起码从 d[i] 开始吧）