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

LG1879 「USACO2006NOV」Corn Fields 状压DP

问题描述 LG1879 题解设\(opt[i][j]\)代表前\(i\)行，且第\(i\)行状态为\(j\)的方案数。枚举\(j\)，再枚举\(k\)，\(k\)为上一行的状态。判断\(j,k\)能否共存（j&k==0）计数转移即可。必须加强位运算能力。 \...

2019-09-30

0 387

LG1410 子序列二分图判定

问题描述 LG1410 题解如果\(i<j,a_j \le a_i\)，那么他它们不能在一个上升序列中。于是在\(i,j\)之间建边，看建出来的图是不是二分图即可。 \(\mathrm{Code}\) #include<bits/stdc++.h> usin...

2019-09-30

0 389

LG5367 「模板」康托展开康托展开

问题描述 LG5367 题解康托展开公式： \[ans=1+(\sum_{i=1}^{n}{a_i})\times(n-i)!\] 用树状数组维护一下\(\sum\)里面的东西，前缀积维护后面的东西。 \(\mathrm{Code}\) #include<bits/st...

2019-09-29

0 467

LG2578 「ZJOI2005」九数码游戏 bfs

问题描述 LG2578 题解用string+map去重。 bfs即可。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; void read(int &x){ x=0;ch...

2019-09-29

0 492

LG1131 「ZJOI2007」时态同步树形DP

问题描述 LG1131 题解正难则反，把从一个点出发到叶子结点看做从叶子结点走到那个点。 DP方程很显然。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; #define int lon...

2019-09-27

0 376

LG2145 「JSOI2007」祖码区间DP

问题描述 LG2145 题解把颜色相同的一段看做一个点。然后类似于合唱队区间DP即可。但是这题好像出过一些情况，导致我包括题解区所有人需要特判最后一个点。 \(\mathrm{Code}\) #include<bits/stdc++.h> using name...

2019-09-25

0 373

UVA1401 Remember the word DP+Trie

问题描述洛谷（有翻译）题解 DP，设\(opt_i\)代表前\(i\)个字符方案数。 Trie优化，刷表法。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <...

2019-09-25

0 397

LG5202 「USACO2019JAN」Redistricting 动态规划+堆/单调队列优化

问题描述 LG5202 题解 \[opt[i]=xx+(cnt[i]-cnt[yy]<=0)\] 发现\(cnt[i]-cnt[yy] <= 0\)只能有两种取值于是直接堆优化即可 \(\mathrm{Code}\) #include<bits/stdc++...

2019-09-22

0 429

模拟赛总结合集

20190922 HZOJ NOIP2019 Round #7 20191003 HZOJ NOIP2019 Round #8 20191004 HZOJ NOIP2019 Round #9 20191102 HZOJ NOIP2019 Round #12

2019-09-22

0 404

LG5201 「USACO2019JAN」Shortcut 最短路树

\(\mathrm{Shortcut}\) 问题描述 LG5201 题解最短路树。显然奶牛的路径就是从\(1\)走到各个草地，于是从\(1\)跑最短路，构建最短路树。为了保证字典序，从\(1\)到\(n\)依次枚举每个结点，构建。显然，用贪心的思想，这条边一定是从某个结点\(x...

2019-09-22

0 638