在刷题的单身狗很开心

分类

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2) 题解(176)

/ 注册

全部文章（共12篇）

题解 | #背包#

做这道题的时候一开始想到了对顶堆但发现如果根据输入逐步使用对顶堆的话，不好实现最优的选择。看了题解才知道这不是一道对顶堆的题目，可以使用对物品的价值进行排序，然后某个物品能否作为中位数可以通过向左取(m-1)/2个物品，向右取(m-1)/2个物品。取左右物品的最小重量总和然后加上中位数可以判...

C++ 堆(优先队列) 前缀和二分 C++ 贪心二分优先队列前缀和

2023-09-20

3 441

自动计算机

题目链接：E-自动计算机_牛客小白月赛78 (nowcoder.com) 这是一道思维题。要想将结果变成0那么就需要经过x轮y次操作。首先从轮来看每次加的都是一样的，如果遍历轮的次数达到了n次，那么n+1次一定会发生循环（因为取余的存在）。所以我们就确定的应该遍历的最大的轮数。如果超过...

C++ 前缀和思维

2023-09-17

2 465

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

从题中描述可以看出w和检验结果之间有一定关系：w越大检验结果越小，w越小检验结果越大。从而得到w的结果具有一个单调的性质。然后根据这个性质可以考虑二分w的做法。在二分的过程中，如果Y>S那么w就得增大，如果Y<S那么w就得减小，如果Y==S那么直接退出就可以了。但我们最终的答案是...

C++ 二分查找前缀和

2023-09-06

2 350

题解 | #[NOIP2012]借教室#

订单的编号具有单调性，也就是说可以往二分答案的方向去思考。已知订单的编号，也就是说在此订单及其之前的订单都能满足。那么如何快速验证订单是否满足就是要解决的问题。按题中描述以某一天为下标每个订单都有连续几天的租借数量，对于连续区间的加减问题可以联想到差分与前缀和的解法可以将原来教室数量的列表...

C++ 二分查找前缀和差分

2023-09-05

2 376

题解 | #[USACO 2009 Dec S]Music Notes#

//使用前缀和记录在什么时候音符开始演奏，然后在通过二分查找值的范围即可。 #include <bits/stdc++.h> using namespace std; const int maxn = 50000+...

C++ 前缀和二分查找

2023-09-04

1 308

小分分

题目链接：B-小分分_2023河南萌新联赛第（八）场：南阳理工学院 (nowcoder.com) 本题要求所有好点的覆盖情况之和，已知好点的范围是1~5e5，从题上而言直接开一个5e5+1的数组来记录每一次之后的情况，然后对每一个数的情况进行相加即可。但由于这样做就将复杂度提升到了O(...

C++ 前缀和

2023-08-31

1 334

牛牛的木板

链接：https://ac.nowcoder.com/acm/contest/20960/1029 来源：牛客网时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 ...

C++ 前缀和枚举

2023-08-17

0 394

加减

链接：https://ac.nowcoder.com/acm/contest/20960/1028 来源：牛客网题目描述小红拿到了一个长度为 n n\n 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。小红最多能进行 k...

C++ 前缀和枚举

2023-08-17

0 1949

线代高手

链接：https://ac.nowcoder.com/acm/contest/63602/J 来源：牛客网题目描述小H是大家公认的线代高手，他最近遇到了一个...

C++ 前缀和

2023-08-16

0 442

仓库选址

链接：https://ac.nowcoder.com/acm/contest/20960/1026 来源：牛客网题目描述牛能在某小城有了固定的需求，为了节省送货的费用，他决定在小城里建一个仓库，但是他不知道选在哪里，可以使得花费最小。 ...

C++ 前缀和

2023-08-16

0 654