悠然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篇）

CF662C Binary Table FWT

设 \(a[i]\) 为二进制为 \(i\) 的列的数量， \(b[i]\) 为 \(i\) 二进制下前 \(n\) 位中 \(0/1\) 出现的较小值。假设我们对列的修改状态为 \(i\) ，那么这时的 \(ans\) 为 \(\displaystyle \sum_{j}a[j] \times...

2020-03-31

0 0

P4552 [Poetize6] IncDec Sequence 差分

题目不难，但是思路巧妙。我们求出差分数组后，就变成了这三种操作 1.一个数加一 2.一个数减一 3.一个数加一的同时一个数减一我们要让 \(2\) ~ \(n\) 变成 \(0\) ，设所有整数的和为 \(s1\) ，负数的和的绝对值为 \(s2\) ，则最少操作数为 \(max(s1, ...

2020-03-30

0 0

P4592 [TJOI2018]异或可持久化0/1Trie树

对于一段区间查询最大异或值，我们可以用可持久化0/1Trie树来维护。对于一个点的子树，它们的 \(dfs\) 序是一段连续的区间。对于一条路经，我们拆成两个端点分别到达 \(LCA\) 的两条路径，它们的 \(dep\) 是连续的。我们分别建出来 1.以 \(dfs\) 序为外层的...

2020-03-30

0 0

洛谷 P5249 [LnOI2019]加特林轮盘赌概率DP

设 \(f[n][k]\) 为 \(n\) 个人第 \(k\) 个人胜利的概率。初始化 \(f[n][1]=1\) 第一个人要想赢的话第一枪不能中，然后他就相当于成了 \(n\) 个人里的第 \(n\) 个，\(f[n][1]=(1-P_0) \times f[n][n]\) 对于其他人，如果第...

2020-03-30

0 0

洛谷 P1654 OSU! 概率DP

首先说明一点：平方的期望不等于期望的平方，三次方也一样设 \(f[i]\) 为只考虑前 \(i\) 个时的答案若当前格子为 \(0\) ，不会造成额外贡献。若当前格子为 \(1\) ，概率为 \(p[i]\) ，造成的贡献为 \(E(len_i^3)=E((len_{i-1}+1)^...

2020-03-28

0 0

CF900D Unusual Sequences 数论

题目大意给定 \(x,y\) ，求有多少个数列满足其 \(gcd\) 为 \(x\) ，和为 \(y\)。题解设 \(k=x/y\),若 \(k\) 不是整数则无解。否则就是求和为 \(k\) ，\(gcd=1\) 的序列个数容斥考虑：首先和为 \(k\) 的所有序列一共有\(2...

2020-03-28

0 0

洛谷 P3317 [SDOI2014]重建矩阵树定理

题目大意给出一个图，每条边都有一定概率出现，问最后出现一棵树的概率。题解我们平时矩阵树定理所求的就是\(\displaystyle \sum_{T} \prod_{e \in T} Val_e\) 其中\(T\)是树，\(e\)是边。这道题我们要求的就是 \(\displaysty...

2020-03-28

0 0

真·想起啥来就记啥

无源汇有上下界可行流 int main() { cin >> n >> m; S = 0; T = n + 1; for (int i = 1; i <= m; ++i) { x = read(); y = read(); L[i] = read(); r...

2020-03-25

0 0

洛谷 P5131 荷取融合

DP 一个值得思考的 \(DP\) 题。设 \(f[i][j]\) 为前 \(i\) 个中选了 \(j\) 次的方案数， \(g[i][j]\) 为前 \(i\) 个中选了 \(j\) 次的所有方案的价值积的和。枚举上一个选取的位置和次数即可. \(O(n^2k^2)\) \(20\)分空...

2020-03-20

0 0

卡常火车头

#pragma GCC diagnostic error "-std=c++11" #pragma GCC target("avx") #pragma GCC optimize(3) #pragma GCC optimize("Ofast"...

2020-03-18

0 0