自动搬运

查看原文

来自洛谷，原作者为

	cyhhhhhh **

搬运于2025-08-24 22:09:29，当前版本为作者最后更新于2019-05-04 12:52:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题不知道为什么大佬们都不屑于来光顾，一篇题解都没有，那就让我这个没发过题解的蒟蒻来试试吧。其实做完之后个人觉得这一道题最难的地方是理解题意，把题意理解好以后，就是简单模拟了（对我来说还是不简单），题例的模拟过程我有发在我的“第0时刻”为题的讨论里面，因为太长不方便发在这里。

题目大概讲的是一款下落式音游（大概吧），有点和长条两种键。点的话比较简单，标记到点就得分，点掉落了就miss；线的话其实就是必须要一直标记着，然后松开标记过早或者过晚都会造成miss，只有在判定范围内才能得分

这道题显然不能用t来进行循环模拟，毕竟10^9的数据摆在那里是不可能完成的，所以我选择用操作进行循环，也就是每次循环执行一个操作，操作分别有：物体出现，物体消失（即最低点运动到第四象限），标记，取消标记，一共4种操作，由于标记和物体加起来最多只有4000个，所以循环最多8000次。所以我设置了操作栏，物品栏以及标记栏

具体解释一下我的四种操作吧：

1、物体的出现：此时会将物体从“未出现”变为“正常状态”

2、物体的消失：这里的消失是“本该在此时消失”的意思，就是说这个物体在不受任何操作下运动到第四象限，执行这个操作时，如果物体处于“正常状态”，就像题目所说的miss，如果不是，那么就跳过这个操作

3、标记：执行这个操作时，会寻找目前处于“正常状态”的物体进行判定（即判定是否得分），并且如题目所说，当两个标记同时对一个物体生效时，会按照规则进行替代，即离物体最近且最接近顶点的标记生效。

4、取消标记：执行这个操作时，会寻找被此标记进行标记过的长条，随后进行判定。

最后再解释代码里面可能有疑惑的地方：

1、物品栏和标记栏是对物品和标记进行编号，操作栏储存的是执行操作的物品或标记的编号

2、关于物品的h值（即状态）：0、1、2都很好理解。给h定义了一个3的原因是在题目中，同一时刻的标记操作是同时执行的，然而操作栏中我没办法做到同时执行，肯定会有先后顺序，所以就用3代表物体在这个时刻已经有标记对它进行了标记，但如果还有得分更高或者得分相等但更接近原点的标记可以对它生效，会发生代替，而这个h值会在时刻结束时进行修改。

3、关于操作的排序：其实就是按照题目的排序

（1）由于物体消失导致的miss（即物体消失排在第一位）

（2）物体出现（即物体出现排在第二位）

（3）由于标记和取消标记造成得分

（4）由于取消标记造成miss（即标记排在第三位，取消标记排在第四位）

最后，代码如下，如果有不懂的还可以问我，有点长，里面还会有文字注释帮助理解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct doit
{
	int appear;//有物体出现的操作（即表明第几号物体在此时出现） 
	int disappear;//有物体消失的操作（即表明第几号物体在此时消失）（表明物体在正常情况下运动到第四象限的时间） 
	int note;//标记操作（即表明第几个标记在此时操作） 
	int cancel;//取消标记操作（即表明第几个标记在此时取消） 
	long long time;//操作时间（即在第几时刻进行的操作） 
};//定义操作栏



struct item
{
	int h;//物体的状态（0表示未出现，1表示正常状态，2表示已经消失或者长条被标记状态，3表示在该时刻已经被标记过了，用于判断究竟是哪个标记起作用）
	long long line;//物体的x坐标 
	long long ly;//物体初始的最低点坐标 
	long long hy;//物体初始的最高点坐标 
	long long v;//物体的速度 
	long long firstp;//物体的第一次得分（即标记得分），因为会被覆盖所以需要储存最大值 
	long long t;//物体出现时的时间 
	int benote;//表示物体被几号标记所标记
	long long notep;//表示标记此物体的标记所在的位置 
};//定义物品栏



long long cmp(doit a,doit b)
{
	if(a.time!=b.time)return a.time<b.time;
	else if(a.disappear!=b.disappear)return a.disappear>b.disappear;
	else if(a.appear!=b.appear)return a.appear>b.appear;
	else if(a.note!=b.note)return a.note>b.note;
	else return a.cancel>b.cancel;
};//操作排序优先级：time→disappear→appear→note→cancel 




