威风镰鼬

题解

/ 注册

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

题解 | #砝码Odw#

思路二分大法好！！非正解，T了很多发，终于把他卡过去了。看题解才知道可以将所有容器进制拆分直接塞，太妙了。但所有人都在贪心的时候，就让我来一提供一份二分代码吧。代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma...

二分贪心

2022-05-12

1 525

题解 | #Dropping tests#

思路 01分数规划模板题。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f //#define int long long using namespace std; const int N=1007; const int mod=1e9...

01分数规划二分

2021-11-16

1 379

题解 | #Desert King#

思路分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得∑（costi−ans∗leni）=0\sum （cost_i-ans*len_i）=0 ∑（costi−ans∗leni）=0 我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。（每个点都是与最...

最小生成树 MST 分数规划二分

2021-11-16

1 293

题解 | #数列分段 II#

思路二分代码 #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+7; inline void read(int &data){ int x=0,...

二分

2021-09-14

2 406

题解 | #愤怒的牛#

思路先将所有牛按位置排序。随后二分间隔的最大值。check的时候如果位置不够加了，那么需要的间隔就加。代码 #include<bits/stdc++.h> #define debug(x) cout<<"x="<<x<<endl...

二分

2021-09-14

1 495

题解 | #Best Cow Fences#

代码采用三分法，然后算出[1,n]中二次函数的最大值，再进行比较就可以了。思路 #include <bits/stdc++.h> #define debug(x) cout<<"x="<<x<<endl #define int ...

二分三分

2021-09-14

0 347

题解 | #Best Cow Fences#

思路求长度不小于L的平均值最大的子区间。可以用前缀和+二分的思想去做，复杂度O(nlogn)。对于每个数减去二分的平均值，并且算出前缀和。那么我们用一个数记录前i个数中总和最小的区间[0,k]，那么只需要判断前i个数最大区间[0,i]-[0,k]是否大于0即可。代码 #include<bi...

二分前缀和

2021-09-14

2 430

题解 | #Sumdiv#

代码读懂代码前需要掌握的芝士：唯一分解定理任意正整数都有且只有一种方式写出其素因子的乘积表达式。约数和方程对于已经分解的整数有A的所有因子之和为我们先记录素因子，然后利用约数和方程求解。这里有一个二分加速的过程，推导在代码里面。牛客上面有三道Sumdiv大家可以顺便A了。思路 #i...

数论二分

2021-08-04

3 497

题解 | #完全平方数#

思路在l和r里面一个一个数肯定会超时的，可以采用二分先把第一个大于l的平方数找出来，然后把第一个大于等于r的平方数找出来（等于的情况可以思考一下l==r的情况）提前打好表然后就能知道中间有多少平方数啦~ 代码 #include<bits/stdc++.h> using namespac...

二分 STL

2021-06-20

1 581

题解 | #华华给月月准备礼物#

思路二分答案，如果满足条件的就向右逼近。判断一个答案是否满足条件，只需要对所有木棍求能分的段数之和是否大于等于k就好了。代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int ma...

排序二分

2021-06-16

1 385