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)

/ 注册

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

NC9985A美丽的路径来自专栏

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

DFS 二分

2021-02-23

4 623

K叉哈夫曼树

定义：哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 K叉哈夫曼树：哈夫曼树的构造方法是贪心的每次选最小的几个节点构造。当的时候需要预处理一下，因为可能最后一步合并操作的点数不到K个节点，这样的话就不是最优的了。预处理方法：当时：加入个权重为0的虚拟节点。将个节点先合并为1个节...

二分 K叉哈夫曼树数据结构

2020-09-17

0 1108

牛客练习赛63

A.牛牛的三角形输出边长能组成三角形的三条边或者"No solution" Solution 暴力瞎搞搞其实排序之后可以优化到但是不影响能过。 Code #include<bits/stdc++.h> using namespace std; typedef long long ll...

二分

2020-05-08

1 686

NC14301 K-th Number

Question 将所有连续区间中第K大的数放入一个新的数组B中，求数组B中第M大的数为多少？ Solution 二分+尺取答案具有单调性，故考虑二分。看了邓老师的题解之后发现居然可以二分诶那么问题就是check函数该如何写了，这里要用到尺取法判断。我们求任意连续区间中第K大的数的数量，若数量则L...

二分尺取

2020-04-23

0 620

NC5157 A-聚会

Question 一个数轴，牛牛的家在0点处，在道路上的整数点上建立两个传送门，朋友们可以通过传送门从一个位置瞬间传送到另一个位置，在最优策略下，朋友们最晚需要多长时间可以到达聚会地点？ Solution 答案具有单调性，二分答案。接下来就是check函数怎么写的问题了。牛牛的朋友到0点距离小于...

二分

2020-04-19

0 827

NC23049

题意你有段小木棍，对每段小木棍切割，要求得到段长度相等为(正整数)的小木棍，求最大为多少？思路答案具有单调性，故考虑二分，时间复杂度 #include<bits/stdc++.h> using namespace std; typedef long long ll; typede...

二分

2020-04-16

0 626

NC5026E

NC5026E 题意把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？思路二分+哈希字符串时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表...

哈希字符串二分哈希

2020-04-12

1 680

NC23053

NC23053 题意给你一个字符串s，给你T组数据，每组数据输入一个字符串t，对该字符串判断是否为s的子串，若为子串则输出"YES"否则输出"NO"。思路预处理二分查找最坏复杂度数据范围这么大，暴力是肯定要超时的，贪心每次必取s串中的第一个没用过的字母和对应的t的字母进行匹配，这样才能...

预处理二分

2020-04-02

0 594