sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

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

程序自动分析来自专栏

离散化+并查集关系的化就是并查集处理，但是数据规模很大，下标到了1e9，所以开不下那么大的并查集数组，那么怎么办，离散化去搞。我们不需要知道每个数具体多大，只需要知道相对大小，找到这个数就行了。别用set，常数很大，就用快排+去重。 #pragma GCC target("avx,sse2,sse...

2020-06-08

1 762

背包来自专栏

优先队列+二分题目需要找到中位数最大，那么我们直接按照价值升序排序，再把体重升序排序。从头把m对半分开，求前m最小和后m最小，如果是奇数最终加上当前这位的体积比v小于等于，直接这一位的价值就是答案。如果是偶数，这个会复杂一点，因为你无法保证某一次价值大的体重小，但是可以发现，我们是求中间两个取平均...

2020-06-08

3 999

食物链来自专栏

并查集测谎话，并查集的基础作用，我们开个3 * n的数组，每n个元素看成是同类，其余跨种族。我们把输入的x和y进行找种族，如果存在冲突+1即可，雨巨也教的比较明白了，白嫖课大家可以去康康吖。安利一波江大佬的带权并查集不用开3 * n的空间，保存n的大小，对3取模。传送门 #pragma G...

2020-06-08

3 703

Operating System 来自专栏

堆/优先队列这个题目写起来不难，题目读起来是真的困难，出题人根本没把题目意思交代清楚……观摩大佬AC代码之后，看的有点懵，反正给出的数，需要求一下下一次出现的位置，可以用2个数组，也可以用umap去离散记录。我就不展开了。其余的就是贪心的思路了，按下一次出现优先降序排序，最大的那个最先出队，如果出...

2020-06-07

4 1131

Music Notes 来自专栏

前缀和+STL 前缀和应该挺简单不用我说吧，C++中一个STL叫upper_bound()查找在一个左闭右开的区间中第一个大于x的迭代器位置，记住不带等号！！带等号的是lower_bound()！！！迭代器减掉起始下标就是距离了。 #pragma GCC target("avx,sse2,sse3...

2020-06-07

3 767

Monthly Expense 来自专栏

二分题目意思，给出最大k个球，问每个球重量一样最小可能需要多大才可以把这n个东西都放进去。很容易发现的二分思路，check函数也挺好写的，直接看代码应该挺容易理解，基础二分题。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC ...

2020-06-07

1 587

Monthly Expense 来自专栏

二分挺容易发现的二分思路，单调性比较明显，而且check函数直接把大于等于答案的累加进去，求解判断下就可以了。注意特判个k=1，就行了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofa...

2020-06-07

0 530

Chocolate Eating 来自专栏

二分首先假设已经求解到的ans代表合理的最大幸福的，我们显然希望找到一个吃巧克力的方式让他比当前ans更大，否则只能更小。符合二分性质。而且二分的check函数设计直接把吃过的sum每天减半如果不够了再吃一个新的巧克力，看最后会不会超过n即可最后调用一次check求道合理的最大幸福度的安排方法。...

2020-06-07

5 797

[SCOI2010]传送带来自专栏

三分雨巨点名的三分题……本菜鸡还是不太懂，观摩其他大佬的代码终于有点理解。我们先三分出从A点到AB中的某个点X，作为出发点，然后，再三分出从X到CD的某个点Y，再从Y直接到D，这样，我们就可以求出最小的值了。路径的话，存在4条路，分别代表走不走传送带。不走AB带就直接走到B，不走CD带就直接从x走...

2020-06-07

4 1127

聪明的质监员来自专栏

二分+前缀和求解最小值，观察题目给出的判断条件，W随着变大时，区间中符合要求的会减少，同时所有，所以也随着变小，求得Y也是递减，可以得知W和Y是满足二分的关系。在求解每一个时，运用到前缀和的思想O(1)实现。总的时间复杂度 Code #pragma GCC target("avx,sse2,s...

2020-06-07

1 620