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

LG2375/LOJ2246 「NOI2014」动物园 KMP改造

问题描述 LG2375 LOJ2246 题解看了题解，需要回看，需要继续通过本题深入理解KMP。为了将 \(\mathrm{KMP}\) 和只插入了一个模式串的\(\mathrm{AC}\)自动机有机统一，称通常意义下的 \(\mathrm{KMP}\) 的 \(\mathrm{n...

2019-10-07

0 380

LG4824 「USACO2015FEB」(Silver)Censoring KMP+栈

问题描述 LG4824 题解大概需要回顾（看了题解） KMP 先对要删除的模式串进行自我匹配，求出 \(\mathrm{fail}\) 然后再扫文本串的过程中记录一下每个字符匹配的最大长度，用栈进行删除。这类删除一段连续区间的问题常用栈来优化维护 \(\mathr...

2019-10-06

0 488

20191004 「HZOJ NOIP2019 Round #9」20191004模拟

综述第一次 rk1 ，激动。题目是 COCI 18/19 Round #1 的三至五题。得分 \(100+100+20\) \(\mathrm{cipele}\) 问题描述 HZOJ1313 题解二分答案+贪心发现“最大值最小”，自然想到二分答案。对 \(a,b\...

2019-10-04

0 497

LG5357 「模板」AC自动机（二次加强版） AC自动机+fail树

问题描述 LG5357 题解不是fail树的AC自动机复杂度是假的。把AC自动机搞出来，建立Trie树，树上爆搜一遍就好了。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; templ...

2019-10-04

0 457

LG3812 「模板」线性基线性基

问题描述 LG3812 题解线性基是一类擅长解决异或问题的数据结构（也不算数据结构吧...就是一种玄学的东西）对于数列 \(a\) ，它的线性基 \(d\) 为出现 \(1\) 的最高位在第 \(i\) 位的数（这里借用了"帅到报警"的题解）。构造方法 ...

2019-10-03

0 491

LG5003 跳舞的线 - 乱拐弯线性DP

问题描述 LG5003 题解设 \(mx[i][j][0/1]\)代表当前位置、朝向的最大拐弯数，最小同理。来源为左边和上边。坑点：起点可能为#。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespac...

2019-10-03

0 416

20191003 「HZOJ NOIP2019 Round #8」20191003模拟

综述试题为常州集训2019SCDay2 得分\(100+30(0)+28\) 时之终结问题描述 HZOJ1310 题解构造题。发现部分分有一档是 \(Y\) 是 \(2^x\) ，于是自然想到很多个三角形连到一起。然后正解就是在这个基础上删边。 \(\mathrm{...

2019-10-03

0 423

LG3092 「USACO2013NOV」No Change 状压DP

问题描述 https://www.luogu.org/problem/P3092 题解观察到 \(k \le 16\) ，自然想到对 \(k\) 状压。设 \(opt[i]\) 代表使用硬币状况为 \(i\) 时，最多可以买到 \(opt[i]\) 个物品。然后 \(opt[i]...

2019-10-02

0 335

LG4158 「SCOI2009」粉刷匠线性DP

问题描述 LG4158 题解设\(opt[i][j][k]\)代表到\((i,k)\)刷了\(j\)次的方案数。一开始DP顺序有点问题，调了很长时间。务必考虑清楚DP顺序问题 \(\mathrm{Code}\) #include<bits/stdc++.h> ...

2019-10-02

0 359

LG2679 「NOIP2015」子串线性DP

问题描述 LG2679 题解设\(opt[i][j]\)代表A串前\(i\)个，匹配\(B\)串前\(j\)个，选择了\(k\)个子串的方案数。转移用前缀和优化一下。 \(\mathrm{Code}\) #include<bits/stdc++.h> using ...

2019-10-02

0 415