int main()
{
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout); 
	int n,m;
	cin>>n>>m;
	int o=2*(m+n);
	doit a[o+1];//声明操作栏
	item b[n+1];//声明物品栏
	int c[m+1];//声明标记栏 
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	
	
	
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].line>>b[i].ly>>b[i].hy>>b[i].t>>b[i].v;//输入物品初始信息（h值默认为0） 
		a[2*i-1].appear=i;
		a[2*i-1].time=b[i].t;
		a[2*i].disappear=i;
		a[2*i].time=b[i].t+1+(b[i].ly/b[i].v);//将物品的出现和消失时间加入操作栏中 
	}
	
	
	
	for(int i=1;i<=m;i++)
	{
		cin>>c[i]>>a[2*(n+i)-1].time>>a[2*(n+i)].time;//输入标记 
		a[2*(n+i)-1].note=i;
		a[2*(n+i)].cancel=i;//将标记和取消标记加入操作栏 
	}
	
	
	
	long long d0,s1,s2,w;//d0是判定长度，s1是基础分数，s2是额外基础分数，w是允许miss的次数 
	cin>>d0>>s1>>s2>>w;
	sort(a+1,a+o+1,cmp);//排序操作 
	long long combo=0,miss=0,lastmiss=0,dcount=0;
	//combo即连击数，miss即miss数
	//lastmiss储存上一时刻的miss数，当这一时刻miss比上一时刻多时，combo被断
	//dcount累计消失的物体个数，当dcount=n时游戏结束 
	long long total=0;
	
	
	
	for(int i=1;i<=o;i++)//游戏开始了 
	{
		if(a[i].appear!=0)b[a[i].appear].h=1;//当有物体出现时，该物体处于正常状态
		
		
		if(a[i].disappear!=0)
		{
			if(b[a[i].disappear].h==1)
			{
				miss++;
				combo=0;
				lastmiss=miss;
				dcount++;
				b[a[i].disappear].h=2;
			}//如果物体处于正常状态掉落，则miss
			//如果物体在其他时刻消失或者被标记，不考虑disappear操作
			
			
			if(miss>w)//miss数超限，游戏结束 
			{
				cout<<total<<endl<<a[i].time<<endl;
				return 0;
			} 
		}
		
		
		if(a[i].note!=0)
		{
			for(int j=1;j<=n;j++)
			{
				if(b[j].h==1||b[j].h==3)//表示物体在本轮处于正常状态（在不确定哪个标记生效时处于正常状态） 
				{
					long long dx=c[a[i].note]-b[j].line;//物体距离标记的水平距离 
					long long dy=b[j].ly-b[j].v*(a[i].time-b[j].t);//物体离标记的竖直距离，即物体此时最低点的纵坐标
					long long distance=dx*dx+dy*dy;//直线距离的平方，与d0的平方比较
					
					
					if(distance<=d0*d0)
					{
						long long point=(d0*d0-distance)*s1;//分数
						if(b[j].firstp==0)
						{
							combo++;
							total+=(point+combo*s2);
							b[j].firstp=point;
							if(b[j].hy!=b[j].ly)
							{
								b[j].benote=a[i].note;//如果物体是一条线，则被标记
								b[j].notep=c[a[i].note];//储存标记所在的位置 
							}
						}//如果物体这个时刻还没有受过标记，则combo数增加，并取得额外得分
						
						
						else if(point>b[j].firstp)//比较标记的得分，取最大的为生效的标记 
						{
							total+=(point-b[j].firstp);
							b[j].firstp=point;
							b[j].benote=a[i].note;//被标记
							b[j].notep=c[a[i].note];//储存标记所在的位置 
						}
						
						
						else if(point==b[j].firstp)//如果相等，比较标记离原点的距离 
						{
							if(b[j].notep>c[a[i].note])//离原点更近则替换 
							{
								b[j].benote=a[i].note;
							    b[j].notep=c[a[i].note];
							}
						}
						
						
						b[j].h=3;//改变物体的状态 
					}
				} 
			}
		}
		
		
		if(a[i].cancel!=0)
		{
			for(int j=1;j<=n;j++)
			{
				if(b[j].benote==a[i].cancel)
				{
					long long dx=c[a[i].cancel]-b[j].line;//物体距离标记的水平距离
					long long dy=b[j].hy-b[j].v*(a[i].time-b[j].t);//物体离标记的竖直距离，即物体此时最高点的纵坐标
					long long distance=dx*dx+dy*dy;//直线距离的平方，与d0的平方比较
					
					
					if(distance<=d0*d0)
					{
						long long point=(d0*d0-distance)*s1;//分数
						combo++;
						total+=(point+(combo*s2));
					}
					
					
					else miss++;
					//在这里先不判定miss是否大于w或者lastmiss，等到本时刻结束再判定
					//因为由操作引起的miss是在得分之后进行的，而在这里得分和miss是一起算的
					
					
					b[j].h=2;
					dcount++;//无论怎么样都会消失 
				}
			}
		}
		
		
		if(dcount==n)
		{
			cout<<total<<endl<<a[i].time<<endl;
			return 0;
		}//所有物体都消失，游戏结束
		
		
		if(a[i].time!=a[i+1].time||i==o)//当本时刻结束时，结算miss，并且将状态为3的物体处理掉
		{
			if(miss>w)
			{
				cout<<total<<endl<<a[i].time<<endl;
				return 0;
			}
			
			
			for(int j=1;j<=n;j++)
			{
				if(b[j].h==3)
				{
					if(b[j].hy==b[j].ly)dcount++;//是一个点的话，被标记立即消失
					b[j].h=2;//无论是点还是线状态都为2，但表示的意义不同 
				}
			}
			
			
			if(lastmiss!=miss)
			{
				combo=0;
				lastmiss=miss;
			}//如果本轮的操作出现了miss，则清除combo
			
			
			if(dcount==n)
	    	{
	    		cout<<total<<endl<<a[i].time<<endl;
	    		return 0;
	    	}//所有物体都消失，游戏结束
		} 
	}
	
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}