首页 > 其他分享 >CF1063E Lasers and Mirrors题解

CF1063E Lasers and Mirrors题解

时间:2024-09-26 19:23:17浏览次数:7  
标签:一个点 镜子 Mirrors 题解 CF1063E Lasers 号点

一道很好的手玩题,被薄纱了。

首先判掉\(\forall i,p_i=i\)的情况(显然是\(n\))

然后考虑按照\(p_i\)连边,先构造每一个环的方案。发现可以简单放置两面镜子使得\(i\)射到\(p_i\),而且只要从高到底构造,一定不会产生影响。

但是每一个环的最后一个点很特殊,因为第1个点下面放置了让第1个点射到第二个点的镜子,最后一个点就不能这样射回去。

但是如果我们另外找一个点,就可以放4面镜子绕回去,但这样的话另外找的点就不能接收了。

显然,对于每一个环,我们希望另外找的一个点一样,于是我们选择n号点,而且这样n号点下面只用向左边射,是符合要求的。

因此,其它情况的答案为n-1。

标签:一个点,镜子,Mirrors,题解,CF1063E,Lasers,号点
From: https://www.cnblogs.com/wangwenhan/p/18434125

相关文章

  • LOJ 6241. 性能优化 I 题解
    题给代码意为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\sum\limits_{k=1}^j[\gcd(j,k)=1]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\varphi(j)\\......
  • P8475 「GLR-R3」雨水 题解
    关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多......
  • P8474 「GLR-R3」立春 题解
    俗话说的好:“打表出奇迹”,所以我们这一题打表计算。其实确实可以打表来找规律。通过打表,我们可以获得如下的结果:1 12 33 214 3155 9765…… ……然后观察可得:\[1\times3=1\times(2^2-1)=3\]\[3\times7=3\times(2^3-1)=21\]\[21\times15=21\t......
  • Codeforces Round 971 (Div. 4)题解记录(G3待补)
    A.Minimize!暴力模拟一遍即可#include<iostream>#include<queue>#include<deque>#include<map>#include<set>#include<stack>#include<vector>#include<bitset>#include<math.h>#include<random>#include&l......
  • P8563 Magenta Potion 题解
    前排警告这是较为通用,不需要脑子,但是代码量巨大的题解,请谨慎食用解题思路不知道大家做没做过带修改的区间最大连续子段和,这一题其实就是带修改的区间最大连续子段积。那么其实做法是类似的。我们用线段树维护五个量:当前区间答案,区间前缀最小值,区间前缀最大值,区间后缀最小值,区......
  • P8564 ρars/ey 题解
    显然树上背包。首先一眼会想到的状态:\(dp_{i,j}\)表示\(i\)的子树最后剩下\(j\)个结点的最小代价。然而开始写会发现这并不好DP。于是我们换一个想法:\(dp_{i,j}\)表示\(i\)的子树删去\(j\)个结点的最小代价。则有转移方程:\[dp_{i,j}=\min_{v\inson(i)}\{dp_{i......
  • 题解:UVA1456 Cellular Network
    UVA1456CellularNetwork题解夭寿了!30行写完紫题了!更新:已联系管理员修改难度,现在是绿题题意很简单,不再赘述。首先一个小贪心,将概率\(u​\)进行从大到小的排序,优先查看概率大的区域,显然这样能够保证访问数量期望最小。接着考虑如何将区域分组。一个显而易见的思路是动态......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......
  • 题解:P4288 [SHOI2014] 信号增幅仪
    很好一题目,使我的最小圆覆盖旋转。先假设\(p=1\)。这是最简单的情况。这个时候我们就得到了一个裸的最小圆覆盖。当\(p\not=1\),但是\(a=0\)的时候。圆就变成了对称轴与坐标轴平行的椭圆,运用高中知识仿射一下,又回到了最小圆覆盖。在一般的情况下,我们先通过坐标的旋转......
  • 《超级机器人大战30》缺少roboex32.dll启动遇阻怎么办?轻松应对《超级机器人大战30》ro
    当《超级机器人大战30》因缺少roboex32.dll文件而启动遇阻时,可以尝试以下几种解决方案来轻松应对这一问题:一、下载并替换缺失的DLL文件寻找可靠来源:首先,需要在互联网上找到可靠的roboex32.dll文件下载源。建议访问官方网站、微软官方下载中心或知名的软件下载站点,以确保下载......