noi2010专题

LUOGU P2048 [NOI2010] 超级钢琴（贪心+堆）

原题链接：[NOI2010] 超级钢琴题目大意：给出一个长度为 n n n 的数组，且 a i a_{i} ai 可正可负，再给出三个数字 k , L , R k,L,R k,L,R 。定义每个子数组的价值为其所有元素的和，你需要找到 k k k 个连续的子数组（可重叠但不可重复），且满足长度在 [ L , R ] [L,R] [L,R] 内，问你最后这 k k

NOI2010...BZOJ2006 超级钢琴贪心

Description 小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且

bzoj2005 [NOI2010]能量采集莫比乌斯反演

题目链接：传送门考虑点 ( x , y ) (x,y) (x,y)对答案的贡献：设 g c d ( x , y ) = k gcd(x,y)=k gcd(x,y)=k， x = a k , y = b k . x=ak,y=bk. x=ak,y=bk. 若有 x ′ , y ′ x',y' x′,y′满足 ( x ′ , y ′ ) (x',y') (

BZOJ 2005 [Noi2010]能量采集 (容斥)

[Noi2010]能量采集 Time Limit: 10 Sec Memory Limit: 552 MB Submit: 2324 Solved: 1387 [Submit][Status][Discuss] Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能

洛谷P1447 - [NOI2010]能量采集

Portal Description 给出\(n,m(n,m\leq10^5)，\)计算\[ \sum_{i=1}^n \sum_{j=1}^m (2gcd(i,j)-1)\] Solution 简单起见我们来钦定\(n\leq m\)，然后计算\(\sum_{i=1}^n \sum_{j=1}^m gcd(i,j)\)。\[ans = \sum_{i=1}^n \sum_{j=1}^m gcd

NOI2010 海拔

正解是平面图转对偶图然后跑最短路先是题目的读入没有说明白导致wa 后来用最大流最小割TLE后两个点转SPFA跑最短路依然TLE后两个点 SPFA加上优先队列优化才A掉貌似更多人写heap优化的dijkstra.... 注意最短路建图由于每条边是双向的所以一一对应到最短路的边权里去自己画下图就能发现怎么对应 80分的

NOI2010 能量采集

仅仅求GCD居然就有 80分然后枚举gcd 容斥下就可以做了 #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;long long f[100000+10];int main(){long long ans=0;int n,m;cin>

BZOJ2005 [Noi2010]能量采集——莫比乌斯反演

Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。由

[BZOJ2006] [NOI2010]超级钢琴

[BZOJ2006] [NOI2010]超级钢琴题目大意给定一个序列,要求找到连续的序列满足长度在 [L,R] [L,R]范围内,询问前 k k大的满足条件的序列的和 n,k≤5∗105n,k\le 5*10^5 题解设一个三元组 (R,L1,L2) (R,L1,L2):表示左端点在 [L1,L2] [L1,L2]内,右端点为R的区间最大值 =sum[R]−min{sum[i]},

【NOI2010】bzoj2005 能量采集

Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的

【随机化贪心】【动态规划】【NOI2010】成长快乐

【问题描述】Nemo是一条无忧无虑的小鱼，它的初始体重为w0。可爱的Nemo希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo最喜爱的食物是海里的小虾。已知Nemo对食物的情况了解如下：大海里共有n只小虾，从1到n编号，其中编号为i的小虾的重量为wi。将大海看作一个X-Y坐标系，在0时刻编号为i的小虾所在的位置为(xi, yi)。小虾在大海中作匀速直线运动，其中编号为i的小虾的速度向量为