社区讨论

为什么爆搜过不了前两个点

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 条回复,欢迎继续交流。

正在加载回复...