shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

Sand Fortress 来自专栏

思路挺简单的题...二分答案.因为凸函数价值最高,那么我们尽量凸起,然后ck一下,唯一的坑点就是会爆ll,这里的话使用__int128. 总的来说这题就是. code #include <bits/stdc++.h> using namespace std; typedef long ...

二分贪心

2021-03-19

3 851

Tree Decoration 来自专栏

思路不要想复杂就好了...贪心的选取子树中最小的那个,多了就不要选,少了就更新数量...一个dfs就可以解决了.. 代码 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long...

dfs 贪心

2021-03-08

0 716

Microtransactions (hard version) 来自专栏

思路二分答案,贪心验证.我们二分出最少需要多少天可以做完.然后贪心的把所有做的,推到我们二分答案限度内的最后一天,不是在我二分答案外的最后一天.不然类似下面的数据就过不去. 4 7 23 78 12 46 100 1 41 3 213 2 321 3 12 2 87 1 76 2 213然后本题...

二分贪心

2021-02-19

2 729

Stars Drawing (Hard Edition) 来自专栏

思路: 这题思路还是比较好的,对于这种十字形状的图形,我们可以设置一个表示这个点上下左右四个方向可以延续的长度是多少.然后转移十分简单,这里就不写了.然后我们贪心的把每个可以取的位子全部取了,都取.最后再前缀记录一下是否被全部覆盖,假如存在没有被覆盖的,那么答案就输出.否则就是所有存在里的答案了. ...

贪心 dp

2021-02-07

4 613

Generating Sets 来自专栏

思路: 我也不知道为什么写这个代码调了一会.思路其实比较简单,就是维护一个,从大的能消则消,不能消则加入答案,这样一次一次的变小,最后集合肯定是一个最小的,因为我是从最大的开始消的.每次操作是次,维护一个,然后时间复杂度应该是具体实现过程见代码. 代码: #include <bits/stdc...

贪心

2021-02-06

2 550

Train Hard, Win Easy 来自专栏

题意: 题意有点难懂,这里解释一下.题意:给你n组数,每组都可以和其他组配对,然后你只能选这个组的a类,那个组的b类/这个组的b类,那个组的a类.然后要求总和最小,当然还给了m组不能配对的点,然后输出每组配对所获得的值. 思路: 暴力的思路十分简单,就是一一配对,然后一一比较即可.但是这样做的时间复...

贪心

2021-02-01

1 779

codeJan与旅行来自专栏

简单贪心题.但是我才知道lower_bound找不到就算返回n...第一次学到= - =好累好困,还有一个挺难的dp要学 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5...

贪心

2021-01-12

1 733

模拟战役来自专栏

前言: 晚上有点困了,本来是看吉吉是第一个的,然后其实是司机,然后打错一些东西...不过也没很久就搞好了..说明还行. 思路: 本题思路十分简单,就算搜每个连通块大小,然后判断下吉吉的和司机的连通块数量就好了. 代码: 代码有点丑,将就一下~ #include <bits/stdc++.h&g...

并查集贪心

2021-01-12

4 704

网络优化

贪心还是得保证正确再写,不难就挺难受的,这个题的贪心解法讲出来挺容易的,就是按r排序从小到大排,然后分配区间[L,R].这里也从小到大分配,能分配就分配,这样就必定是最优解了.因为我从小到大分配的R,这样的R去分配L,是不影响后面的.但是这样做的复杂度是O(N^2)的.显然太高了.我们不妨用优先队列...

贪心优先队列

2020-10-02

5 673

Stressful Training 来自专栏

挺套路的一个题目.问最小的问题,一般就二分一下,且这个单调性真的显然.然后我们注意k只有2e5,完全可以贪心检测,1min..1min的检测嘛,贪心的策略就是ck时间,把我所坚持时间小的优先充电.貌似就么了..代码如下: #include <bits/stdc++.h> using na...

二分贪心

2020-09-29

4 630