-
P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌
典中典题 核心为，先观察出值域较小的情况，然后根号分治分开处理两侧，选择一遍进行状压，另一边用其它算法处理 当 时，直接考虑状压因子，预处理每个数含有哪些因子 设 为当 ， 选择质因子集合为 ， 时的方案数，枚举每个数进行转移 当值域变大，考虑根号分治， ，即 每个数最多含有一个 的质因子 直接状压前 个质因子（)，然后考虑每个数一定属于至多一个 的质因子集合，比如 ，它就属于 ... -
P9019 [USACO23JAN] Tractor Paths P
一个点跑到一个区间+两点最短距离，直接倍增一直跑就行了 找到每个点向左最远的区间 ，向右最优的区间 直接大力倍增跑路 注意倍增跑路一定是 不要取 ，最后再 +1 即可 考虑第二问，设第一问答案为 考虑走到一个特殊点 ，当前走了 步 问题等价于从 出发，走 步可达 维护 这段的特殊拖拉机个数 同理维护 我们 i 4 p 2 q 1 j 从 中间的数字表示跳了多少条边 考虑... -
Kru重构树
Kru 重构树https://www.luogu.com.cn/blog/me-immortal/kruskal-chong-gou-shu https://www.luogu.com.cn/blog/mywd-ylyy/kruskal-zhong-gou-shu 构造的过程很像 生成树 解决 从A点走到B点的所有路径中，最长的边最小值是多少 这类问题 考虑 我们新建节点 ， 的点权为 ... -
Borůvka
Borůvka 求 ，一般用于求完全图 ů 其实是一种多路增广的 算法由一个点开始，往外不断贪心地找最短边，然后不断扩大连通块，直到形成一棵树 而 ů 算法每一次的增广，会对现在的每一个连通块都找一遍的最短边，最后每个连通块择优，将这些边全部连上 对于现在的每个连通块，找到从这个连通块出发，不在最小生成树中的、到达别的连通块的最短边 （注：若权值相同，则需要再按照另一个维度严格排序，... -
Hash
Hash 123456789101112131415ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; //这步其实是将h[l-1]左移} //其目的事实上是为了将h[l-1]的高位与h[r]相对齐从而才可以未完成计算int main(){ ... -
2-SAT
2-SATSAT给定变量 ， 若 为真则 ，否则 给定约束条件 ， 等，每组多个变量个变量 求是否存在一组 的解 2-SAT 定义每组两个变量，共 种关系 这个很像图论的最小割的二分点集问题，我们考虑图论建模 考虑等价问题， 个集合，每个集合两个元素 ， 选择元素，等价于变量为真 表示，当 时， ， 不能同时选 等价于 ， ， 必须同时选/不选 等价于 ， ， 必须选至少... -
ABC277 G
考虑暴力 ， 当前在 ，移动了 次，等级为 的期望 考虑把 融入 状态 我们考虑 显然有 根据 的套路，我们可以得到 直接维护 表示当前在 ，移动了 次， 次项的期望 以及注意是 的贡献，所以是 += 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647... -
P6148 [USACO20FEB] Swapity Swapity Swap S
考虑倍增，我们跑一次是 的，直接倍增跑路即可 首先强行记录一次，记录每个点到了哪个位置，倍增转移一下即可 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<bits/stdc++.h>#define... -
P2331 [SCOI2005] 最大子矩阵
，序列最大的 个字段和 1234567891011121314151617181920212223struct Solve1{ int s[N],f[N][12]; void init() { mem(f,0),mem(s,0); for(int i=1;i<=n;i++) s[i]=s[i-1]+fr(); ... -
浅谈随机化
Here’s something encrypted, password is required to continue reading.
