• 2024-09-06P2048 [NOI2010] 超级钢琴
    P2048[NOI2010]超级钢琴题目链接其实这道题在我刚学oi两个月(2023.3)就见过了当时是作为st表的一个例题出现的,我学st表就已经学得迷迷糊糊的了,更别说这题了哈哈所以这是第二次见到他,必须写了(这一次他是作为NOIP模拟赛的一个部分分做法出现的)思路不错的限制:每
  • 2024-08-18P2048 [NOI2010] 超级钢琴
    题意在一个数组中选择\(k\)个长度为\([l,r]\)的序列,对每个序列求和,使每个序列的和的和最大。思路首先,我们可以将序列之和转化为前缀和,如果固定左端点\(l\),那么我们只需要在\([l+len_l,l+len_r]\)中寻找最大的右端点,减去\(sum[l-1]\)就是在长度为\([len_l,le
  • 2024-08-05P1447 [NOI2010] 能量采集
    题目传送容斥思想的一道好题。题目容易转化为:\[2\times\sum_{i=1}^n\sum_{j=1}^n(\gcd(i,j))\-nm.\]直接求和不好求,不妨转换为枚举\(d=\gcd(i,j)\)。那么\(i,j\)应该均为\(d\)的倍数。记\(f(i)=\left\lfloor\frac{n}{i}\right\rfloor\cdot\left\lfloor
  • 2024-05-25【NOI2010】能量采集 题解
    【NOI2010】能量采集题解谨纪念我的第一道手推出来的莫反题。题目大意:已知\(n\),\(m\),求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)\)。首先变形一手:\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)=2\sum\limits_{i=1}^n\sum\limits_{j=
  • 2024-03-20[NOI2010][洛谷P2048]超级钢琴
    一道很不错也很难的ST表Debug了好久之后发现撞变量了
  • 2024-01-222023NOIP A层联测9 风信子+P2048 【NOI2010】 超级钢琴 2023
    P2048【NOI2010】超级钢琴2023NOIPA层联测9风信子一年OI一场空,一道原题见祖宗……Ps:超级钢琴是风信子的前置题。超级钢琴题意在一段序列上,选择长度为\(x\)的区间且\(x\in[L,R]\),求选择\(k\)个区间求和的最大值。思路来自洛谷第一篇Nekroz的题解。将区间和
  • 2023-10-27[NOI2010] 超级钢琴 题解
    [NOI2010]超级钢琴题解说点闲话原本不想写这个题解的但是看到我的代码居然长度为2048B->刚好2KiB,然后还跟题号相同QAQ题目翻译给你一段序列,求出其中从第\(1\)大到第\(k\)大的子区间的和。思路解析首先可以想到一个简单的暴力,对于每一个区间开头\(i\),和区间结尾\(j\),都求
  • 2023-10-08解题报告P2048 [NOI2010] 超级钢琴
    P2048[NOI2010]超级钢琴题目链接RMQ好题,但是不知道为啥hzoi放到了lca的题单这道题思路想了一半然后卡了,不知道怎么处理重复贡献的问题。然后he了眼题解,茅塞顿开。可以再次将最优分成两个,再次计算。全程维护音符的前缀和,和区间最大值。结构体内存最大值,左端点,右端点范围,以
  • 2023-05-17【BZOJ2007】【NOI2010】海拔(对偶图,最短路)
    DescriptionYT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路(简称道路),每条双向道路连接主干道上两个相邻的交叉路口。下图为
  • 2023-03-24bzoj 2006 [NOI2010] 超级钢琴 线段树求区间极值+优先队列
    挺神奇的一道题,唯一想不通的是为什么放在主席树的题单里..首先暴力找出所有的合法区间显然是不可能的。考虑怎么贪心,假如固定每个L作为左端点,那么合法的区间就是[L+l-1,L
  • 2023-01-31关于NOI2010“超级钢琴”的反思
    [NOI2010]超级钢琴题目描述小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏
  • 2023-01-07[RMQ记录] P2048 [NOI2010] 超级钢琴
    题目如果枚举所有的情况肯定是不行的。不过可以发现一些对答案完全没有影响的答案也被枚举,十分浪费时间,所以下面介绍一种很好的思路。首先,考虑优化暴力(暴力指用堆维护每
  • 2022-11-02洛谷 P1447 [NOI2010] 能量采集
    题目描述https://www.luogu.com.cn/problem/P1447栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能