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)

/ 注册

全部文章 / 题解（共13篇）

NC11169E 来自专栏

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

单调队列单调队列dp dp

2021-03-29

1 680

NC12986K 来自专栏

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

DP

2021-03-24

1 563

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

NC14704 美味佳肴

Question 给定n个食物素材和m个食物种类，每个食物素材具有不新鲜度b，每个食物具有特定且唯一的食物素材编号为j，美味值a和做菜所需要的时间c。食物美味值，求T时刻，最大美味值为多少？ Solution 每个食物的美味度只和他完成的时间点有关。两个食物若默认比先做后做的区别在于: 我们对其排序...

DP 01背包

2020-04-28

0 683

NC17065 子序列

Question 一个由n个元素组成的序列，她想知道其中有多少个子序列，满足对于所有的成立。 Solution 盲猜当满足时前后都是单调递增的。严格证明(来源于雨巨的题解！我估计我可能真的做的时候会盲猜试一发，或许这是一种直觉？)然后DP求对应的贡献即可，设表示必选第i个的情况下有多少种满足的取法,...

dp

2020-04-28

0 524

NC51180

题意给定一棵个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。思路换根DP这种题往往都是先从某个点出发，求出以这个节点为根的答案，并记录与答案相关的数据到数组中。然后从节点出发，记录换根的答案，其中所有根的最大值就为所求值。难点在于该如何去找寻其中的递推关系式。数组表...

树换根dp DP

2020-04-17

0 642