zyz_yuanzhe

分类

二分(1) 启发式合并类(1) 哈希(1) 最短路(2) 线段树(1) 题解(2)

/ 注册

全部文章（共8篇）

动态开点线段树学习笔记

动态开点就是为了应付不同的版本的线段树,目前我只会具有单点修改的动态开店线段数,核心就是为每个版本分配一个root.一个版本是依据之前某一个版本修改过来的,而你只是单点修改的话,只会增加log(n)个节点,所以把父亲版本的数据先复制过来,然后再依据是否要修改左儿子和右儿子继续递归下去,在递归时返回新...

2026-04-14

0 6

对系数进行二分,余数单独处理

这是一个比较常见的trick,但是我蓝桥杯cb省赛上面没写出来,所以在这边进行笔记 1蓝桥杯原题链接. 贪心的思考,我们肯定是对当前能提升的倍数最大的进行+b操作,但是数据范围这么大,我们得把系数变换一下,并且寻找一个阈值如果对于位置已经进行了k次操作,那么接下来再操作一次的倍数贡献:(sum+b...

2026-04-13

0 9

蓝桥杯多校模拟赛(个人题解)

A.2026 %4讨论即可,每4位有2个2,202620262026%4为剩下的单独计算 B：子序列钦定当前遍历到j cnt1[i]记录j以前,%6==i的当前下标个数 cnt2[i]记录j以前,%6==i的当前下标两两组合个数所以cnt2[(6-a[j])%6]即为以当前下标的合法子序列个数 ...

2026-04-10

2 25

不容易看出是最短路的题目,但可以用最短路做

如题,有些状态很容易描述,状态较多,且转移起来较为容易,但不好用dp表述的题目,只要状态数<=1e6,甚至<=1e7,且转移(边)数<=1e6甚至<=1e7,我们就直接最短路做 1.调色题Ⅱ 链接赛时这题我使用了很奇怪的写法状压,写的很烦,但赛后看题解才发现可以最短路我们...

2026-04-09

0 15

异或哈希(异或散列)

有些题目,我们需要判断一个区间某个元素出现的次数奇偶,如果元素的种类不多,我们可以使用异或哈希 1.炼金术士的配方(杭电2026春季联赛1) 你可以发现,a[i]<=1e6,质数的种类很少,所以我们可以给每一个质数随机分配一个不同的哈希值,如果区间异或值是0,那么这个区间合法异或值生成代码...

2026-04-09

0 15

笛卡尔树上的启发式合并

有一种题型,是对于一个下标的值作为max/min时,对雨某种满足题目要求性质的子段的计数,而我们知道,值满足堆的性质,下标满足二叉线索树的性质,就是笛卡尔树,处理一个区间,我们只要遍历左右里面长度小的区间,再通过预处理的东西算出结论(可能是预处理,可能是二分) 例1.Max to the Right...

2026-04-09

0 13

最短路中的虚拟点(中转站)

前言:我们再做一些最短路题目时候,往往会因为一些特殊限制导致建的边太多,所以我们建立一种虚拟点作为中转站,大大减少边数 1.HDU春季联赛10.小塔的梦境迷宫题面: 对于走的边数为%3=0,%3=1,%3=2的情况,可以直接拆点,但是如果对于"瞬移"这种情况要建图,那最坏情况将会多见nn条边,所...

2026-04-09

0 19

蓝桥杯省赛模拟赛(第二场)个人题解

A.2026(个人难度评价:洛谷红) 枚举模拟即可,如果数据范围较大可以使用数位dp #include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define int long long #de...

2026-04-08

6 29