-
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.
-
P8817 [CSP-S 2022] 假期计划
首先把 ， 转换成两点距离 考虑到枚举四个点不行，但是 可以，我们考虑枚举两个点，然后 找出剩下两个点 首先 预处理每个点 之内的点，并求出这些点中到 距离 的权值最大的点 ，注意不要选到自己了 我们考虑答案为 但是则海洋 可能与 重复，这样是不合法的，所以我们每个点要预处理前三大的点权点，因为至多为第一大第二大都被 占掉 ， 123456789101112131415... -
P6064 [USACO05JAN] Naptime G
考虑不是环怎么做 我们只用考虑当前选不选 考虑前 个数，选了 个，当前数选/不选我们考虑跨过 的情况，一定强选了 睡觉，我们再钦定 强制睡觉，这样就可以得到等效的情况 即 ，答案取 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354... -
浅谈随机堆
Here’s something encrypted, password is required to continue reading.
-
P9378 [THUPC 2023 决赛] 物理实验
字典序/次幂贪心模型 显然从 ，我们选择的答案是一个前缀状态，保住一个胜过后面所有的 问题等价于，当前有答案集合 ，求加入元素 是否合法 判定就是枚举每一轮宇宙射线 我们考虑到已经有 了，我们可以直接找出来每轮宇宙射线轰掉哪个，即未被轰掉，未被保护的第一个元素 此时可以得到另一个性质 ， 中的每一个元素都必须要在被轰掉之前做完，判定时候即可求出每一个元素最晚的做掉时间， 问题等价于，我们...
