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

NC11169E 来自专栏

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

单调队列单调队列dp dp

2021-03-29

1 680

NC12986K 来自专栏

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

DP

2021-03-24

1 563

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

NC9985A美丽的路径来自专栏

Question 给定点权无向图，求任意由到的路径中最大的第小的点权。 Solution 二分答案，假设答案为，则对于第小的点权，我们将其转化为该路径上有的点，他们的点权值。我们将路径上的点染色分为两种点：，染为。，染为。有如下情况：一. 与不联通，二. 与联通，路径上存在两个连续...

DFS 二分

2021-02-23

4 623

NC9985D石子游戏来自专栏

Solution 一遍贪心的差分就够了，从开头往后插有三种情况：代表a[i]处的差分前缀和说明两者相等，无需操作。 a. 说明前方的数都要增加，那么显然。 b. a. 说明后方的k个数都要增加$ ...

差分

2021-02-23

1 614

牛客题霸NC65题解

题目题解斐波那契数列： Code class Solution { public: int Fibonacci(int n) { int f[40]={0,1}; for(int i=2;i<=n;i++) f[i]=f[i-1]+f...

求职题解 leetocde 刷题

2020-11-26

2 647

NC8282C

Solution 对于任意一组我们可以使其中间的数与之构成一个等差数列，利用数形结合，使每个数的，，这在几何学上就是一个凸壳。问题转换为求一个凸壳并计算答案。凸壳需要满足：对于任意三个点，，由于除法有精度误差，上式转换为乘法。若不满足上述条件则点需要删除。最后对维护之后的凸壳进行等差数列求和...

凸壳数形结合计算几何数学

2020-11-07

3 750