代码编织梦想

【luogu p3295】萌萌哒(并查集)(倍增)_csdn萌萌哒-爱代码爱编程

萌萌哒 题目链接:luogu P3295 题目大意 给你一个大的数,然后有一些限制条件是如果把这个数看做一个串,有几对长度分别相同的子串是相同的。 然后问你有多少个数满足条件。 思路 可以发现基本跟数字没关系,就唯

【loj 2788】管道(树上差分)-爱代码爱编程

管道 题目链接:LOJ 2788 题目大意 给你一个 n 个点 m 条边的无向图不一定连通,把每个连通块看做子图,求每一个子图的桥。 n 1e5 m 6e6 空间 16 MB 思路 发现存不下所有的边,但是能存点。

【ybt2023寒假day2 b】树上距离(分块)(lca)(dp)-爱代码爱编程

树上距离 题目链接:YBT2023寒假Day2 B 题目大意 一棵树,边有边权,每次给出 l,r,x,求 x 号点走到编号在 l~r 之间最近的点的距离。 思路 这题还有其它方法,比如线段树分治+线段树,点分树+线

【luogu p1600】天天爱跑步(线段树合并)(lca)_weixin_43346722的博客-爱代码爱编程

天天爱跑步 题目链接:luogu P1600 题目大意 有一棵树,给你若干条路径,对于每个点,有一个数 x,求出有多少条路径的第 x 个点是当前点。 思路 考虑把路径拆成两个部分,向上和向下。 考虑对于每个点建一

【luogu CF1654F】Minimal String Xoration(倍增)-爱代码爱编程

Minimal String Xoration 题目链接:luogu CF1654F 题目大意 给你一个长度为 2^n 的字符串 s,然后你要选一个在 0~2^n-1 中的数 k,使得变换得到的字符串 t 字典序最大。 变换操作为 t[i]=s[i⊕k],输出 t 这个字符串即可。 思路 考虑设

【YBT2022寒假Day6 C】【luogu CF1063F】子串选取 / String Journey(SAM)(线段树)(倍增)-爱代码爱编程

子串选取 / String Journey 题目链接:YBT2022寒假Day6 C / luogu CF1063F 题目大意 给你一个字符串,要你找最大的 k 满足你可以从左往右一次选 k 个不交子串,满足前一个是后一个的真子串。 思路 首先我们考虑小小贪心一下,每个子串肯定是之前的长度减一,那么长度就是:

【luogu P4238】【模板】多项式乘法逆(NTT)(倍增)-爱代码爱编程

【模板】多项式乘法逆 题目链接:luogu P4238 题目大意 给你一个多项式 F(x),要你求一个多项式 G(x),使得 F(x)*G(x)≡1(mod x^n),系数对 998244353 取模。 思路 考虑用倍增的方法。 首先只有 1

【luogu P4308】幸福路径(倍增)(模拟)-爱代码爱编程

幸福路径 题目链接:luogu P4308 题目大意 给你一个有向图,点有点权,然后你一开始的体力是 1,某走一步体力会乘上一个小于 1 的小数,然后到每个点的分数是当前体力乘那个点的点权。 然后一条路径的分数是它每次经过点的分数和,然后要你求最大的路径分数保留一位小数的结果。 思路 你会发现数的值域很小,而且只用保留一位小数。 然后你发现随着

【ybtoj高效进阶 21174】景区旅行(二分)(倍增)(状压DP)(DP)-爱代码爱编程

景区旅行 题目链接:ybtoj高效进阶 21174 题目大意 给你一个无向图,边有贡献,然后你有一个油量,每走一条边油量减一,然后总贡献加上边的贡献。 然后你的油量不能是负数,你可以在一些地方加油,你有油量上限,每个地方也有能加到的油量,你的油量会变成这两个的最小值,然后每个地方加油也有对于的费用。 然后多次询问,每次告诉你出发点,要的总贡献和有的钱

【ybtoj高效进阶 21168】打字机器(Trie树)(LCA)(值域线段树)-爱代码爱编程

打字机器 题目链接:ybtoj高效进阶 21168 题目大意 要你实现一些操作: 在末尾加字符或删字符,记录当前的字符串。 将记录的第 i 个字符串的第 j 个字符设为不可匹配字符,即它不可以与任何字符匹配,两个不可匹配字符和不可以匹配。(如果这个位置原来就是,就改回之前的字符) 求两个记录下来的字符串的最长公共前缀。 思路 首先是找到那些记录的

