首页 > 其他分享 >ABC321题解

ABC321题解

时间:2023-09-28 22:44:19浏览次数:44  
标签:题解 clac 即可 ABC321 text 我们

以后应该都是从 E 开始。

E:

problem

LCA题。

我们枚举向上跳 \(t\) 步,跳到了 \(y\)。

假如说 \(t = 0\) 那么我们计算 \(\text{clac}(x,k)\) 即可。(\(\text{clac}\) 怎么算放在最后讲)

否则 计算 \(\text{clac}(y,k) - \text{clac}(x >> (t - 1),m - t - 1)\) 。(建议自己理解一下)

那么如何算 \(\text{clac}\) 呢?

我们发现点的编号是连续的,所以我们只需要求出最小的值和最大的值即可。

所以我们要求的就是以 \(x\) 为根节点,深度为 \(d\) 的每一个点。

所以就做出来了!

code

标签:题解,clac,即可,ABC321,text,我们
From: https://www.cnblogs.com/Carousel/p/17736623.html

相关文章

  • P2427 题解
    洛谷链接题目简述给定\(N\timesM\)的字符矩阵,有\(Q\)次询问,对于每次询问给出\(x,y\),求以\((x,y)\)为中心的最大正方形边长且正方形中字符均相同。思路看到数据范围较小,可以考虑深搜解决,约掉常数的时间复杂度最坏为\(O(q\times\min(n,m))\),勉强可以通过。(不过代码......
  • AT_arc111_a 题解
    洛谷连接&Atcoder链接题目简述给定两个数\(n\)和\(m\),输出\(\left\lfloor\frac{10^n}{m}\right\rfloor\bmodm\)的值。数据范围:\(n\le10^{18},m\le10^4\)思路首先看到数据范围还是很大的,直接快速幂会炸,所以需要一些优化操作。推理如下:\[\left\lfloor\frac{10^n}......
  • AT_agc019_b 题解
    洛谷链接&Atcoder链接。题目简述给定一个字符串\(A\),可以选择区间\([i,j]\)翻转一次,求能得到多少本质不同的字符串。(\(A\)的长度不超过\(2\times10^5\))。思路首先解释本质不同的含义,即不完全相等的两个字符串(可能\(A\)是\(B\)的字串)。如果想直接求得答案显然是不......
  • P1989 无向图三元环计数 题解
    P1989无向图三元环计数题解考虑对无向图的边定向:对于每一条无向边,度数小的点向度数大的点连边,如果读书相等则按编号大小确定。这样枚举一个\(u\),再枚举它的出点\(v\),接着枚举\(v\)的出点\(w\),如果存在一个\(w\),\(u\)向它连边,那么\((u,v,w)\),就对应了原图中的一个三......
  • 加训日记 Day3——atcoder ABC321乐子场
    Day3,9.23  ·打了场acwing周赛,第三题差点就想出来了,想歪到组合数上乱选了呜呜呜  ·ABC321场写的太抽象了,A题上来wa两次,B题少考虑情况乱wa  ·C题更是重量级,想不出来正确做法直接暴力,结果打表最后少写了几个数,纯纯犯病场  ·最后加了36分没绷住acwing周赛排名atcod......
  • SOJ1835 题解
    题意给出一个\(1,\dots,n+1\)的排列\(v_{1},\dots,v_{n+1}\)与两组权值\(a_{1,\dots,n},b_{1,\dots,n}\)。满足\(v_{n+1}=n+1\)。构造一张\(n+1\)个点的有向图:对于\(i=1,\dots,n\),从\(i\)向\(i+1\)连一条权值为\(a_i\)的边;对于\(i=1,\dots,n\),找到最小的\(i......
  • LOJ 6479 [ICPC World Finals 2017] 小小水管工 Son of Pipe Stream 题解
    更好的阅读体验题意原题链接给出\(n\)个城市和\(m\)条双向管道,以及两个实数\(v\)和\(a\)。有两种液体,分别是水和Flubber(下面简写为W和F)。\(1\)号和\(2\)号城市分别生产Flubber和水,并通过管道流入\(3\)号城市。对于一条管道,其中可以同时存在两种液体,但是方向......
  • Jenkins问题解决_控制台输出:Windows下中文乱码,文本方式查看显示正常
    背景使用Git克隆代码时出现错误,控制台输出内容为中文乱码,文本方式查看显示正常Jenkins版本:2.423原因Jenkins内JAVA编码设置问题查看jenkins编码格式系统管理——>系统信息,查找sun.jnu.encoding字段。如果不是UTF-8,就可能导致中文支持有问题(GBK等支持度不够)。解决设......
  • 题解 [HEOI2016/TJOI2016] 排序
    题目链接看到这道题按照套路首先想到二分答案(即二分\(q\)位置上的数,记作\(mid\))。再按照套路将大于\(mid\)的数字设为\(1\),将等于\(mid\)的数设为\(2\),小于\(mid\)的数字设为\(0\)。那么对于区间\([l,r,0]\)操作,应该先讲\(0,1,2\)的数量找出来,然后按照从小到大......
  • 题解 CF1873H【Mad City】
    其他题解怎么又Tarjan又Dijkstra的,这是div4H的样子吗,来个简单好写的做法。题面里的人名太复杂了,本题解中称为警察和小偷。注意到,如果小偷成功到达了环上,那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里,他可以执行相同的操作(顺时针/逆时针/静止),使得他和警察之间......