在刷题的单身狗很开心 - 个人主页动态 - 牛客网

发布(192) 评论刷题收藏

2023-09-11 21:21

中原工学院 Java

题解 | #[NOIP2016]蚯蚓#

使用优先队列会超时，因为优先队列的内部实现是小根堆或大根堆。并不是O(N)的时间复杂度。   在本题当中可以使用三个队列，一个原始序列排序好的队列，一个切完后左边蚯蚓的队列，一个切完后右边蚯蚓的队列。这样只需要每次比较队首的蚯蚓长度就可以得到刽子手需要去砍的蚯蚓。   然后本题的输出比较麻烦，需要输出在砍的某个蚯蚓之前的长度和最终所有蚯蚓的长度，本题解采用假设当前蚯蚓从一开始就存在，然后在最终加上时间即可。   那么就需要在出对的时候将时间增长的加上，在如果的时候再减去。   #include <bits/stdc++.h> typedef long ...

0 点赞评论收藏

分享

2023-09-11 13:46

中原工学院 Java

题解|#Antiamuny wants to leaern binary search again#

将题目中的二分写法做一个小小的改变即可，注意：一定要将左边移动，不然会损失一些次数。   #include <bits/stdc++.h> using namespace std; int f(int l, int r, int cnt) {     int n = 0, mid;     while (l<=r) {  &nbs...

0 点赞评论收藏

分享

2023-09-11 10:10

中原工学院 Java

题解|#A-Mountain sequence#

一道组合数学的问题，一开始想的是改变最大值的位置然后分类计算，但那样太麻烦。不从最大值下手，除最大值以外的每一个数都有道最大值左边和右边两种选择。而如果有相同的可以将其看成一个一起，首先将他们插空分隔就可以得到N+1中左右分配的方案。然后全部相乘即可。   #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1e5+10; const int p&...

0 点赞评论收藏

分享

2023-09-11 08:52

中原工学院 Java

题解 | #好串#

和括号匹配一样，左括号压栈右括号与栈顶的左括号匹配出栈，如果中间无法与右括号匹配或最后A有剩余，即为Bad。   #include <bits/stdc++.h> using namespace std; int main() {     stack<int> st;     string s;     cin>>s;     fo...

0 点赞评论收藏

分享

2023-09-10 21:46

中原工学院 Java

题解 | #栈和排序#

每次都选取尽可能大的即可，一个简答的贪心。所以需要记录后面的最大值，来判断当前是不是有可能的最大的那个数，从而判断值不值得弹出。   #include <bits/stdc++.h> using namespace std; int a[1000001]; int b[1000001]; int main() {     int n, k, j=0, flag = true;    &...

0 点赞评论收藏

分享

2023-09-10 21:01

中原工学院 Java

题解 | #Rails#

就是查看出队序列合不合理罢了，只要和数组中的数一致按需出队即可。   #include <bits/stdc++.h> using namespace std; const int maxn = 100000+10; int a[maxn]; int n; bool is_end() {     cin>>n;     return n==0? false&nbs...

0 点赞评论收藏

分享

2023-09-08 23:10

中原工学院 Java

题解 | #[SHOI2017]期末考试#

//思维还是不够灵活，以前的二分答案基本上都是以题目中要求的入手的。二本题题目所要求的是求总的不愉快度之和最小。 //如果以总和的不愉快度入手的话难以验证是否满足，动不动就从问题出发了。 //看大佬的题解才知道，这道理可以利用的一个固定点在于课程的最晚公布时间，如果最晚公布时间太早可能会因为要调整策略而导致总愉快度变小，如果太晚自然也一样。 //所以在这中间有一个最适合的值。至于他一定是一个凹曲线的证明那当然不去证明，比如咱不是数学的。看着像就可以去尝试。 //因为学生的不愉快仅仅取决于最晚的那个科目的公布时间，那么其实我们已知最晚公布时间，根据最晚公布时间就得到哪些没有达到最晚公布时间的就是...

0 点赞评论收藏

分享

2023-09-08 16:01

已编辑

中原工学院 Java

题解 | #神奇盘子#

题目中情况要么从边界传送，要么直接直接过去。那么就是要求出从边界传送的最短路，由于边界传送的特点，在圆周上是一个凹的函数图形，所以使用三分去求解即可。   那么问题就到了如何定三分的左右边界呢？在园的方程里面有一个参数方程。在里面可以从0,2*PI的范围内将圆表示出来。所以通过参数方程即可求解。   #include <bits/stdc++.h> using namespace std; struct Node{     double x;     d...

