首页 > 其他分享 >是这样的

是这样的

时间：2024-08-10 15:49:02浏览次数：3  
标签：std return int double long 这样 define

是这样的，我的 \(O(128n\log n)\) 做法没有跑过 \(O(128n\log^2 n)\) 做法。

zr day5 t2

场切了，又没场切。

首先考虑圆上两点距离怎么求。

如果知道圆上两点坐标，直接欧几里得公式 \(dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)。

但是并不知道，考虑扔到坐标系上，这就是一个单位圆，充分发挥人类智慧，利用勾股定理求出每个点的坐标，手动算出距离即可。可以发现，两点之间的距离只与中间隔着几个点有关。

不难发现，将一些点移到坐标轴上，然后对于不在坐标轴上的点，横纵坐标的绝对值都为 \(\dfrac{\sqrt{2}}{2}\)。

二分速度 \(v\)。

考虑 dp，\(dp_{i,j}\) 表示获得 \(i\) 分且落在 \(j\) 位置上的最小时间（实数），分类讨论转移，时间复杂度 \(O(128n\log n)\)。

题解复杂度 \(O(128n+16n\log n)\)，怎么会是呢？

悬赏卡常。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
//#define double long double
//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
#pragma GCC optimize(3)
//using long double=double;

//#define file(...) freopen("##__VA_ARGS__.in","r",stdin);freopen("##__VA_ARGS__.out","w",stdout)
//#define outfile(...) freopen("##__VA_ARGS__.out","w",stdout)
//#define infile(...) freopen("##__VA_ARGS__.in","r",stdin);
//#define datafile(...) freopen("##__VA_ARGS__.in","w",stdout)
#define debug(...) fprintf(stderr,##__VA_ARGS__)
//#define printf(...) fprintf(stdout,##__VA_ARGS)
template<typename T,typename I>
#define heap(T) std::priority_queue<T>
#define umap(T,I) std::unordered_map<T,I>
#define pii(T,I) std::pair<T,I>
#define map(T,I) std::map<T,I>
#define vector(T) std::vector<T>
#define stack(T) std::stack<T>
using ll=long long;
using i128=__int128;
using ull=unsigned long long;

template<typename T>
inline void read(T &x){
	x=0;
	char c=getchar();
	int f=1;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(int)(c-'0'),c=getchar();
	x*=f;
}

template<typename T,typename I>
inline void chkmin(T &a,I b){
	a=std::min(a,b);
}

template<typename T,typename I>
void chkmax(T &a,I b){
	a=std::max(a,b);
}

//随机数部分
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
int getgen(T L,T R){
	return rnd()%(R-L+1)+L;
}

const double eps=1e-7,pi=std::acos(-1);
const int inf=1e18,MOD1=998244353,MOD2=1e9+7,MOD3=2147483579,MOD4=19198111;
const __int128 inf128=1e30;

bool Mbe;

stack(char) st;
template<typename T>
void print(T x){
	while(st.size()) st.pop();
	if(x==0) st.push('0');
	if(x<0) putchar('-'),x=-x;
	while(x) st.push((char)('0'+x%10)),x/=10;
	while(st.size()) putchar(st.top()),st.pop();
}
template<typename T>
void printsp(T x){
	print(x);
	putchar(' ');
}
template<typename T>
void println(T x){
	print(x);
	putchar('\n');
}

const int maxn=20010,nxam=10010;

const long double sqrt2=1.41421356237309;

long double dp[maxn][10];//,dis[5]={0,std::sqrt(std::pow(sqrt2/2.0,2)+std::pow(1.0-sqrt2/2.0,2)),sqrt2,std::sqrt(std::pow(sqrt2/2.0,2)+std::pow(1.0+sqrt2/2.0,2)),2.0};

long double dis[5]={0,0.765366864730,1.414213562373,1.847758065023,2.0};

int t[maxn],x[maxn],n,k;

//long double mi[maxn][nxam][10];

long double getdis(int x,int y){
	if(x>y) std::swap(x,y);
	int dist=y-x;
	if(dist>4) dist=8-dist;
	return dis[dist];
}

long double time(long double dis,long double v){
	if(v==0) return 1e9;
	return dis/v;
}

const int maxt=1e6+11;

long double mi[maxt][10];
long double in[maxt][10];
long double go[10][10];

void preinit(){
	for(int i=0;i<=(int)1e6+10;i++)
		for(int j=1;j<=8;j++) in[i][j]=mi[i][j]=1e9;
	for(int i=1;i<=n;i++) in[t[i]][x[i]]=t[i]*1.0;
	for(int j=1;j<=8;j++){
		for(int i=(int)1e6+9;i>=0;i--) mi[i][j]=mi[i+1][j],chkmin(mi[i][j],in[i][j]);
	}
	return ;
}

long double y,z,u,d;

int into=0;

struct Info{
	int t,x;
}a[nxam]; 

bool comp_t(Info s1,Info s2){
	return s1.t<s2.t;
}

