本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Farm Harvest Festival【题目描述】Takahashi manages a vast farm.The farm hasN NNplots arranged in a row, numbered from1 11toN NN. Ploti ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)has a fruit tree planted in it, and the amount of fruit that can be harvested from it isA i A_iAikilograms.During the harvest festival, Takahashi performsM MMharvesting operations. In thej jj-th( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)harvesting operation, he harvests fruit from all consecutive plots from plotL j L_jLjto plotR j R_jRj.The fruit in each plot is gone once harvested. Therefore, even if a plot is included in multiple harvesting operations, the yield obtained from that plot is only from the first time, namelyA i A_iAikilograms.In other words, the total harvest Takahashi obtains is the sum ofA i A_iAiover all plots that were targeted by at least one of theM MMharvesting operations. Find this total harvest.高桥管理着一个广阔的农场。农场有N NN块田地排成一行编号从1 11到N NN。田地i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N里种着一棵果树可以从上面收获的水果量为A i A_iAi公斤。在丰收节期间高桥执行M MM次收割操作。在第j jj次1 ≤ j ≤ M 1 \leq j \leq M1≤j≤M收割操作中他从田地L j L_jLj到田地R j R_jRj的所有连续地块中收割水果。每块田地的水果一旦被收割就会消失。因此即使一块田地包含在多次收割操作中从该田地获得的产量也只有第一次即A i A_iAi公斤。换句话说高桥获得的总收成是所有被至少一次收割操作覆盖过的田地的A i A_iAi之和。求这个总收成。【输入】N NNM MMA 1 A_1A1A 2 A_2A2… \ldots…A N A_NANL 1 L_1L1R 1 R_1R1L 2 L_2L2R 2 R_2R2⋮ \vdots⋮L M L_MLMR M R_MRMThe first line contains the number of plotsN NNand the number of harvesting operationsM MM, separated by a space.The second line contains the amounts of fruit harvestable from each plotA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,AN, separated by spaces.In the followingM MMlines, thej jj-th line( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)contains the left endpointL j L_jLjand right endpointR j R_jRjof the range of plots targeted by thej jj-th harvesting operation, separated by a space.【输出】Output the total harvest of fruit that Takahashi obtains, in a single line.【输入样例】5 3 10 20 30 40 50 1 3 2 4 4 5【输出样例】150【算法标签】#差分【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 定义数组最大容量constintN200005;// 全局变量声明intn,m;// n: 数组长度, m: 区间操作次数intans;// 最终答案inta[N];// 原始数组intda[N];// 差分数组用于高效记录区间覆盖// 主函数入口signedmain(){// 读取数组长度n和区间操作次数mcinnm;// 读取原始数组元素for(inti1;in;i)cina[i];// 处理m次区间操作使用差分数组标记覆盖范围while(m--){intl,r;// 区间的左右端点cinlr;da[l];// 左端点标记开始da[r1]--;// 右端点后一位标记结束}// 通过前缀和还原每个位置被覆盖的次数for(inti1;in;i)da[i]da[i-1]da[i];// 累加所有被覆盖过的位置的元素值for(inti1;in;i)if(da[i])// 如果该位置被覆盖过至少一次ansa[i];// 输出最终结果coutansendl;return0;}【运行结果】5 3 10 20 30 40 50 1 3 2 4 4 5 150
题解：AtCoder AT_awc0088_c Farm Harvest Festival
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Farm Harvest Festival【题目描述】Takahashi manages a vast farm.The farm hasN NNplots arranged in a row, numbered from1 11toN NN. Ploti ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)has a fruit tree planted in it, and the amount of fruit that can be harvested from it isA i A_iAikilograms.During the harvest festival, Takahashi performsM MMharvesting operations. In thej jj-th( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)harvesting operation, he harvests fruit from all consecutive plots from plotL j L_jLjto plotR j R_jRj.The fruit in each plot is gone once harvested. Therefore, even if a plot is included in multiple harvesting operations, the yield obtained from that plot is only from the first time, namelyA i A_iAikilograms.In other words, the total harvest Takahashi obtains is the sum ofA i A_iAiover all plots that were targeted by at least one of theM MMharvesting operations. Find this total harvest.高桥管理着一个广阔的农场。农场有N NN块田地排成一行编号从1 11到N NN。田地i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N里种着一棵果树可以从上面收获的水果量为A i A_iAi公斤。在丰收节期间高桥执行M MM次收割操作。在第j jj次1 ≤ j ≤ M 1 \leq j \leq M1≤j≤M收割操作中他从田地L j L_jLj到田地R j R_jRj的所有连续地块中收割水果。每块田地的水果一旦被收割就会消失。因此即使一块田地包含在多次收割操作中从该田地获得的产量也只有第一次即A i A_iAi公斤。换句话说高桥获得的总收成是所有被至少一次收割操作覆盖过的田地的A i A_iAi之和。求这个总收成。【输入】N NNM MMA 1 A_1A1A 2 A_2A2… \ldots…A N A_NANL 1 L_1L1R 1 R_1R1L 2 L_2L2R 2 R_2R2⋮ \vdots⋮L M L_MLMR M R_MRMThe first line contains the number of plotsN NNand the number of harvesting operationsM MM, separated by a space.The second line contains the amounts of fruit harvestable from each plotA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,AN, separated by spaces.In the followingM MMlines, thej jj-th line( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)contains the left endpointL j L_jLjand right endpointR j R_jRjof the range of plots targeted by thej jj-th harvesting operation, separated by a space.【输出】Output the total harvest of fruit that Takahashi obtains, in a single line.【输入样例】5 3 10 20 30 40 50 1 3 2 4 4 5【输出样例】150【算法标签】#差分【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 定义数组最大容量constintN200005;// 全局变量声明intn,m;// n: 数组长度, m: 区间操作次数intans;// 最终答案inta[N];// 原始数组intda[N];// 差分数组用于高效记录区间覆盖// 主函数入口signedmain(){// 读取数组长度n和区间操作次数mcinnm;// 读取原始数组元素for(inti1;in;i)cina[i];// 处理m次区间操作使用差分数组标记覆盖范围while(m--){intl,r;// 区间的左右端点cinlr;da[l];// 左端点标记开始da[r1]--;// 右端点后一位标记结束}// 通过前缀和还原每个位置被覆盖的次数for(inti1;in;i)da[i]da[i-1]da[i];// 累加所有被覆盖过的位置的元素值for(inti1;in;i)if(da[i])// 如果该位置被覆盖过至少一次ansa[i];// 输出最终结果coutansendl;return0;}【运行结果】5 3 10 20 30 40 50 1 3 2 4 4 5 150