0 点赞评论收藏

分享

2023-09-08 15:13

中原工学院 Java

题解 | #Greedy Gift Takers#

首先可以看出是按照奶牛的编号进行二分去寻找第一个没有礼物的奶牛。但如何验证某个编号的奶牛前面有死循环存在呢。   因为是从后面插空的所以会因为后面牛数量的改变而改变。但可以转化到插第几个位置，如果位置2上有两个及其以上的牛的目标都是它，那么就会造成死循环。同样如果3这个位置上有三个及其以上的牛目标都是他，也会造成死循环。   #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int N, c[maxn]...

0 点赞评论收藏

分享

2023-09-07 21:50

中原工学院 Java

题解 | #小咪买东西#

可以采用二分总价值的方式，已知总价值为x了，那么需要对分数进行价值和/花费和>=0进行变形得：总（价值-x*花费）>=0.势必要贪心的选取价值-x*花费最大的前k个东西。那么就可以得到是否满足。之后二分就行。   值得注意的是本题的答案是在实数范围内的。所以采用足够的循环来界定要二分多少次，一防止出现死循环的现象。    #include <bits/stdc++.h> typedef long long ll; using namespace std; int n, k; const&nb...

0 点赞评论收藏

分享

2023-09-07 20:44

中原工学院 Java

题解 | #[SCOI2010]传送带#

对CD来说进早了可能因为路远，时间增大，进晚了因为没有省力所以时间增大，故区间是一个凹状的，可以使用三分去解决。对于何时进入CD也是一样的。故嵌套三分的做法。   但因为本题针对实数的运算，所以要求精度。至于为什么要在计算距离时加上精度，我想是因为在求距离过程中小数位会有所丢失的原因吧。所以需要加上（当然这只是我的想法）。   按雨巨的另一种做法，直接固定循环次数也可以。   #include <bits/stdc++.h> using namespace std; struct Node{     d...

0 点赞评论收藏

分享

2023-09-06 21:33

中原工学院 Java

题解 | #[HEOI2014]南园满地堆轻絮#

二分答案，验证方式为将当前的音符值降到尽量小，以便后来的付出小的代价就可以维持递增。   比较坑的是取余运算，在这里面取余运算一定要加括号，因为取余运算和乘除运算同级。不加括号将不符合取余运算的规则。   #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 5000000+10; ll a[maxn]; ll b[maxn]; ll n,...

0 点赞评论收藏

分享

2023-09-06 19:47

中原工学院 Java

题解 | #位数差#

做这题的时候因为没有看清题目走了好多弯路，题目中要去i<j，所以不会出现抽取相同下标的数。也是因为这个要求所以不能对数组直接进行排序，会将数组顺序打乱导致错误的。   但要求数位差如果有序的话最好的办法是求得大于等于10-a,100-a,1000-a的个数，然后相加。但本题不能直接排序。   然后可以想到使用整体二分递归的方式，将右半边排序，从遍历左半边去计算右半边有多少符合的数。这样由于递归栈的性质，从小的区间开始计算所以就算排序也不会影响后续的结果。因为左半边的顺序对结果没影响。   #include <bits/stdc++.h> typedef l...

0 点赞评论收藏

分享

2023-09-06 16:32

中原工学院 Java

题解 | #[NOIP2011]聪明的质监员#

从题中描述可以看出w和检验结果之间有一定关系：w越大检验结果越小，w越小检验结果越大。从而得到w的结果具有一个单调的性质。然后根据这个性质可以考虑二分w的做法。   在二分的过程中，如果Y>S那么w就得增大，如果Y<S那么w就得减小，如果Y==S那么直接退出就可以了。但我们最终的答案是需要取|S-Y|的最小值。   在计算Y的过程中也要注意不能直接暴力模拟，由于w的限制无法在一开始就对价格进行前缀和计算，但在计算Y的函数中w的值是确定的，在这时候可以使用前缀和将时间复杂度降低为：O(N)。   否则会超时。   #include <bits/stdc++.h>...

0 点赞评论收藏

分享

2023-09-06 08:44

中原工学院 Java

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

//二分答案的方式，将答案二分然后验证。 #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 2e5+10; ll N, K; int a[maxn]; bool yanz(int x) {     ll cnt = 0;  &n...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务