社区讨论

70pts求条,孩子从考场下来到现在也没想出为什么WA

P11232[CSP-S 2024] 超速检测参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m35a2l1z
此快照首次捕获于
2024/11/06 10:46
去年
此快照最后确认于
2025/11/04 15:15
4 个月前
查看原帖
WA on #5 #6 #10
下面是考场代码,本人推测是被卡精度了,但是也不知道怎么修正这个问题。
CPP
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,l,v;
struct nd{
	long double d,vi,a;
	long double le,ri;//Overspeed:(le,ri)
	bool zb,yb,ovsp;
}cr[100002];
int sxt[100002];
struct nd2{
	int lf,rt;
	bool avi;
}sg[100002];
stack<int> s;
bool cmp(nd2 a,nd2 b)
{
	if(a.rt==b.rt)
	{
		return a.lf<b.lf;
	}
	return a.rt>b.rt;
}
int ef(int lft,int r,long double num)
{
	if(lft>=r)
	{
		return lft;
	}
	int mid=(lft+r)/2;
	if(sxt[mid]*1.0>=num)
	{
		return ef(lft,mid,num);
	}else{
		return ef(mid+1,r,num);
	}
}
int main()
{
//	freopen("detect5.in","r",stdin);
//	freopen("detect5.out","w",stdout);
	cin>>T;
	while(T--)
	{
		for(int i=1;i<=n;i++)
		{
			cr[i].d=0;
			cr[i].vi=0;
			cr[i].a=0;
			cr[i].le=0;
			cr[i].ri=0;
		}
		for(int i=1;i<=m;i++)
		{
			sxt[i]=0;
		}
		scanf("%d %d %d %d",&n,&m,&l,&v);
		int di,vii,ai;
		//Phase 1:deal with the cars.
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d %d",&di,&vii,&ai);
			cr[i].d=((long double)(di)); 
			cr[i].vi=((long double)(vii)); 
			cr[i].a=((long double)(ai)); 
			if(cr[i].a==0)
			{
				if(cr[i].vi>v)
				{
					cr[i].le=cr[i].d*1.0;
					cr[i].ri=l*1.0;
					cr[i].zb=true;
					cr[i].yb=true;
				}else{
					cr[i].le=(l+1.0)*1.0;
					cr[i].ri=(l+1.0)*1.0;
				}
			}else{
				if(cr[i].a>0)
				{
					if(cr[i].vi>v)
					{
						cr[i].le=cr[i].d*1.0;
						cr[i].ri=l*1.0;
						cr[i].zb=true;
						cr[i].yb=true;
					}else{
						cr[i].le=cr[i].d*1.0+(1.0*(((v*v*1.0-cr[i].vi*cr[i].vi*1.0))/(2.0*cr[i].a)));
						if(cr[i].le<=l)
						{
							cr[i].ri=l*1.0;
							cr[i].yb=true;
						}
					}
				}else{
					if(cr[i].vi>v)
					{
						cr[i].le=cr[i].d*1.0;
						cr[i].ri=cr[i].d*1.0+(1.0*(((v*v*1.0-cr[i].vi*cr[i].vi*1.0))/(2.0*cr[i].a)));
						cr[i].zb=true;
						if(cr[i].ri>l*1.0)
						{
							cr[i].yb=true;
							cr[i].ri=l*1.0;
						}
					}else{
						cr[i].le=(l+1)*1.0;
						cr[i].ri=(l+1.0)*1.0;
					}
				}
			}
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&sxt[i]);
		}
		//Phase 2:use all sxt[] to cover the segments
		int ans=n;
		for(int i=1;i<=n;i++)
		{
			sg[i].lf=ef(1,m,cr[i].le+(cr[i].zb?0:0.00000001));
			sg[i].rt=ef(1,m,cr[i].ri-(cr[i].yb?0:0.00000001));
			
			sg[i].avi=true;
			if(sxt[sg[i].rt]*1.0>cr[i].ri-(cr[i].yb?0:0.00000001))
			{
				sg[i].rt--;
			}
			if(sg[i].lf==sg[i].rt)
			{
				if(sxt[sg[i].lf]*1.0>=cr[i].le+(cr[i].zb?0:0.00000001)&&sxt[sg[i].rt]*1.0<=cr[i].ri-(cr[i].yb?0:0.00000001))
				{
					cr[i].ovsp=true;
				}else{
					ans--;
					cr[i].ovsp=false;
					sg[i].avi=false;
				}
			}else{
				if(sg[i].lf>sg[i].rt)
				{
					ans--;
					cr[i].ovsp=false;
					sg[i].avi=false;
				}else{
					cr[i].ovsp=true;
				}
			}
		}
		printf("%d ",ans);
//		Phase 3:use the fewest sxt[] to cover all the segments.
		sort(sg+1,sg+1+n,cmp);
		int ans2=0;
		for(int i=1;i<=n;i++)
		{
			if(!sg[i].avi)
			{
				continue;
			}
			if(s.empty())
			{
				ans2++;
				s.push(sg[i].lf);
			}else{
				if(sg[i].rt>=s.top())
				{
					if(sg[i].lf>=s.top())
					{
						while(s.size()&&s.top()<sg[i].lf)
						{
							s.pop();
						}
						s.push(sg[i].lf);
					}
				}else{
					while(s.size())
					{
						s.pop();
					}
					s.push(sg[i].lf);
					ans2++;
				}
			}
		}
		printf("%d\n",m-ans2);
		while(s.size())
		{
			s.pop();
		}
	}
	
	return 0;
}
/*
This took me 3h.But on the special sample of B type,always 1 difference to AC.
Nevermind.

II.Firmament Star
Though Luxe877 only got 4pts in 2022 and only got 2nd price at the junior group.
He didn't give up,and prepared for the (te chang sheng kao shi) in July.
At last,he passed with 67/100 pts.Phew.After entering the senior high school,Luxe877 keep learning OI,but found that many people in the same room as him is better at him in OI.
Thankfully,it didnt hurt him.And he successfully entered round2 2023.
*/

回复

2 条回复,欢迎继续交流。

正在加载回复...