bool Acheck(long double p){
//	for(int i=1;i<=n;i++) a[i].t=t[i],a[i].x=x[i];
//	std::sort(a+1,a+n+1,comp_t);
	long double T=a[1].t-0.2;
	int pos=a[1].x;
	for(int i=2;i<=n;i++){
		T=T+time(getdis(pos,a[i].x),p);
		if(T<a[i].t-0.2) T=a[i].t-0.2;
		if(T-a[i].t>0.2) return 0;
		pos=a[i].x;
	}
	return 1;
} 

int lim;

bool check(long double p){
//	if(2.0-p<=1e-5) return 1;
//	if(p>0.5) return 1;
//	if(p<0.5) return 0;
//	for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) debug("dis %lld -> %lld : %.7Lf\n",i,j,time(getdis(i,j),p));
	//dp[i][j]:i j
	for(int i=1;i<=8;i++) dp[0][i]=0.0;
	for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) go[i][j]=time(getdis(i,j),p);
//	int lim=std::min(n*2,k+1);
	for(register int i=1;i<=lim;i++){ 
		for(register int j=1;j<=8;j++){
			dp[i][j]=1e9;
			//dp[i][j]
//			debug("ok\n");
			for(int k=1;k<=8;k++){
//				into++;
				long double x=dp[i-1][k];
				if(x>1e7) continue;
				y=go[j][k];
				z=x+y;
				if(j==k&&i!=1) z+=1.0;
				d=(std::floor(z)),u=(std::ceil(z));
//				if(j==k) d+=1.0;
//				debug("i=%lld j=%lld k=%lld d=%.7Lf u=%.7Lf z=%.7Lf\n",i,j,k,d,u,z);
				if(z-d>0.2&&z-d<=0.4){
					if(mi[(int)d][j]==d) chkmin(dp[i][j],z);
					else chkmin(dp[i][j],mi[(int)d][j]-0.4);
				}
				else{
					if(mi[(int)d+1][j]==d+1.0) chkmin(dp[i][j],std::max(z,mi[(int)d+1][j]-0.4));
					else chkmin(dp[i][j],mi[(int)d+1][j]-0.4);
				}
				if(u-z>0.2&&u-z<=0.4){
					if(mi[(int)u][j]==u) chkmin(dp[i][j],z);
					else chkmin(dp[i][j],mi[(int)u+1][j]-0.4);
				}
				else chkmin(dp[i][j],mi[(int)u+1][j]-0.4);
//				debug("dp=%.7Lf\n",dp[i][j]);
			}
//			debug("first appear i=%lld j=%lld dp=%.7Lf\n",i,j,dp[i][j]); 
			if(i==1) continue;
//			debug("okk\n");
			for(int k=1;k<=8;k++){
				long double x=dp[i-2][k];
				if(x>1e7) continue;
				y=go[j][k];
				z=x+y;
				if(j==k&&i!=2) z+=1.0;
				d=(std::floor(z)),u=(std::ceil(z));
//				if(j==k) d=d+1.0;
				if(z-d<=0.2){
					if(mi[(int)d][j]==d) chkmin(dp[i][j],z);
					else chkmin(dp[i][j],mi[(int)d][j]-0.2);
				}
				else{
					if(mi[(int)d+1][j]==d+1.0) chkmin(dp[i][j],std::max(z,mi[(int)d+1][j]-0.2));
					else chkmin(dp[i][j],mi[(int)d+1][j]-0.2); 
				} 
				if(u-z<=0.2){
					if(mi[(int)u][j]==u) chkmin(dp[i][j],z);
					else chkmin(dp[i][j],mi[(int)u][j]-0.2);
				}
				else chkmin(dp[i][j],mi[(int)u+1][j]-0.2);
//				debug("k=%lld d=%.7Lf u=%.7Lf z=%.7Lf x=%.7Lf y=%.7Lf\n",k,d,u,z,x,y);
			}
			if(i>=k&&dp[i][j]<1e7) return 1;
//			debug("p=%.7Lf i=%lld j=%lld dp=%.7Lf\n",p,i,j,dp[i][j]);
		}
	}
	return 0;;	
	long double tt=1e9;
	for(int i=k;i<=2*n;i++)
		for(int j=1;j<=8;j++) if(dp[i][j]<1e9) chkmin(tt,dp[i][j]);//,debug("i=%lld j=%lld %.7Lf\n",i,j,dp[i][j]);
//	debug("tt=%.10Lf\n",tt);
	return tt<1e7;
}

bool Men;

