首页 > 其他分享 >题解:AT_abc374_d [ABC374D] Laser Marking

题解:AT_abc374_d [ABC374D] Laser Marking

时间:2024-10-05 23:22:27浏览次数:7  
标签:Marking Laser 印刷 题解 线段 abc374

看到 \(n\le6\),就知道这道题又是一道搜索了。

题面有点长,信息也给的有点多,但稍微分析就可以得到只需要搜索印刷线段的顺序即可。

具体的,我们在深搜函数里面传 \(4\) 个参数,分别代表已选线段的数量,当前位置的横纵坐标,以及当前时间。为了方便,我们表示的是已经印刷完当前线段后的时间。

我们可以先预处理出来每条线段净印刷所需的时间,用一个数组标记每条线段是否已经印刷。

搜索过程中我们枚举所有未印刷的线段,然后从这条线段的两头分别开始计算时间,因为数据很小,所以我们无需确定哪种方式最优。

距离计算就使用勾股定理即可。(这个肯定都会)

有一点需要注意,题目所有数据均为浮点数,代码中不要出现整型变量。

提交记录

标签:Marking,Laser,印刷,题解,线段,abc374
From: https://www.cnblogs.com/Lydic/p/18448720

相关文章

  • P5593 题解
    题目分析首先考虑什么样的颜色能被链覆盖。容易想到当某种颜色恰巧在一条链上会被覆盖。所以只需要判断一种颜色是否能构成链即可,链的贡献也很好计算。算法考虑链的性质:有且仅有两个端点。凭借这个性质,可以判断一种颜色是否在一条链上。在dfs中考虑各种情况。假设一个......
  • P10418 [蓝桥杯 2023 国 A] 相连的边 题解
    一个比较有趣的树形DP,情况比较多。【题目简述】给定一棵树,求三条相连的边,其边权之和最大。【思路】以X代表当前节点,S表示儿子,G表示孙子,P表示父节点。首先把树建出来,在以下图中,我们模拟二号点的DP过程,考虑以下几种情况:有一条边指向父节点时FG(FatherGrandson):一......
  • 数列 题解
    题意给出一张联通图,图上每个点有红蓝两色,给每一条边都赋一个权值,使得所有的红边构成一颗最小生成树,且权值是\(1\)到\(m\)的排列,求字典序最小的情况。题解对于一条蓝边,其权值一定小于除它以外全是红边的环上的所有红边的权值(有点绕),否则就构不成一颗生成树。所以只需要按顺......
  • CF946G Almost Increasing Array 题解
    题目传送门前置知识最长不下降子序列|权值树状数组及应用解法若将\(\{a\}\)变成严格递增序列,至少需要更改\(n\)减去\(\{a_{i}-i\}\)的最长不下降子序列长度个数。证明对于\(a_{i},a_{j}(i<j)\)若都在最终的严格递增序列里,则有\(a_{i}-a_{j}\lei-j\),即\(......
  • PHP报错getimagesize(): SSL operation failed with code 1问题解决方案
    这个PHP错误通常发生在尝试通过HTTPS协议获取图像时,由于缺少或过期的CA证书导致SSL连接验证失败。以下是详细的解决方案:解决方案一:更新CA证书下载最新的CA证书访问 curl官方提供的CA证书 页面下载 cacert.pem 文件。上传证书文件将下载的 cacert.......
  • U486684 「INOI2016」Brackets 题解
    首先对于回文&括号有一个经典转移:枚举分割点+区间两个端点讨论此题也是如此首先枚举分割点十分套路,如下\[dp_{i,j}=\max_{k=i}^{j-1}dp_{i,k}+dp_{k+1,j}\]如果两个端点相同\[dp_{i,j}=dp_{i+1,j-1}+v_i+v_j\]还有一个转移对于一个区间,因为是子序列,所以一个区间的子区间......
  • qoj9230 Routing K-Codes 题解
    首先这个图肯定不能有环,也不能有度数大于\(3\)的点。也就是说这是一颗二叉树。我们假设父亲都比儿子小,根节点的值最小。那么假设\(u\)点的值为\(x\),它的儿子的值一定是\(\{2x,2x+1\}\)的子集。会发现\(u\)的子树内的权值和是一个关于\(x\)的一次函数。而且无论两个儿......
  • CF1648F Two Avenues 题解
    非常好题目,使我代码旋转。思路考虑什么样的边有贡献。我们首先提出原图的一个dfs树。处理出经过关键点的树上路径在每一条树边的经过次数\(v_i\)。我们选点会有以下几种情况。选两条割边\(i,j\),由于割边肯定是树边,所以答案就是\(v_i+v_j\)。选一条只被一条非树边覆盖......
  • P9611 题解
    题目大意从题目可知,本题要求求出\(l\simr\)的因子个数和。题目分析我们可以将这个问题分解为两个问题,变成求\(1\simr\)的因子个数和减去\(1\siml-1\)的因子个数和,然后我们考虑如何求\(1\simn\)的因子个数和首先,如果正着做很难的话,我们可以考虑反着做。对于一个数\(......
  • CF1108F题解
    传送门:https://codeforces.com/problemset/problem/1108/F求出最小生成树后处理出任意两点间边的最大值,这里可以用倍增或者树刨。然后用不在生成树上的边去替换,如果边权和边两端点路径最大边值相同则最小生成树不唯一,需要将边权\(+1\)。实现比较简单,写了一遍就过了。#include<b......