本文涉及知识点升序 单调声海 | Sea of Voices题目背景「真是如梦似幻呢。」“怎么”「我看见你从开始到现在的一切记忆看见你从一次次或欢喜或失落中走来。那些场景在我眼前浮现像梦却又那么模糊——我只听见那些声音只感到那片声音的海洋将我环围… 你听得见吗」“当然。毕竟它们是我的记忆啊。”「或许一次生命便是一场发声的历程吧。我们诞生时的啼哭便在向世界发出宣告降临的声音在一次次挑战的过程中我们向一切阻碍我们的事物唱出不屈的战歌在日常的点滴中我们向所珍视之人倾诉内心深处的话语… 这样的声音这样的感情是不是就是我们所生存世界的本质呢」“或许就是这样吧。纵使一路走来我们看见了无尽的景色但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。”「是啊… 但愿在这片声音的海洋里你不会迷失你的方向。我期许着听见更多关于你的声音。怀揣着这种信念向前走下去吧。」“你也一样。”We’ll see creation come undone我们会见证自己存在的印记被世界拂去These bones that bound us will be gone而那些既有的束缚将不再留存We’ll stir our spirits till we’re one我们会洗涤自己的灵魂直至合为一体Then soft as shadows we’ll become然后成为掠影散失在虚无之中题目描述“但是… 曾有一些人在我的生命里留下了重要的声音我却无法回忆起了…”「为什么呢」“不妨让我们把问题变得形式化一点。我想回忆起的声音有n nn个它们的共鸣度——非负整数a i a_iai是单调不降的。最初它们互不干涉但随着时间的推移多个相邻的声音会交织在一起形成新的声音——也就是说对于任意的1 ≤ l ≤ r ≤ n 1\le l\le r\le n1≤l≤r≤n第l ll一直到第r rr个声音会交织在一起形成新的声音而这个声音的共鸣度便是这些声音共鸣度的总和。”「也就是说例如n 3 n3n3a [ 1 , 2 , 4 ] a[1,2,4]a[1,2,4]那么最终3 × ( 3 1 ) 2 6 \dfrac{3\times(31)}2623×(31)6个声音的共鸣度分别是1 , 2 , 4 , 3 , 6 , 7 1,2,4,3,6,71,2,4,3,6,7」“没错。现在我把最终所有声音的共鸣度无序地告诉你你能帮我还原最开始n nn个声音的共鸣度吗”「乐意之至。」简要题意a aa为长度为n nn的非负整数序列满足∀ 1 i ≤ n , a i − 1 ≤ a i \forall 1i\le n,a_{i-1}\le a_i∀1i≤n,ai−1≤ai。现无序地给出可重集S { ∑ k l r a k ∣ 1 ≤ l ≤ r ≤ n } S\left\{\sum_{kl}^r a_k|1\le l\le r\le n\right\}S{∑klrak∣1≤l≤r≤n}试还原a aa。输入格式第一行一个正整数n nn代表最初声音的个数。接下来一行n × ( n 1 ) 2 \dfrac{n\times(n1)}22n×(n1)个非负整数表示现在所有声音的共鸣度输入无序。输出格式一行n nn个非负整数表示最初n nn个声音共鸣度a i a_iai。样例 #1样例输入 #13 1 2 3 4 6 7样例输出 #11 2 4样例 #2样例输入 #25 1 3 4 7 8 9 10 11 15 17 18 19 24 27 28样例输出 #21 3 7 8 9提示对于全部数据有1 ≤ n ≤ 2000 1\le n\le 20001≤n≤20000 ≤ a i ≤ 10 5 0\le a_i\le 10^50≤ai≤105。Subtask 15 pts保证n 2 n2n2。Subtask 215 pts保证n 3 n3n3。Subtask 330 pts保证n ≤ 100 n\le 100n≤100。Subtask 450 pts无特殊限制。声海 | Sea of Voices 超时注意a是升序。多键有序集合s 记录所有输入。a[0] s的最小值从s中删除a[0]。a[1]s的最小值从s中删除a[0…1]和a[1]。此时s中至少包括a[2…]中的一个元素。a[i] s的最小值从s中删除a[i]、a[i-1…i]…a[0…i]。此时s中至少包括a[i1…]中的一个元素。时间复杂度O(nnlognn) 稍稍超时。性能优化c升序。vErase[i] 记录i需要被删除的次数。一M max(a)如果ci M忽略。二for(i : c ) 如果vErase[i] 0vErase[i] --。三如果i已经枚举故只需要删除 a[j…i],j∈ \in∈[0.i-1]不需要也不能删除a[i…i]。代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}classSolution{public:vectorintAns(vectorintc){constintM100000;sort(c.begin(),c.end());vectorintans;vectorintpreSum{0};vectorintvErase(M1);for(constautoi:c){if(iM){break;}if(vErase[i]0){vErase[i]--;continue;}ans.emplace_back(i);preSum.emplace_back(ipreSum.back());for(intj0;j2preSum.size();j){constautosumpreSum.back()-preSum[j];if(sumM){vErase[sum];}}}returnans;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintn;cinn;autocReadint(n*(n1)/2);autoresSolution().Ans(c);#ifdef_DEBUG//printf(K%d, K);//Out(b, b);Out(c,c);#endif// DEBUGfor(constautoi:res){printf(%d ,i);}return0;}单元测试vectorintc;TEST_METHOD(TestMethod11){c{1,2,3,4,6,7};Solution slu;autoresslu.Ans(c);AssertEx({1,2,4},res);}TEST_METHOD(TestMethod12){c{1,3,4,7,8,9,10,11,15,17,18,19,24,27,28};Solution slu;autoresslu.Ans(c);AssertEx({1,3,7,8,9},res);}TEST_METHOD(TestMethod13){c{0,0,0,0,0,0};Solution slu;autoresslu.Ans(c);AssertEx({0,0,0},res);}TEST_METHOD(TestMethod14){c{1,3,4,7,6,2};Solution slu;autoresslu.Ans(c);AssertEx({1,2,4},res);}TEST_METHOD(TestMethod15){c{0,1,1,3,3,2};Solution slu;autoresslu.Ans(c);AssertEx({0,1,2},res);}TEST_METHOD(TestMethod16){c{1,2,3,1,2,1};Solution slu;autoresslu.Ans(c);AssertEx({1,1,1},res);}扩展阅读我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。 
长河君 · 2026/10/9 1:24:00 · 阅读 1.2k 【排序】P8148 声海 | Sea of Voices|普及+
本文涉及知识点升序 单调声海 | Sea of Voices题目背景「真是如梦似幻呢。」“怎么”「我看见你从开始到现在的一切记忆看见你从一次次或欢喜或失落中走来。那些场景在我眼前浮现像梦却又那么模糊——我只听见那些声音只感到那片声音的海洋将我环围… 你听得见吗」“当然。毕竟它们是我的记忆啊。”「或许一次生命便是一场发声的历程吧。我们诞生时的啼哭便在向世界发出宣告降临的声音在一次次挑战的过程中我们向一切阻碍我们的事物唱出不屈的战歌在日常的点滴中我们向所珍视之人倾诉内心深处的话语… 这样的声音这样的感情是不是就是我们所生存世界的本质呢」“或许就是这样吧。纵使一路走来我们看见了无尽的景色但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。”「是啊… 但愿在这片声音的海洋里你不会迷失你的方向。我期许着听见更多关于你的声音。怀揣着这种信念向前走下去吧。」“你也一样。”We’ll see creation come undone我们会见证自己存在的印记被世界拂去These bones that bound us will be gone而那些既有的束缚将不再留存We’ll stir our spirits till we’re one我们会洗涤自己的灵魂直至合为一体Then soft as shadows we’ll become然后成为掠影散失在虚无之中题目描述“但是… 曾有一些人在我的生命里留下了重要的声音我却无法回忆起了…”「为什么呢」“不妨让我们把问题变得形式化一点。我想回忆起的声音有n nn个它们的共鸣度——非负整数a i a_iai是单调不降的。最初它们互不干涉但随着时间的推移多个相邻的声音会交织在一起形成新的声音——也就是说对于任意的1 ≤ l ≤ r ≤ n 1\le l\le r\le n1≤l≤r≤n第l ll一直到第r rr个声音会交织在一起形成新的声音而这个声音的共鸣度便是这些声音共鸣度的总和。”「也就是说例如n 3 n3n3a [ 1 , 2 , 4 ] a[1,2,4]a[1,2,4]那么最终3 × ( 3 1 ) 2 6 \dfrac{3\times(31)}2623×(31)6个声音的共鸣度分别是1 , 2 , 4 , 3 , 6 , 7 1,2,4,3,6,71,2,4,3,6,7」“没错。现在我把最终所有声音的共鸣度无序地告诉你你能帮我还原最开始n nn个声音的共鸣度吗”「乐意之至。」简要题意a aa为长度为n nn的非负整数序列满足∀ 1 i ≤ n , a i − 1 ≤ a i \forall 1i\le n,a_{i-1}\le a_i∀1i≤n,ai−1≤ai。现无序地给出可重集S { ∑ k l r a k ∣ 1 ≤ l ≤ r ≤ n } S\left\{\sum_{kl}^r a_k|1\le l\le r\le n\right\}S{∑klrak∣1≤l≤r≤n}试还原a aa。输入格式第一行一个正整数n nn代表最初声音的个数。接下来一行n × ( n 1 ) 2 \dfrac{n\times(n1)}22n×(n1)个非负整数表示现在所有声音的共鸣度输入无序。输出格式一行n nn个非负整数表示最初n nn个声音共鸣度a i a_iai。样例 #1样例输入 #13 1 2 3 4 6 7样例输出 #11 2 4样例 #2样例输入 #25 1 3 4 7 8 9 10 11 15 17 18 19 24 27 28样例输出 #21 3 7 8 9提示对于全部数据有1 ≤ n ≤ 2000 1\le n\le 20001≤n≤20000 ≤ a i ≤ 10 5 0\le a_i\le 10^50≤ai≤105。Subtask 15 pts保证n 2 n2n2。Subtask 215 pts保证n 3 n3n3。Subtask 330 pts保证n ≤ 100 n\le 100n≤100。Subtask 450 pts无特殊限制。声海 | Sea of Voices 超时注意a是升序。多键有序集合s 记录所有输入。a[0] s的最小值从s中删除a[0]。a[1]s的最小值从s中删除a[0…1]和a[1]。此时s中至少包括a[2…]中的一个元素。a[i] s的最小值从s中删除a[i]、a[i-1…i]…a[0…i]。此时s中至少包括a[i1…]中的一个元素。时间复杂度O(nnlognn) 稍稍超时。性能优化c升序。vErase[i] 记录i需要被删除的次数。一M max(a)如果ci M忽略。二for(i : c ) 如果vErase[i] 0vErase[i] --。三如果i已经枚举故只需要删除 a[j…i],j∈ \in∈[0.i-1]不需要也不能删除a[i…i]。代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}classSolution{public:vectorintAns(vectorintc){constintM100000;sort(c.begin(),c.end());vectorintans;vectorintpreSum{0};vectorintvErase(M1);for(constautoi:c){if(iM){break;}if(vErase[i]0){vErase[i]--;continue;}ans.emplace_back(i);preSum.emplace_back(ipreSum.back());for(intj0;j2preSum.size();j){constautosumpreSum.back()-preSum[j];if(sumM){vErase[sum];}}}returnans;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintn;cinn;autocReadint(n*(n1)/2);autoresSolution().Ans(c);#ifdef_DEBUG//printf(K%d, K);//Out(b, b);Out(c,c);#endif// DEBUGfor(constautoi:res){printf(%d ,i);}return0;}单元测试vectorintc;TEST_METHOD(TestMethod11){c{1,2,3,4,6,7};Solution slu;autoresslu.Ans(c);AssertEx({1,2,4},res);}TEST_METHOD(TestMethod12){c{1,3,4,7,8,9,10,11,15,17,18,19,24,27,28};Solution slu;autoresslu.Ans(c);AssertEx({1,3,7,8,9},res);}TEST_METHOD(TestMethod13){c{0,0,0,0,0,0};Solution slu;autoresslu.Ans(c);AssertEx({0,0,0},res);}TEST_METHOD(TestMethod14){c{1,3,4,7,6,2};Solution slu;autoresslu.Ans(c);AssertEx({1,2,4},res);}TEST_METHOD(TestMethod15){c{0,1,1,3,3,2};Solution slu;autoresslu.Ans(c);AssertEx({0,1,2},res);}TEST_METHOD(TestMethod16){c{1,2,3,1,2,1};Solution slu;autoresslu.Ans(c);AssertEx({1,1,1},res);}扩展阅读我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。