在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #背包#

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

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

2023-09-20

2 441

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

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

C++ 二分查找前缀和

2023-09-06

2 346

题解 | #[NOIP2012]借教室#

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

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

2023-09-05

2 385

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

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

C++ 前缀和二分查找

2023-09-04

1 303

牛牛的木板

链接：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 389

加减

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

C++ 前缀和枚举

2023-08-17

0 1789

线代高手

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

C++ 前缀和

2023-08-16

0 435

仓库选址

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

C++ 前缀和

2023-08-16

0 656

「土」秘法地震

链接：https://ac.nowcoder.com/acm/contest/20960/1025 来源：牛客网题目描述帕秋莉掌握了一种土属性魔法这种魔法可以在一片k×k大小的一个正方形区域内产生地震但是如果某片即...

C++ 前缀和

2023-08-15

0 348

Xorto

链接：https://ac.nowcoder.com/acm/contest/20960/1023 来源：牛客网题目描述给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。输入描述: 第一行一个数n表示数组长度；第二...

C++ 前缀和

2023-08-14

0 441