孩子只是想过#2的数据
查看原帖
孩子只是想过#2的数据
846661
ARIS1_0楼主2024/11/5 20:23

求各位大佬帮忙优化一些我的程序

是优化我的程序而不是给我你自己的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-w;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*w;
}
void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	static int sta[35];
	int top=0;
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
	while(top)putchar(sta[--top]+'0');
}
namespace ___{
	vector<int>tot[30];
	set<int>tt;
	int t,n,m,L,v,disr,pos[100005],ans,cnt;
	struct node{
		int v,_a,dis;
	}a[100005];
	double get_v(ll sv,ll a,ll s){
		if(sv*sv+2*a*s<0)return 0;
		return sqrt(sv*sv*1.0+2.0*a*s);
	}
	bool vis[100005],vis2[100005];
	void mian(){
		freopen("detect.in","r",stdin);
		freopen("detect.out","w",stdout);
		t=read();
		while(t--){
			memset(vis,0,sizeof(vis));
			memset(vis2,0,sizeof(vis2));
			disr=0;
			cnt=0;
			ans=INT_MAX;
			n=read();m=read();L=read();v=read();
			for(int i=1;i<=n;i++){
				a[i].dis=read();
				a[i].v=read();
				a[i]._a=read();
			}
			for(int i=1;i<=m;i++){
				pos[i]=read();
				disr=max(pos[i],disr);
			}
			if(n<=20&&m<=20){
				for(int i=1;i<=m;i++)tot[i].clear();
				for(int i=1;i<=n;i++){
					if(a[i].dis>disr)continue;
					for(int j=1;j<=m;j++){
						if(a[i].dis>pos[j])continue;
						int tmps=pos[j]-a[i].dis;
						double tmpv=get_v(a[i].v,a[i]._a,tmps);
						if(tmpv>v){
							if(!vis[i])cnt++;
							vis[i]=1;
							tot[j].push_back(i);
						}
					}
				}
				for(int i=1;i<=(1<<m)-1;i++){//状压枚举拆监控的每一种情况 
					int tmp=0;tt.clear();
					for(int j=1;j<=m;j++){
						if((1<<(j-1))&i){
							for(int k=0;k<tot[j].size();k++)tt.insert(tot[j][k]);
							tmp++;
						}
					}
					if(tt.size()==cnt)ans=min(tmp,ans);
				}
				if(cnt!=0){
					write(cnt);putchar(' ');
					write(m-ans);putchar('\n');
				}
				else{
					write(cnt);putchar(' ');
					write(m);putchar('\n');
				}
				continue;
			}
			if(a[1]._a==0){
				for(int i=1;i<=n;i++){if(a[i].dis>disr)continue;
					if(a[i].v>v&&a[i].dis<=disr)cnt++;
				}
				if(cnt!=0){
					write(cnt);putchar(' ');
					write(m-1);putchar('\n');
				}
				else{
					write(cnt);putchar(' ');
					write(m);putchar('\n');
				}
				continue;
			}
			if(a[1]._a>0){
				for(int i=1;i<=n;i++){
					if(a[i].dis>disr)continue;
					if(a[i].v>v&&a[i].dis<=disr)cnt++;
					else{
						int tmps=pos[m]-a[i].dis;
						double tmpv=get_v(a[i].v,a[i]._a,tmps);
						if(tmpv>v)cnt++;
					}
				}
				if(cnt!=0){
					write(cnt);putchar(' ');
					write(m-1);putchar('\n');
				}
				else{
					write(cnt);putchar(' ');
					write(m);putchar('\n');
				}
				continue;
			}
		}
		return;
	}
}
using namespace ___;
int main(){
	mian();
	return 0;
}
2024/11/5 20:23
加载中...