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

20200408 黑白树

20200408 黑白树题意转化在个点中选择若干个点，将这些点的级父亲以内全部染成黑色，求要把所有点染成黑色至少选多少点。题解考虑下面的这样一种情况傻子才会选红色的点——绿色的点可以完全替代掉红色的点。这样一来，可以等价为红色点。由此可以得到，一个点的可以更换为自...

贪心

2020-04-10

0 570

20200407 树

20200407 树题意转化将一棵树剖分为若干个颜色不同的联通块，求数目。题解这种题目第一反应就是树形dp，但是由于涉及到联通块，所以应当和 dfs 序有一定的关系。 dfs 序可以将一个树形结构映射到一个序列上，从而实现一些操作。树链剖分就是按照特定的顺序对树进行 dfs 序标定，之后...

2020-04-09

0 444

20200403 Shortest Path 贪心

20200403 Shortest Path 下载pdf，获得更好的阅读体验。提取码：f1ji 题意翻译有一棵有个结点的树（为偶数）将其划分为对点对，使得点对间距离综合最小，求该最小值。多测，组测试数据。题解为了值最小，显然尽量不选重的。对于一棵子树，如果它的大小是偶数...

2020-04-02

0 572

20200402 月月查华华的手机序列自动机

20200402 月月查华华的手机下载pdf，获得更好的阅读体验。提取码：06ez 问题简述给出字符串，查询是否为的子串，询问次。查询是否为的子串可以用序列自动机完成。序列自动机在 JSOI2019SC 听过这个科技，现在又查了几个博客复习了一下。序列自动机...

序列自动机

2020-04-01

0 984

2020.04.01 Rinne Loves Edges

下载pdf，获得更好阅读体验。提取码：ke7w。 upd：这好像是 08 年哪个省省选题原题题意转化毒瘤出题人把放在最后，害得眼睛不好的选手一开始没看到想了好长时间... 为一棵树那这样就是一棵根为的树上删除若干条边，使得所有叶子结点都与根不连通。树形 DP 画一棵树，假设 ...

dp

2020-03-31

0 518

滑动窗口 3.30

单调队列模板题每次先把已经超过范围的扔掉。然后把范围内不可能成为最优解的扔掉。然后入队。很久以前写的代码： #include<iostream> #include<cstdio> using namespace std; #define maxn 10000007 ...

2020-03-29

0 537

NC15553

首先有暴力枚举左端点和右端点的做法，加上前缀和优化，时间复杂度为发现时间复杂度瓶颈在于枚举左右端点，考虑从这里着手优化。发现枚举左端点后右端点最优解确定，所以可以只枚举左端点，时间复杂度答案为。

dp

2020-03-27

0 472

【题解】NC13230 区间DP

设代表字符串中至个字符，字符串中至个字符是否能构成回文串。然后区间DP套路转移。时间复杂度 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int max...

dp

2020-03-25

0 773

牛客OI周赛14 PJ

Prologue 菜的真实，普及都 AK 不掉.. Score: 100 + 100 + 100 + 0 = 300 rank: 16 A String 看来 PJ T1 考字符串读入成铁上钉钉了？考虑开桶，记录 ASCII 为的字符是否出现即可。 #include<bits/st...

暴力

2020-03-25

0 451

【题解】NC50439

考虑枚举，显然有贪心做法：取超过武力值最大的个人。发现从小到大枚举，每次要把不符合条件的删掉，再筛选个，不太容易。考虑倒序枚举，这样不符合条件的只用筛选一次，用堆维护即可。

堆

2020-03-25

0 428