卷王小富最近又在内卷，并且学了一门新的技能：书法，但是不幸的是在国庆节的书法大赛上，小富不小心打翻了墨水瓶，导致很多墨滴溅在了他的书法纸上，看着墨水不断扩散，浸透了他的书法纸，小富突然萌生了一个想法：我能不能知道某时刻纸上一共有多少墨块？
我们假设墨滴是同时溅在纸上的，并且它们起始大小都为 0，由于墨滴大小不同，因此它们的扩散速度也不同，姑且假设墨滴都是按圆形扩散，如果两个或以上墨滴在扩散过程中相遇，那么就称它们为一个墨块（单独一个墨滴也是墨块），并且假设墨滴相遇不影响它的扩散，对于任意时刻 tt，小富想知道纸上有多少墨块
由于小富是ccpc金牌，这个问题对他来说简直是小菜一碟，并且小富还要继续他的书法大赛，于是他决定把这个问题交给你来解决，希望你不要辜负他的期望哦
输入描述:
第一行一个整数 nn，表示一共 nn 个墨滴(1≤n≤10^3)
接下来 n 行，每行三个整数 x,y,v，分别表示墨滴的位置 (x,y)，以及墨滴扩散的速度 v(0≤x,y,v≤103)
接下来一行一个整数 q，表示 q 次查询(0≤q,t≤10^3)
之后是 q 行，每行一个整数 t ，表示查询 t 时刻纸上一共多少个墨块
输出描述:
q 行，每行一个整数，表示 t 时刻纸上一共多少个墨块
示例1
输入
3 0 2 1 0 0 1 7 7 2 3 0 1 5
输出
3 2 1
说明
0时刻墨滴面积均为0，故答案为3
1时刻墨滴1，2相切，也记为相遇，故答案为2
5时刻三个墨滴都相遇，答案为1
思路：
题目让求的是每次询问的时候，t时刻桌面上有多少墨水。那么一开始所有墨水没有扩散，此时是不是就是有n个墨水。那么再想想，俩块墨水什么时候会变成一块墨水，而题中墨水一开始大小都是0，那么是不是可以抽象为，俩个墨点之间要多久才能从这个墨点到达另一个墨点。
那么此时不就能得到多少时间会有墨点相融合，而融合事后的墨点就用并查集，将他们连起来。文章来源：https://www.toymoban.com/news/detail-638115.html
（数据不超过1e3，所以预处理墨点合成时间是不会超时的）。当询问的时候采用离线处理的方法。还有一个小技巧就是，询问和预处理的放在一起，但是由于t时刻可能有刚好融合的，那么我们把t+1e-7这样询问就会在t时刻之后，从而解决t时刻有融合的问题文章来源地址https://www.toymoban.com/news/detail-638115.html
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"hear!"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define endl "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double,long double> PDD;
ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 1e6+ 10;
const ll mod1 =998244353;
const ll mod2 =1e9+7;
const ll hash_num = 3e9+9;
ll n,m,ca, k,ans;
ll arr[N],brr[N],crr[N];
ll h[N],ne[N],e[N],w[N],book[N],idx;
ll par[N];
struct node
{
ll x,y,v;
}noda[N];
struct query
{
double time;
ll l,r;
}q[N];
bool cmp(query a,query b)
{
return a.time<b.time;
}
double get_len(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
ll findd(ll x)
{
if(par[x]!=x)par[x]=findd(par[x]);
return par[x];
}
void init()
{
rep(i,1,n){
par[i]=i;
}
}
void solve()
{
cin >> n;
idx=0;
rep(i,1,n)
{
cin >> noda[i].x >> noda[i].y >> noda[i].v;
}
rep(i,1,n)
{
rep(j,i+1,n)
{
double t=get_len(noda[i].x,noda[i].y,noda[j].x,noda[j].y)/(noda[i].v+noda[j].v);
q[idx].time = t;
q[idx].l = i;
q[idx++].r = j;
}
}
cin >> m;
rep(i,1,m)
{
cin >> q[idx].time;
q[idx].time+=1e-7;
q[idx].l=-1;
q[idx++].r=i;
}
sort(q,q+idx,cmp);
ll now=n;
init();
rep(i,0,idx-1)
{
if(q[i].l==-1)
{
arr[q[i].r]=max(now,ll(0));
}else{
ll fa=findd(q[i].l),fb=findd(q[i].r);
if(fa!=fb)
{
par[fa]=fb;
now--;
}
}
}
rep(i,1,m)
{
cout << arr[i]<<endl;
}
}
int main()
{
IOS;
ll _;
_=1;
//get_eulers();
//scanf("%lld",&_);
//cin>>_;
ca=1;
while(_--)
{
solve();
ca++;
}
return 0;
}
到了这里，关于F-小富的idea（2023河南萌新联赛第（四）场：河南大学）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
