害害害我又来写题解了题目大意国庆旅游高峰期高速路上来了一些车主路长为LLL它们驶入主路的位置不同也有加速度(可正可负)。路上有一些监控问有几辆会被监控抓到超速扣你六分就老实了至多可以撤去几个监控保证前面求出的车都会被拍到这题最讨厌的就是这个加速度对我来说就是降维打击不过题目贴心的给了公式。很明显最好做的就是加速度为全为0可以保证一直做——匀——速——直——线——运动只让最远的那个监控测。注意有的车行驶路线刁钻不会经过监控那么它就不会被检测到超速。代码for(inti1;in;i){if(a[i].vVa[i].dp[m])ans;}if(!ans)cout0 mendl;elsecoutans m-1endl;然后可以发现所有车加速度为正的的情况也比较好写。如果一个一来就超速了那它肯定一路上都在超不放过每个监控。如果它开始没超那么通过最后一个公式可以算出它到哪里会超速和最远监控比比位置就行了。但是如果根据公式去除以2a2a2a的话会有精度损失不妨让最远距离乘以2a2a2a再进行比较。代码for(inti1;in;i){intsp[m]-a[i].d;longlongvmaxa[i].v*a[i].v2*a[i].a*s;if(vmax1LL*V*Va[i].dp[m])ans;}if(!ans)cout0 mendl;elsecoutans m-1endl;然后是全部加速度小于0的情况。这个怎么弄呢因为车子一直在减速如果刚开始它没超就直接continue掉。接着可以想到先二分求出每辆第一个能遇到的监控再判断到这里时车有没有超速没超的话也continue。如果超了就用二分算它最多能保持超速状态到哪个监控得到一个超速区间。然后就是一个简单的区间覆盖点问题。想必大家都会这里就不赘述了。代码vectorqujianaa;//自己定义的一个struct类型的玩愣intans20;for(inti1;in;i){if(a[i].vV)continue;intL_idxlower_bound(p1,pm1,a[i].d)-p;if(L_idxm1)continue;longlongvsq_L1LL*a[i].v*a[i].v2LL*a[i].a*(p[L_idx]-a[i].d);if(vsq_L1LL*V*V)continue;intloL_idx,him,lastL_idx;while(lohi){intmid(lohi)/2;longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[mid]-a[i].d);if(vsqV*V*1LL)//同样关注精度损失问题{lastmid;lomid1;}else{himid-1;}}qujian q;q.lL_idx;q.rlast;aa.push_back(q);ans2;}sort(aa.begin(),aa.end(),cmp);ints-1;intk0;for(inti0;iaa.size();i){if(saa[i].l){saa[i].r;k;}}coutans2 m-kendl;最后就是最难的混合的情况了。首先看到1、2个点。小数据直接暴力二进制枚举。intmask[25];for(inti1;in;i){mask[i]0;for(intj1;jm;j){if(p[j]a[i].d)continue;longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[j]-a[i].d);if(vsq0)continue;if(vsq1LL*V*V){mask[i]|(1(j-1));}}}intcnt0;for(inti1;in;i){if(mask[i]!0)cnt;}intmink30;for(intmask_10;mask_1(1m);mask_1){boolok1;for(inti1;in;i){if(mask[i]!0(mask[i]mask_1)0){ok0;break;}}if(ok){intcnt10;for(intj0;jm;j){if(mask_1(1j))cnt1;}minkmin(mink,cnt1);}}coutcnt m-minkendl;其实写了第三种情况后就能猜出个一二了无非就是把前面写的加起来。加速度等于0只看超不超速就行加速度大于0找到刚好超速的那个监控与最远那个监控组成一个超速区间小于0就直接拷贝啥也不变。最终代码#includebits/stdc.husingnamespacestd;structcar{intd,v,a;};structqujian{intl,r;};intn,m,L,V,ans;car a[100005];intp[100005];boolcmp(qujian a,qujian b){returna.rb.r;}voidcheck(){for(inti1;in;i){if(a[i].vVa[i].dp[m])ans;}if(!ans)cout0 mendl;elsecoutans m-1endl;}voidcheck2(){for(inti1;in;i){intsp[m]-a[i].d;longlongvmaxa[i].v*a[i].v2*a[i].a*s;if(vmax1LL*V*Va[i].dp[m])ans;}if(!ans)cout0 mendl;elsecoutans m-1endl;}voidcheck3(){vectorqujianaa;intans20;for(inti1;in;i){if(a[i].vV)continue;intL_idxlower_bound(p1,pm1,a[i].d)-p;if(L_idxm1)continue;longlongvsq_L1LL*a[i].v*a[i].v2LL*a[i].a*(p[L_idx]-a[i].d);if(vsq_L1LL*V*V)continue;intloL_idx,him,lastL_idx;while(lohi){intmid(lohi)/2;longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[mid]-a[i].d);if(vsqV*V*1LL){lastmid;lomid1;}else{himid-1;}}qujian q;q.lL_idx;q.rlast;aa.push_back(q);ans2;}sort(aa.begin(),aa.end(),cmp);ints-1;intk0;for(inti0;iaa.size();i){if(saa[i].l){saa[i].r;k;}}coutans2 m-kendl;}voidcheck4(){intmask[25];for(inti1;in;i){mask[i]0;for(intj1;jm;j){if(p[j]a[i].d)continue;longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[j]-a[i].d);if(vsq0)continue;if(vsq1LL*V*V){mask[i]|(1(j-1));}}}intcnt0;for(inti1;in;i){if(mask[i]!0)cnt;}intmink30;for(intmask_10;mask_1(1m);mask_1){boolok1;for(inti1;in;i){if(mask[i]!0(mask[i]mask_1)0){ok0;break;}}if(ok){intcnt10;for(intj0;jm;j){if(mask_1(1j))cnt1;}minkmin(mink,cnt1);}}coutcnt m-minkendl;}intmain(){intT;cinT;while(T--){boolflagtrue,flag2true,flag3true;cinnmLV;ans0;for(inti1;in;i){cina[i].da[i].va[i].a;if(a[i].a!0)flagfalse;if(a[i].a0)flag2false;if(a[i].a0)flag3false;}for(inti1;im;i){cinp[i];}if(flag){check();}if(flag2){check2();}if(flag3){check3();}// if(!flag!flag2!flag3n20m20)// {// check4();// }elseif(!flag!flag2!flag3){vectorqujianaa;for(inti1;in;i){if(a[i].a0){if(a[i].vV)continue;intL_idxlower_bound(p1,pm1,a[i].d)-p;if(L_idxm1)continue;aa.push_back({L_idx,m});}elseif(a[i].a0){intlo1,him,first-1;while(lohi){intmid(lohi)/2;if(p[mid]a[i].d){lomid1;continue;}longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[mid]-a[i].d);if(vsq1LL*V*V){firstmid;himid-1;}else{lomid1;}}if(first-1)continue;aa.push_back({first,m});}else{if(a[i].vV)continue;intL_idxlower_bound(p1,pm1,a[i].d)-p;if(L_idxm1)continue;longlongvsq_L1LL*a[i].v*a[i].v2LL*a[i].a*(p[L_idx]-a[i].d);if(vsq_L1LL*V*V)continue;intloL_idx,him,lastL_idx;while(lohi){intmid(lohi)/2;longlongvsq1LL*a[i].v*a[i].v2LL*a[i].a*(p[mid]-a[i].d);if(vsqV*V*1LL){lastmid;lomid1;}else{himid-1;}}qujian q;q.lL_idx;q.rlast;aa.push_back(q);}}intcntaa.size();sort(aa.begin(),aa.end(),cmp);ints-1;intk0;for(inti0;iaa.size();i){if(saa[i].l){saa[i].r;k;}}coutcnt m-kendl;}}return0;}温馨小提示大家平时开车切莫心急莫要超速哦——(不然奖励你300块和6分)