专栏文章

题解：P10195 [USACO24FEB] Quantum Moochanics G

HHYR403
P10195题解参与者 9已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@mio6vyp7
此快照首次捕获于
2025/12/02 14:20
3 个月前
此快照最后确认于
2025/12/02 14:20
3 个月前
查看原文

题意

有偶数个粒子，按照正反正反正反……的顺序排下去。第 i 个粒子的位置在 p[i]，速度为 s[i]。粒子的初始方向由其粒子性质决定，正粒子初始方向向右，反粒子初始方向向左。当 Bessie 看向这些粒子的时候，它们的方向会被改变。Bessie 会在实验开始后的第 1 秒，第 3 秒，第 6 秒……看向这些粒子。
综上所述，一个正粒子的运动轨迹大致如下（反粒子方向相反）：

思路

首先，我们观察发现。每一次发生湮灭的两个粒子在此之前一定是相邻的。
反证法，如果正粒子和反粒子之间还隔着粒子，那么中间一定既有正粒子也有反粒子，而且外正粒子与内反粒子相邻，内正粒子与外反粒子相邻，就会先发生湮灭。不存在能让内正反粒子湮灭前外正反粒子湮灭的情况。
所以我们很快就可以想到一个方法：先遍历所有相邻的粒子，查找第一对要湮灭的，使它们湮灭，然后使他们左右两边的粒子互相标记为相邻的。
那么，如何标记相邻状态呢？我们可以先定义两个数组 pre[] 和 nxt[] ，标记粒子的前后驱。当我们使两个粒子湮灭时，就让前粒子的前驱将后驱标记为后粒子的后驱，让后粒子的后驱把前驱标记为前粒子的前驱。
对的，就是数组模拟链表！
那么，如何计算哪一对粒子要先湮灭呢？
我们思考只有两个粒子的情况：
首先，如果正粒子在左侧，反粒子在右侧，设 k=t+12k=\frac{t+1}{2}，此处的 t 是观察的次数。
那么每一个 t%2==1 时候，正粒子 i 的位置距离原来的点，向右偏移了 k 个 s[i]。同理，反粒子 j 向左偏移 k 个 s[j]。
当粒子相遇时，有：
pi+ksi≥pj−ksjp_i+ks_i \ge p_j-ks_j
化简得：
k≥pj−pisi+sjk \ge \frac{p_j-p_i}{s_i+s_j}
因为是大于等于，所以向上取整。
左边是反粒子，右边是正粒子的计算一模一样。只是 k=t2k=\frac{t}{2}。
由于正粒子编号为奇数，反粒子编号为偶数，所以粒子 x、y 相遇时间的计算就可以写出一个简洁的式子：
CPP
int ceil(int x,int y){
	return x/y+bool(x%y);
}

int ct(int x,int y){
	int k=ceil(p[y]-p[x],s[x]+s[y]);
	return 2*k-x%2;
}
但是如果直接遍历所有相邻的粒子显然会超时。那么如何优化这个过程呢？
我们可以使用优先队列。优先队列对于队列中的元素，按照从大到小的顺序编排。尽管我们想要的是相遇时间最小的那一对粒子，我们也可以通过取反来使得排序生效。由于 pair 的比较是按照第一个元素，所以我们套两层 pair，外面的 pair 把时间的相反数存在第一位用来排序，第二位再放一个 pair 存相邻的粒子。
但现在我们又遇到了一个问题。比如有这样一段正反粒子：
TXT
+1 -1 +2 -2
那在我们初始化的时候，我们要比较所有相邻的粒子，所以我们的优先队列里面存了 3 对粒子：
TXT
+1 -1
-1 +2
+2 -2
假设 -1 与 +2 最先湮灭，那么我们的粒子和队列情况会变成这样：
TXT
+1 -2
TXT
+1 -1
+2 -2
+1 -2 //新加的
可以看到，尽管 -1 和 +2 已经湮灭，但是队列中仍然保留这与它们有关的点对。如何将这些点对去除呢？
很简单，我们可以不去除它们，当它们被我们出队的时候，我们再看看之前它们是否出过队。如果出过队，但我们再 continue。

代码

CPP
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=2e5+5;

int p[N],s[N],a[N],pre[N],nxt[N];
//位置，速度，答案（存点是哪一次观察时湮灭的），前驱，后继 

void init(int n){
	for(int i=0;i<N;i++)
		a[i]=0;
//多测要记得清空答案数组，因为这里的答案数组兼职vis的功能 
	for(int i=1;i<=n;i++){//初始化前驱后继 
		pre[i]=i-1;
		nxt[i]=i+1;
	} 
}

int ceil(int x,int y){//计算x/y向上取整 
	return x/y+bool(x%y);
}

int ct(int x,int y){//计算两点什么时候相撞。 
	int k=ceil(p[y]-p[x],s[x]+s[y]);
	return 2*k-x%2;
}

void solve(){
	int n;
	cin>>n;
	init(n);
	for(int i=1;i<=n;i++)
		cin>>p[i];
	for(int i=1;i<=n;i++)
		cin>>s[i];
	priority_queue<pair<int,pair<int,int>>>q;
	//第一个int填时间（观察次数）的相反数，后面两个int存点对 
	for(int i=1;i<n;i++)
		q.push({-ct(i,i+1),{i,i+1}});//取反存入 
	while(!q.empty()){
		auto tmp=q.top();
		q.pop();
		int t=-tmp.first,x=tmp.second.first,y=tmp.second.second;
		//读出信息 
		if(a[x]||a[y])//如果之前出过队 
			continue;//跳过 
		a[x]=a[y]=t;//记录答案和vis  
		int pres=pre[x],nxts=nxt[y];
		if(pres>=1&&nxts<=n)
			q.push({-ct(pres,nxts),{pres,nxts}});//将两侧粒子入队
		//更新前驱后继 
		pre[nxts]=pres;
		nxt[pres]=nxts;
	}
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
//	#ifndef local
//		freopen("quantum.in","r",stdin);
//		freopen("quantum.ans","w",stdout);
//	#endif
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
		solve();
	return 0;
}

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...