Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 852人学习

11eyes的排位日记

10篇文章 946人学习

0篇文章 0人学习

全部文章（共181篇）

P3523 [POI2011]DYN-Dynamite 来自专栏

Question 给一棵树,树上有一些关键节点，要求你选个点，使得关键节点到这些点中距离的最小值的最大值最小，求这个值。 Solution 显然这道题是可以二分的，二分的好处在于我们将原问题转化为了：对于一个树，选中最少的节点，使得任意关键节点到选中节点的最小距离，请问需要选中多少个节点？这样...

DFS 树上最小点覆盖二分树形DP DP BFS

2021-03-31

2 704

NC11169E 来自专栏

比赛的时候写了个假算法，跑的贼快还AC了，现在看了下确实相当不妥，当时写的两个dp并不同步，运气好，数据刚好没有能卡的罢了，现在来补一下正解。 Solution 遇到问题毫无头绪的时候先从暴力的方法入手然后逐步优化。首先能想到01背包的暴力解法。表示前个数满足: 对于这一维，我们可以...

单调队列单调队列dp dp

2021-03-29

1 680

NC12986K 来自专栏

Solution 遇到比较困难的题目可以先从比较暴力的方法开始入手在结合题目的一些性质、数据范围开始进行优化。思考一下能够想到比较暴力的dp: : 表示第行选了列，一共选了个数的最大值。按上述式子写复杂度是毫无疑问会TLE、MLE，接着开始优化，我们降一维则可以通过本题。仔细观...

DP

2021-03-24

1 563

CF1484E 来自专栏

Solution 每次遇到这种比较复杂的问题的时候，可以先从比较直观的暴力方法去考虑再去思考如何优化。比如这道题，我们比较容易的想到的是的dp转移。定义： : 到第个建筑物的最大美丽值。 : 到之间最矮的建筑物的美丽值，即。为了降低复杂度，DP存在很多种优化方式，而这道题需...

单调栈 dp 单调栈dp

2021-03-24

0 639

NC12606I 来自专栏

Solution 首先很容易看出这道题是一道换根DP。我们首先可以写一个DFS求出以某个节点为根的答案，一般根节点就取1号节点，是因为,一般1号节点是存在的，当然也可以随便取别的。重点是考虑答案的转移。假设已知节点的答案，我们需要哪些信息能够通过一定的方式转移到呢？将转移分为部分维护，左边部分为部...

换根DP 树形DP DP

2021-03-08

2 601

ABC186F - Rook on Grid 来自专栏

Solution 首先容易分析有两种走法：先右再下(包含只右不下) 先下再右对于第1种走法，我们只需要遍历第一行第一个障碍物之前的列，计算每一列遇到第一个格子之前的长度即为贡献。问题在于如何计算第2种走法的同时不重复计算第1种走法。下面为了方便我用表示每一行的限制，表示每一列的限制，及第一个...

树状数组扫描线

2021-02-27

2 811

NC9985H白色长方形来自专栏

Solution 扫描线读题的时候发现重点是，这就大大简化了这道题。首先我们先考虑如何计算某一行的贡献，我们发现如果我们知道连续的白色块的，那么他的贡献就是，那么我们创建一个set<pair<int, int>>去维护当前行的连续白色格子的断点即可，我们对每一列的计算可以将列...

线段树 set 扫描线

2021-02-26

1 683

NC9984E九峰与子序列来自专栏

Solution 哈希 + DP复杂度：首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串[l, r]的部分是否相等。转移方程：表示有多少匹配的方案数。首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串的部分是否相等。然后暴...

哈希字符串 DP

2021-02-25

0 946

NC9986B系数来自专栏

Solution 比赛的时候手推，发现规律，然后打了个表。看到了如下的规律: 0 : 1 1 : 1 1 1 2 : 1 2 0 2 1 3 : 1 0 0 1 0 0 1 4 : 1 1 1 1 1 1 1 1 1 5 : 1 2 0 0 0 0 0 0 0 2 1 6 : 1 0 ...

Lucas

2021-02-24

1 842

NC9985B比武招亲(上) 来自专栏

Solution 枚举贡献,当前的数量为个。对于贡献挑选的有对，对于确定的情况有多少种的选法问题，其实等价于个不同的盒子里放个相同的小球，有多少种放法。下面求个盒子里放个相同的小球，有多少种放法，这本质就是重复组合的问题。有种方法，具体可以看重复组合的定义和证明。将代入，对于确定的情况有...

组合数学

2021-02-24

1 781