首页 > 其他分享 >题解 P2903 【[USACO08MAR]The Loathesome Hay Baler S】

题解 P2903 【[USACO08MAR]The Loathesome Hay Baler S】

时间:2023-07-25 12:33:44浏览次数:58  
标签:结点 齿轮 int 题解 Loathesome 相切 bfs P2903 Roller

posted on 2021-05-03 20:50:49 | under 题解 | source

首先输入,记录一下哪个齿轮的位置在 \((0,0)\),哪个在 \((x_t,y_t)\)。

接着,为了避免多次判断两个齿轮相切而超时,我们可以预处理一个 \(link_{i,j}\),表示第 \(i\) 个齿轮是否和第 \(j\) 个齿轮相切。

这部分直接 \(O(n^2)\) 暴力即可,注意 \(link_{i,i}\) 要 \(=0\),不然 bfs 时会重复搜自己。

怎么判断两个齿轮是否相切?我们小学二年级都学过一种距离,叫「欧几里得距离」。设两个点分别在 \((x_1,y_1)\) 和 \((x_2,y_2)\),那它们的距离就是:

\[dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]

怎么把它运用到这道题上呢?很简单,如果两个齿轮的圆心的距离等于这两个齿轮的半径之和,就说这两个齿轮相切。

实际运用时,为了防止被卡精度,一般对等式两边开平方,也就是:

\[(x_1-x_2)^2+(y_1-y_2)^2=(r_1+r_2)^2 \]

处理完 \(link_{i,j}\),就可以直接暴力 bfs 了。

bfs 的结点记录三个东西:当前是哪一个齿轮,当前齿轮的速度,当前经过齿轮的总速度。

题目要求「绝对值之和」,那就忽视计算速度这个负号。

每次扩展结点时,要选没扩展过而且与它相切的齿轮。

这样的 bfs,每个结点只会搜一次,每个结点要遍历一次 \(1\) 到 \(n\),时间复杂度为 \(O(n^2)\)。

最后输出答案要注意,直接向下取整,而不是四舍五入。

代码实现:

#include <queue>
#include <cstdio>
using namespace std;
int f(int a){return a*a;}//开平方函数,用 define 会计算很多次,不推荐
struct Roller{
    int x,y,r;
    Roller(int a=0,int b=0,int c=0):x(a),y(b),r(c){}
    friend bool check(Roller a,Roller b){
    	return f(a.x-b.x)+f(a.y-b.y)<=f(a.r+b.r);//判断相切
    }
    friend bool operator==(Roller a,Roller b){
    	return a.x==b.x&&a.y==b.y;//判断相等
    }
} a[1060];
int n,si,ei,ex,ey;
bool vis[1060],link[1060][1060];//vis 记录这个齿轮有没有被扩展过
struct Node{
	int i;
    double v,tot;//float 已死
    Node(int a,double c,double d):i(a),v(c),tot(d){}
};
queue<Node> q;
int bfs(){
    q.push(Node(si,10000.0,10000.0));
    vis[si]=1;//搜索记得标记起点
    while(!q.empty()){
        Node now=q.front();q.pop();
        if(now.i==ei) return (int)now.tot;//向下取整
        for(int i=1;i<=n;i++){
            if(!vis[i]&&link[now.i][i]){
                vis[i]=1;
                double v=now.v*(1.0*a[now.i].r/a[i].r);//计算扩展的齿轮的速度,注意 *1.0
                q.push(Node(i,v,now.tot+v));
            }
        }
    }
    return -1;
}
int main(){
    scanf("%d%d%d",&n,&ex,&ey);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
        if(a[i]==Roller(0,0)) si=i;
        if(a[i]==Roller(ex,ey)) ei=i;//记录头尾
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(check(a[i],a[j])) link[i][j]=link[j][i]=1;//预处理link[i][j]
        }
    }
    printf("%d",bfs());
    return 0;
}

标签:结点,齿轮,int,题解,Loathesome,相切,bfs,P2903,Roller
From: https://www.cnblogs.com/caijianhong/p/Solution-p2903.html