Snow的追寻(线段树)(LCA)-爱代码爱编程

Snow的追寻 题目大意 给你一棵树,每次规定两个子树不能到,问你树上的最长路径长度。 思路 看到有关子树,考虑用 dfs 序来搞。 而且一般这种子树的操作会用到线段树? 考虑用线段树维护,维护 l ∼

【jzoj 4498】回文树(并查集)(倍增)(LCA)(ST 表)-爱代码爱编程

回文树 题目链接:jzoj 4498 题目大意 给你一棵树,然后你要给每个点给上一个字母。 有一些限制条件,要求某一段路径在填好之后是一个回文串。 问你总有有多少种方案满足限制条件。 思路 首先不难从回文串中看出它就是让一些位置规定要字母相同。 那关系之间就只有相同和任意。 那你就需要找到有多少互补相干的,那这么多个

幸运数字(qlog^2G 做法)-爱代码爱编程

幸运数字 题目链接:luogu P3292 题目大意 给你一个树,点有点权。 多次询问,每次问你树上的一条路径,它上面所有点任选记得,使得它们点权的异或和最大。 思路 n l

幸运数字(nlog^3n 做法)-爱代码爱编程

幸运数字 题目链接:luogu P3292 题目大意 给你一个树,点有点权。 多次询问,每次问你树上的一条路径,它上面所有点任选记得,使得它们点权的异或和最大。 思路 q l

【luogu P7599】雨林跳跃-爱代码爱编程

雨林跳跃 题目大意:luogu P7599 题目大意 有一排数,它们互不相同。 我们将移动定义为向左或向右走到第一个大于它的数。 现在多组询问,每次给出起点范围和终点范围,要你选起点终点,然后能走到而且用的步数最少。 如果无论如何都走不到终点就输出 -1。 思路 小性质 首先我们要发现一些性质: 是不会有跳到终点区间右边再跳回来的情况。因为终点

【luogu P3703】树点涂色-爱代码爱编程

树点涂色 题目链接:luogu P3703 题目大意 给你一个树,每个点有颜色,初始互不相同,根节点是 1,要你维护几个操作。 给一个从根出发的路径上点染上一个新的颜色。 询问一个路径中的点有多少种颜色。 找在一个子树中找一个点使得它到根节点的路径上的点的颜色种数最多。 思路 首先我们看到染色一定是从根节点出发的一条路径。 那我们会联想到 LC

【ybt金牌导航2-2-3】【POJ 3693】连续重复子串 / Maximum repetition substring-爱代码爱编程

连续重复子串 / Maximum repetition substring 题目链接:ybt金牌导航2-2-3 / POJ 3693 题目大意 给你一个字符串,要你找一个子串,让它可以由另一个子串复制 x 次得到,而且这个 x 是最大的那个。 要你输出这个子串。 思路 首先你看到复制多次得到,想到可以用 LCP 来求。 什么意思呢?画个图就清楚了

【ybt高效进阶4-5-6】【LOJ 10133】【luogu P4180】次小生成树 / 严格次小生成树-爱代码爱编程

次小生成树 / 严格次小生成树 题目链接:ybt高效进阶4-5-6 / LOJ 10133 / luogu P4180 题目大意 给你一个图,要你求这个图的次小生成树。 次小生成树就是边权之和大于最小生成树边权和的生成树的边权之和最小的一个。 一定要严格大于,保证一定存在,输出这个边权和。 思路 首先看到次小生成树,我们考虑先把最小生成树弄出来。

【ybt高效进阶4-5-5】【luogu P2680】运输计划-爱代码爱编程

运输计划 题目链接:ybt高效进阶4-5-5 / luogu P2680 题目大意 有一个树,边有权值。 然后有一些路径,然后你可以选一条边,使它的权值变成 0。 要你让修改后最长的给出路径最短,输出这个值。 思路 首先看到要求树上路径的距离,先会想到 LCA。 但是它可以改变权值。 那我们就从最长路径最短这个方面下手,想到二分这个长度。 那左

【ybt高效进阶4-5-4】【luogu P1967】货车运输-爱代码爱编程

货车运输 题目链接:ybt高效进阶4-5-4 / luogu P1967 题目大意 有一些点,然后又一些有权值的边。 然后多组询问,每次给你两个点,要你找一条路径,使得这条路径上权值最小的边的权值最大。(输出权值) 如果没有路径就输出 -1。 思路 那首先我们看到它是找路径,然后路径不是权值相加,而是权值的极值。 自然想到贪心弄一个最大生成树的东