本文涉及知识点枚举「SWTR-6」GCDs LCMs题目描述小 A 有一个长度为n nn的序列a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an。他想从这些数中选出一些数b 1 , b 2 , ⋯ , b k b_1,b_2,\cdots,b_kb1,b2,⋯,bk满足对于所有i ( 1 ≤ i ≤ k ) i\ (1\leq i\leq k)i(1≤i≤k)b i b_ibi要么是序列b bb中的最大值要么存在一个位置j jj使得b j b i b_jb_ibjbi且b i b j gcd ( b i , b j ) l c m ( b i , b j ) b_ib_j\gcd(b_i,b_j)\mathrm{lcm}(b_i,b_j)bibjgcd(bi,bj)lcm(bi,bj)。如果你不知道gcd \gcdgcd和l c m \mathrm{lcm}lcm是什么可以点击最底部的「帮助/提示」部分的链接。小 A 想让选出的数之和尽量大。请求出这个最大值。输入格式第一行一个整数n nn表示序列的长度。第二行n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an。输出格式输出一行一个整数表示答案。样例 #1样例输入 #14 4 3 2 1样例输出 #15样例 #2样例输入 #210 6 7 18 4 17 10 9 1 3 8样例输出 #219样例 #3样例输入 #33 123456789 234567890 123456789样例输出 #3246913578提示「样例 1 说明」可以选择b { 2 , 3 } b\{2,3\}b{2,3}因为2 3 gcd ( 2 , 3 ) l c m ( 2 , 3 ) 23\gcd(2,3)\mathrm{lcm}(2,3)23gcd(2,3)lcm(2,3)。「数据范围与约定」本题采用捆绑测试。Subtask 15 pointsn ≤ 2 n\leq2n≤2Subtask 220 pointsn ≤ 17 n\leq 17n≤17Subtask 315 pointsa i ≤ 2 × 10 3 a_i\leq 2\times 10^3ai≤2×103Subtask 415 pointsn ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103Subtask 510 pointsn ≤ 5 × 10 4 n\leq 5\times 10^4n≤5×104Subtask 610 pointsa i ≤ 10 7 a_i\leq 10^7ai≤107Subtask 725 points无特殊限制。对于100 % 100\%100%的数据1 ≤ n ≤ 3 × 10 5 1\leq n\leq 3\times 10^51≤n≤3×1051 ≤ a i ≤ 10 9 1\leq a_i\leq 10^91≤ai≤109。「帮助/提示」gcd \gcdgcd表示最大公约数l c m \mathrm{lcm}lcm表示最小公倍数。「来源」【LGR-075】洛谷 8 月月赛 II Div.2 SWTR-06 EZEC Round 3。idea solution data by Alex_Wei。枚举令bj,bj的最大公约数是x令cxbi,dxbj则cd,c和d互质,x0。上式⟺ \iff⟺cxdxx cdx⟺ \iff⟺cd1 cd即(c-1)(d-1)2由于0 c d且是整数。故c等于2d等于3。即序列b是一个比为3/2的等比序列。有序集合s记录a。哈希映射e[i]记录以i结尾的最长序列和。通过i枚举s如果i是3的倍数e[i] i e[i/32]否则e[i] i。max(e)就是最大值。注意如果一个数出现多次可以被选择多次。代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#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:longlongAns(vectorinta){mapint,intmCnt;for(constautoi:a){mCnt[i];}unordered_mapint,longlongmSum;longlongllMax0;for(constauto[i,cnt]:mCnt){if(0i%3){mSum[i]i*(longlong)cntmSum[i/3*2];}else{mSum[i]i*(longlong)cnt;}llMaxmax(llMax,mSum[i]);}returnllMax;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGautoaReadint();#ifdef_DEBUG//printf(K%d, K);//Out(a, a);#endif// DEBUGautoresSolution().Ans(a);coutresendl;return0;}单元测试vectorinta;intK;TEST_METHOD(TestMethod11){a{4,3,2,1};autoresSolution().Ans(a);AssertEx(5LL,res);}TEST_METHOD(TestMethod12){a{6,7,18,4,17,10,9,1,3,8};autoresSolution().Ans(a);AssertEx(19LL,res);}TEST_METHOD(TestMethod13){a{123456789,234567890,123456789};autoresSolution().Ans(a);AssertEx(246913578LL,res);}扩展阅读我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。
【枚举】P6786「SWTR-6」GCDs LCMs|普及+
本文涉及知识点枚举「SWTR-6」GCDs LCMs题目描述小 A 有一个长度为n nn的序列a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an。他想从这些数中选出一些数b 1 , b 2 , ⋯ , b k b_1,b_2,\cdots,b_kb1,b2,⋯,bk满足对于所有i ( 1 ≤ i ≤ k ) i\ (1\leq i\leq k)i(1≤i≤k)b i b_ibi要么是序列b bb中的最大值要么存在一个位置j jj使得b j b i b_jb_ibjbi且b i b j gcd ( b i , b j ) l c m ( b i , b j ) b_ib_j\gcd(b_i,b_j)\mathrm{lcm}(b_i,b_j)bibjgcd(bi,bj)lcm(bi,bj)。如果你不知道gcd \gcdgcd和l c m \mathrm{lcm}lcm是什么可以点击最底部的「帮助/提示」部分的链接。小 A 想让选出的数之和尽量大。请求出这个最大值。输入格式第一行一个整数n nn表示序列的长度。第二行n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an。输出格式输出一行一个整数表示答案。样例 #1样例输入 #14 4 3 2 1样例输出 #15样例 #2样例输入 #210 6 7 18 4 17 10 9 1 3 8样例输出 #219样例 #3样例输入 #33 123456789 234567890 123456789样例输出 #3246913578提示「样例 1 说明」可以选择b { 2 , 3 } b\{2,3\}b{2,3}因为2 3 gcd ( 2 , 3 ) l c m ( 2 , 3 ) 23\gcd(2,3)\mathrm{lcm}(2,3)23gcd(2,3)lcm(2,3)。「数据范围与约定」本题采用捆绑测试。Subtask 15 pointsn ≤ 2 n\leq2n≤2Subtask 220 pointsn ≤ 17 n\leq 17n≤17Subtask 315 pointsa i ≤ 2 × 10 3 a_i\leq 2\times 10^3ai≤2×103Subtask 415 pointsn ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103Subtask 510 pointsn ≤ 5 × 10 4 n\leq 5\times 10^4n≤5×104Subtask 610 pointsa i ≤ 10 7 a_i\leq 10^7ai≤107Subtask 725 points无特殊限制。对于100 % 100\%100%的数据1 ≤ n ≤ 3 × 10 5 1\leq n\leq 3\times 10^51≤n≤3×1051 ≤ a i ≤ 10 9 1\leq a_i\leq 10^91≤ai≤109。「帮助/提示」gcd \gcdgcd表示最大公约数l c m \mathrm{lcm}lcm表示最小公倍数。「来源」【LGR-075】洛谷 8 月月赛 II Div.2 SWTR-06 EZEC Round 3。idea solution data by Alex_Wei。枚举令bj,bj的最大公约数是x令cxbi,dxbj则cd,c和d互质,x0。上式⟺ \iff⟺cxdxx cdx⟺ \iff⟺cd1 cd即(c-1)(d-1)2由于0 c d且是整数。故c等于2d等于3。即序列b是一个比为3/2的等比序列。有序集合s记录a。哈希映射e[i]记录以i结尾的最长序列和。通过i枚举s如果i是3的倍数e[i] i e[i/32]否则e[i] i。max(e)就是最大值。注意如果一个数出现多次可以被选择多次。代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#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:longlongAns(vectorinta){mapint,intmCnt;for(constautoi:a){mCnt[i];}unordered_mapint,longlongmSum;longlongllMax0;for(constauto[i,cnt]:mCnt){if(0i%3){mSum[i]i*(longlong)cntmSum[i/3*2];}else{mSum[i]i*(longlong)cnt;}llMaxmax(llMax,mSum[i]);}returnllMax;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGautoaReadint();#ifdef_DEBUG//printf(K%d, K);//Out(a, a);#endif// DEBUGautoresSolution().Ans(a);coutresendl;return0;}单元测试vectorinta;intK;TEST_METHOD(TestMethod11){a{4,3,2,1};autoresSolution().Ans(a);AssertEx(5LL,res);}TEST_METHOD(TestMethod12){a{6,7,18,4,17,10,9,1,3,8};autoresSolution().Ans(a);AssertEx(19LL,res);}TEST_METHOD(TestMethod13){a{123456789,234567890,123456789};autoresSolution().Ans(a);AssertEx(246913578LL,res);}扩展阅读我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。
