悠然w

分类

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章（共232篇）

ODT 珂朵莉树详解

人们都说珂教兴国，无奈珂学家里数我最菜，只会背一背ODT板子珂朵莉镇楼名字来源 ODT全称Old Driver Tree，中文名珂朵莉树有人为了CF896C发明了这个算法，这道题又和珂朵莉有关，所以这个算法叫做珂朵莉树另外，由于发明者(lxl)的原因，也珂叫ODT(Old D...

2021-07-17

0 0

P1337 [JSOI2004]平衡点 / 吊打XXX 模拟退火

模拟退火模板题，不会可以看这里一个位置到所有点的dis*weight的和越小越好 #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<...

2021-07-17

0 0

模拟退火详解

本算法建议谨慎使用，否则一不小心就会变成模拟退役爬山算法爬山算法是一种贪心搜索，每次从当前状态的所有后继状态中选择一个最优解继续搜索，直到达到一个局部最优解后不再搜索。优点：好写缺点：容易陷入局部最优解出不来就像下图一样多随机几个初始状态就能减小(不能消除)缺点模拟退...

2021-07-16

0 0

随机化算法

只要你敢想，没啥能挡得住你拿分遇到不会的题，随机化算法也不失为一种很好的对策无论你是欧皇还是非酋，在极大似然法面前众生平等生成随机数 cout<<rand();会输出一个随机数，需要用到cstdlib库但是，这些随机数是伪随机数，每次输出的都一样。需要这么做sran...

2021-07-16

0 0

BZOJ 3150 [Ctsc2013]猴子概率&期望+高斯消元

概率&期望首先遇到这到题我们可以想出来一个DP的方法,设 \(f[S]\) 为当前小Q手里的牌的状态为 \(S\) 时，小Q能赢的概率. 我们枚举 \(S\) 能转移的其他状态，就能列出来转移方程，一共有 \(2^n\) 个方程. 解方程我们需要用到高斯消元，所以这样做时间复杂度为 ...

2021-07-16

0 0

bzoj 2554 Color 概率与期望

这道题是真的考验得分技巧如果n<=5,那么直接用随机数模拟 n大一点的时候呢？我们分开单独考虑每一个颜色考虑一个颜色时，可以把这个颜色看成白球，其他颜色看成黑球，我们要求的就是全部变成白球的期望步数，此时我们设\(f[i]\)为当前有i个白球，全部变成白球的期望步数而且我们每...

2021-07-16

0 0

P7426 [THUPC2017] 体育成绩统计模拟

题目链接写这道题最重要的是条理清晰。除了阳光长跑外，其他的都能在读入的时候处理掉。处理阳光长跑最头疼的就是处理时间。把时间单位都变成秒就好啦。我们算出从2017年1月1日0点到这时刻有多少秒就行啦。代码注释很详细，具体看代码吧。 #include<algorithm&...

2021-07-16

0 0

CF570D Tree Requests 树上差分/dsu on tree

判断能否构成回文很简单，出现次数为偶数的不用管，出现次数为奇数的最多有一个可以用状压储存出现次数的奇偶情况，判断的时候 puts(ans[i]==(ans[i]&(-ans[i]))?"Yes":"No"); 这里用到了树状数组的lowbit求法 ...

2021-07-14

0 0

CF600E Lomsat gelral dsu on tree

dsu on tree模板题 dsu on tree详解暴力显然\(O(n^2)\) O(TLE) 我们发现，在对某个节点的树做统计前，最后一个儿子的那棵子树统计不用清空并且，这个不用清空的儿子size越大，显然越优挑size最大的来就行 O(nlogn) #include<...

2021-07-02

0 0

dsu on tree详解

dsu 中文名是并查集，然而除了启发式合并，这个算法和并查集并没啥关系。适用范围: 1.没有修改 2.询问子树流程模板题题解暴力显然\(O(n^2)\) O(TLE) 先分析一下暴力的思路，我们是对每一棵子树做O(n)的统计更确切地说，我们是对一个节点的儿子的那棵子树...

2021-07-02

0 0