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人学习

全部文章（共16篇）

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

NC9984E九峰与子序列来自专栏

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

哈希字符串 DP

2021-02-25

0 946

NC7509B

NC7509B 求含有子序列的最短子串长度为多少 Solution 1 时间复杂度：思路：由于是唯一的，没有重复的字符，所以可以用十个指针维护十个位置，使得满足题目要求，每个指针指向中的字符，然后遍历一边，记录满足要求的最小值即可。 Code #include<bits/stdc++.h>...

指针 DP

2020-09-26

13 524

NC6874C-光玉小镇

NC6874C-光玉小镇求从走完所有再回到所需的最小时间为多少，每经过一次T时间需要停，走一步的时间是.若不能走完所有的，输出，否则输出所需的最小时间。 Solution 状压DP+BFS难点：有多个，我们需要先确定的顺序。注意到的范围，我们从状压DP的经典题TSP问题中得到启示，我们可以...

DP BFS 状压DP

2020-09-17

2 771

NC5556E 简单瞎搞题

Question 一共有个数，第个数是，可以取中任意的一个值。设，求种类数。 Soltuion 分组背包一共有组，这道题难点在于数据的压缩要用到bitset，这是我第一次接触bitset，推荐一篇介绍bitset的博客。表示可以被构造出来，表示可以被构造出来，最后可以构造的种类就是中...

状态压缩 DP 状压DP

2020-05-12

0 636

牛客IOI周赛16-普及组

A-求导 Question 求在次导后前的系数。 Solution Code #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const d...

DP 树形背包

2020-05-01

3 867