signed main(){
//	freopen("ex_maimai3.in","r",stdin);
//	std::ios::sync_with_stdio(false);
//	file();
//	assert(1);
//	debug("%.8lfMB\n",(&Mbe-&Men)/1048576.0);
//	for(int i=1;i<=4;i++) debug("%.12Lf\n",dis[i]);
//	return 0;
	read(n),read(k);
	if(k<=2){
		printf("0\n");
		return 0;
	} 
	lim=std::min(2*n,k+1); 
	for(int i=1;i<=n;i++) read(t[i]),read(x[i]);
	preinit();
	long double l=0,r=2.0;
	int cnt=0;
	for(int i=1;i<=n;i++) a[i].t=t[i],a[i].x=x[i];
	if(k==2*n) std::sort(a+1,a+n+1,comp_t);
	while(r-l>=eps){
		if(k==2*n){
			long double mid=(l+r)/2.0;
			if(Acheck(mid)) r=mid;
			else l=mid;
			continue;
		}
		if(++cnt>=22) break;
		long double mid=(l+r)/2.0;
//		debug("%.7Lf\n",mid);
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.10Lf\n",r);
	debug("%.8lfms\n",1e3*clock()/CLOCKS_PER_SEC);
	return 0;
}
/*
Good luck
-std=c++14 -Wall -O2 -Wextra -Wl,-stack=2147483647
*/

标签：std,return,int,double,long,这样,define
From： https://www.cnblogs.com/BYR-KKK/p/18352379

相关文章

  • python程序代码这样加密保护，你觉得可以吗？
    python程序代码很容易反编译，下面我体验了pyhton代码保护的好方法，方案支持windows与Linux系统，下面以linux系统为例进行加密演示。下载最新Linux平台开发工具包 http://chinadlp.com/?list-DriveDownload.html拷贝到有桌面的Ubuntu系统中解压：tar-xzfSentinel-LDK.tar.gz ......
  • 为了落地DDD，我是这样“PUA”大家的
    本文书接上回《先有鸡还是先有蛋？这是领域驱动设计落地最大的困局》https://mp.weixin.qq.com/s/lzAZXgchCg_VyLmyo2N18Q 故事背景2023年，我加入了一个全新的团队，担任技术Leader的角色，可以算做是“空降”吧，至今已经一年有余的时间了。到目前为止，团队已经完成了领域驱动设计实......
  • 超全能，MobaXterm远程工具，网工、运维这样用就对了
    号主：老杨丨11年资深网络工程师，更多网工提升干货，请关注公众号：网络工程师俱乐部上午好，我的网工朋友。远程访问和管理服务器的能力对于开发人员、系统管理员乃至普通用户来说都变得越来越重要。随着云计算和分布式系统的普及，能够高效、安全地进行远程操作已经成为一项必备技能......
  • 如何修复当我将组合放入这样的列表 ([ 地址 )] 时，它说它是空的并且不打印任何内容的错
    我使用python生成74个字符串的组合，并使用两个组合字符串，即“0123456789abcdef”和“QQQQQQ33”。我希望QQQQQ33位于括号[]中，以便在使用它时，它使用完整的字符串，而不是生成字符串与0123456789abcdef的所有组合。每当我使用括号时，这就像是唯一的方法它完整​​地打印......
  • 不写代码，这样使用Python seaborn、matplotlib
    今天分享一个PyQt5GUI工具，动动鼠标拖拽就使用Python的Matplotlib、Seaborn进行绘图，并导出高清PDF。sviewgui安装pip install sviewguisviewgui使用使用很简单，因为，他只有一个方法啊：buildGUI()；下面以tips.csv数据和boxplot为例介绍sviewgui的使用。以下三种方法均可......
  • Parallels Desktop19Mac就是这样一个神器！在Windows和Mac之间反复切换横跳！
    在Windows和Mac之间反复横跳，是很多职场人的常态。Windows系统生态完善，软件丰富；而Mac的优雅设计、出色的性能以及稳定的系统体验也让人难以舍弃。但鱼与熊掌不可得兼，两个系统来回切换，需要准备两台电脑，既麻烦又占用空间，还增加了经济负担。如果一台电脑可以同时运行两个操作系......
  • 编写一个程序打开两个文件。可以使用命令行参数或提示用户输入文件名. a.该程序以这样
    /编写一个程序打开两个文件。可以使用命令行参数或提示用户输入文件名.a.该程序以这样的顺序打印:打印第一个文件的第一行，第二个文件的第一行，第一个文件的第二行，第二个文件的第二行，以此类推，打印到行数较多文件的最后一行b.修改程序，把行号相同的行打印成一行/#include<stdio.......
  • 当尝试执行Web应用程序时，会发生这样的错误
    ValueError：pickle中的节点数组具有不兼容的dtype：预期：{'names':['left_child','right_child','feature','threshold','impurity','n_node_samples','weighted_n_node_samples','......
  • Prometheus Alertmanager还能这样做数据持久化和可视化看板，太提效了吧？
    引言        Prometheus是一款主流的监控工具，对于Alertmanager存在的局限性我们不言而喻，本文主要介绍如何实现Alertmanager告警数据持久化，并在grafana搭建可视化看板。 背景        PrometheusAlertmanager作为Prometheus生态系统中的核心告警管理组......
  • 【今日曝光】员工恶意删除文件怎么办？企业大佬这样解决
    面对突如其来的挑战总是需要智慧与决断。近日，一起员工恶意删除公司重要文件的事件引发了广泛关注，这不仅考验着企业的应急响应能力，更促使我们深思如何构建更加稳固的数据防护体系。今天，就让我们跟随企业大佬的步伐，一探他们是如何高效解决这一棘手问题的。迅速评估，冷静应对......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99