相关文章

  • 题解 P1538 【迎春舞会之数字舞蹈】
    postedon2021-06-0113:24:05|under题解|source给\(0\cdots9\)每个数字打表,打它在相应的位置有没有一划。然后把每个数字分成\(5\)部分,暴力输出即可。#include<cstdio>#include<cstring>usingnamespacestd;constchar*db[]={"-||||-","||"......
  • 【大联盟】20230714 T1 三分网络(tri) 题解 CF1666K 【Kingdom Partition】
    题目描述here。题解赛时得分:\(30/30\),想了很久网络流最后不会。感觉这题就纯纯对脑洞,因为把题目中的\(2\)改成\(3\)就做不了)))不过还是相当有意思的。考虑如下建模方式:首先,考虑最小割。对于每个点\(i\),我们用两个点\(x_{i}\),\(y_i\)来表示。\(x_i\)表示\(i\)号点是......
  • 题解 [SDOI2009] HH的项链
    题目链接对于这类问区间不同数的总数,显然是不能用线段树直接维护的,毕竟不符合区间区间可加性。考虑对于一个右端点固定的询问,哪些数字实际上是有权值的。比如区间1332312,显然,实际上对于相同的数字,只有一个是有权值的,其他权值均为\(0\)。但是这样还是无法起到简化的作用......
  • 题解 链表 (chain)
    题目链接首先考虑没有修改怎么做。两种做法。想到询问的形式为保留\(\gek\)的连通块个数,那么先将全部数字按照权值排序,然后从后往前做一遍并查集,并同时统计连通块的数量,在询问时只需二分找到第一个\(\gek\)的位置,将这个位置的答案输出即可。注意考虑答案为\(0\)的情况......
  • 【大联盟】20230713 T1 方向矩阵(rect) 题解 CF1666A 【Admissible Map】
    题目描述here。题解赛时得分:60/100。想到了正解,但调不出来,就改写暴力了。。。首先,我们把问题转化成每个点都入度为\(1\)。我们考虑合法子串只有两种形式:注意到U和D,要么同时出现,要么同时不出现,因为如果存在U,就说明U所在这一行得到度数减少了,一定需要上一行D来弥补......
  • luogu P3203 [HNOI2010] 弹飞绵羊 题解
    题目传送门:P3203[HNOI2010]弹飞绵羊题意\(n\)个数,满足\(i<a_i≤N+1\),\(m\)次下面两种操作修改一个数\(a_i\)从\(x\)开始跳,\(x=a_x\),几次能够跳出序列\(n\leq2*10^5,m<10^5\)分析数据范围比较大,单纯搜索模拟肯定会T,那么考虑每次让他跳一段就......
  • 题解 P7971【[KSN2021] Colouring Balls】
    postedon2022-10-0819:07:28|under题解|sourceproblem交互库有一个长为\(n\)的颜色序列,你可以询问区间\([l,r]\)中有多少种颜色,最后还原交互库手中的序列,只需要保持相对顺序不变。\(n\leq10^3\),最多询问次数\(Q=2000\)或\(Q=10^4\)。solution令\(C\)为\([1......
  • CF1051G Distinctification题解
    link首先可以发现,题目给定的两种操作为我们提供了“反悔机制”,所以有:结论\(1\):即任何一个可以到达的局面都能到达最优解。利用这个结论,首先我们先去重。继续提炼性质,与相差不到\(1\)的数为基准\(+1\)与\(-1\)操作,将这个数的变化范围限制在了一个区间,并且这个区间的数能......
  • 题解 Codeforces Round 887 (Div 1+Div 2) / CF1853AB,CF1852ABCD
    下大分!悲!Div1只过了1A!!!但还是补完整场Div2吧。A.Desortinghttps://codeforces.com/problemset/problem/1853/Aproblem用操作:\([1,i]++,[i+1,n]--\),使得数组不单调不降,求最小操作次数。\(n\leq10^5\)。solution操作等同于在差分数组上选出\(i\),做\(c_1:=c_1+1,c_i:......
  • UOJ #284. 快乐游戏鸡题解(长链剖分+单调栈合并)
    UOJ#284.快乐游戏鸡题解(长链剖分+单调栈合并)题面一番战斗之后,程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下:“追!”,于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创,出掉这一年的恶气。可是程序猿一追就走,一走就跑,一跑就无影无踪。计算鸡......