expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

CSP2019 S2滚粗记

最好分数：100+20+10+64+64+55 最坏分数：100+20+10+64+36+55 咕咕数据分数：100+25+10+64+60+55 CCF官方： 100+35+10+64+36+55=300 大概是要退役了吧。 \(\mathrm{Day0}\) 早晨并没有睡懒觉，7...

2019-11-16

0 506

BZOJ2591/LG3047 「USACO12FEB」Nearby Cows 换根树形DP

问题描述 BZOJ2591 LG3047 题解换根树形DP。设 \(opt[i][j]\) 代表当 \(1\) 为根时，\(i\) 为根的子树中，到 \(i\) 的距离为 \(j\) 的权值和。此时我们就可以得到 \(1\) 号结点的答案。考虑...

2019-11-11

1 638

BZOJ1369/LG4395 「BOI2003」Gem 树形DP

问题描述 LG4395 BZOJ1369 题解发现对于结点 \(x\) ，其父亲，自己，和所有的孩子权值不同，共 \(3\) 类，从贪心的角度考虑，肯定是填 \(1,2,3\) 这三种。于是套路树形DP，设 \(opt[x][1/2/3]\) 代表以 \(x\) 为根的子树中，且 ...

2019-11-11

0 500

BZOJ2073 「POI2004」PRZ 状压DP

问题描述 BZOJ2073 题解发现 \(n \le 16\) ，显然想到状压设 \(opt[S]\) 代表过河集合为 \(S\) 时，最小时间。枚举 \(S\) 的子集，进行转移枚举子集的方法对于 \(j\) 为 \(k\) 的子集当知道 \(j\) 时 fo...

2019-11-11

0 432

BZOJ1688 「USACO05OPEN」Disease Manangement 背包+状压DP

问题描述 BZOJ1688 题解背包，在转移过程中使用状压。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <typename Tp> void read(...

2019-11-11

0 488

BZOJ2733/LG3324 「HNOI2014」永无乡权值线段树合并

问题描述 BZOJ2733 LG3224 题解对于每个结点建立一棵权值线段树。查询操作就去查询第 \(k\) 大，合并操作就合并两颗权值线段树。并查集维护连通性。同时 STO hkk,zcr,zzk \(\mathrm{Code}\) #include<bit...

2019-11-11

0 425

LG2996 「USACO10NOV」Visiting Cows

问题描述 LG2996 题解和没有上司的舞会双倍经验？ \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <typename Tp> void read(Tp ...

2019-11-10

0 469

LG3237 「HNOI2014」米特运输树形DP

问题描述 LG3237 题解问题转化为：要求将这棵树，满足结点 \(x\) 所有孩子权值相等结点 \(x\) 权值等于所有孩子权值和将乘法转化为 \(\log\) 加法 \(\mathrm{Code}\) #include<bits/stdc++...

2019-11-10

0 422

BZOJ4027/LG4107 「HEOI2015」兔子与樱花树形DP+贪心

问题描述 LG4107 题解首先，我们可以直接令结点 \(x\) 的权值为 \(c[x]+son_x\) ，发现将 \(x,y\) 合并，相当于增加 \(c[x]+c[y]-1\) 的重量。容易想到对于每个结点 \(x\) ，贪心的从小到大合并 \(c[y],y \in son(x)...

2019-11-10

0 492

LG4556 [Vani有约会]雨天的尾巴动态开点线段树+线段树合并

问题描述 LG4556 题解对于每一个结点，建立一棵动态开点线段树。然后自低向上合并线段树。同时维护整个值域的最大值和最大值位置。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; ...

2019-11-10

0 531