社区讨论
为什么爆搜过不了前两个点
P11232[CSP-S 2024] 超速检测参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m2srt0ec
- 此快照首次捕获于
- 2024/10/28 16:42 去年
- 此快照最后确认于
- 2025/11/04 15:48 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int t,n,m,l,v,p[maxn],flag,vis[maxn],b[maxn],maxx;
struct node {int d,v,a;}c[maxn];
void dfs(int cnt,int ans)
{
if(cnt == m)
{
int res = 0;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
{
if(p[j] < c[i].d || !b[j]) continue;
double V = sqrt(c[i].v*c[i].v+2*c[i].a*(p[j]-c[i].d));
if(V-(double)v > 1e-15) ++res;
}
if(res == ans)
{
int tmp = 0;
for(int i = 1;i <= m;++i)
if(!b[i]) ++tmp;
maxx = max(maxx,tmp);
}
return;
}
b[cnt] = 1;
dfs(cnt+1,ans);
b[cnt] = 0;
dfs(cnt+1,ans);
}
int main(int argc,char *argv[])
{
//freopen("detect.in","r",stdin);
//freopen("detect.out","w",stdout);
cin>>t;
while(t--)
{
maxx = -1;
cin>>n>>m>>l>>v;
for(int i = 1;i <= n;++i)
{
scanf("%d%d%d",&c[i].d,&c[i].v,&c[i].a);
if(c[i].a) flag = 1;
if(c[i].a < 0) flag = 2;
}
for(int i = 1;i <= m;++i)
scanf("%d",&p[i]);
sort(p+1,p+m+1);
if(n <= 20 && m <= 20)
{
int res = 0;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
{
if(p[j] < c[i].d) continue;
double V = sqrt(c[i].v*c[i].v+2*c[i].a*(p[j]-c[i].d));
if(V-(double)v > 1e-15)
{
++res;
//cout<<i<<" "<<j<<'\n';
break;
}
}
cout<<res<<" ";
dfs(1,res);
cout<<maxx<<'\n';
continue;
}
if(!flag)
{
int res = 0;
for(int i = 1;i <= n;++i)
if(c[i].v > v && p[m] >= c[i].d) ++res;
int maxx = -1;
for(int i = 1;i <= n;++i)
maxx = max(maxx,c[i].d);
cout<<res<<" ";
if(res) cout<<m-1<<'\n';
else cout<<m<<'\n';
continue;
}
else if(flag == 1)
{
int res = 0;
for(int i = 1;i <= n;++i)
{
if(p[m] < c[i].d) continue;
double V = sqrt(c[i].v*c[i].v+2*c[i].a*(p[m]-c[i].d));
if(V-(double)v > 1e-15) ++res;
}
int maxx = -1;
for(int i = 1;i <= n;++i)
maxx = max(maxx,c[i].d);
cout<<res<<" ";
if(res) cout<<m-1<<'\n';
else cout<<m<<'\n';
continue;
}
else if(flag == 2)
{
memset(vis,0,sizeof(vis));
int res = 0;
for(int i = 1;i <= n;++i)
{
if(p[m] < c[i].d) continue;
int pos = upper_bound(p+1,p+m+1,c[i].d)-p-1;
double V = sqrt(c[i].v*c[i].v+2*c[i].a*(p[pos]-c[i].d));
if(V-(double)v > 1e-15) ++res,vis[pos] = 1;
}
int res2 = 0;
for(int i = 1;i <= m;++i)
if(!vis[i]) ++res2;
cout<<res<<" "<<res2<<'\n';
continue;
}
}
return 0;
}
rt 只有40pts
回复
共 0 条回复,欢迎继续交流。
正在加载回复...