本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P7962 [NOIP2021] 方差 - 洛谷【题目描述】给定长度为n nn的非严格递增正整数数列1 ≤ a 1 ≤ a 2 ≤ ⋯ ≤ a n 1 \le a_1 \le a_2 \le \cdots \le a_n1≤a1​≤a2​≤⋯≤an​。每次可以进行的操作是任意选择一个正整数1 i n 1 i n1in将a i a_iai​变为a i − 1 a i 1 − a i a_{i - 1} a_{i 1} - a_iai−1​ai1​−ai​。求在若干次操作之后该数列的方差最小值是多少。请输出最小值乘以n 2 n^2n2的结果。其中方差的定义为数列中每个数与平均值的差的平方的平均值。更形式化地说方差的定义为D 1 n ∑ i 1 n ( a i − a ˉ ) 2 D \frac{1}{n} \sum_{i 1}^{n} {(a_i - \bar a)}^2Dn1​∑i1n​(ai​−aˉ)2其中a ˉ 1 n ∑ i 1 n a i \bar a \frac{1}{n} \sum_{i 1}^{n} a_iaˉn1​∑i1n​ai​。【输入】输入的第一行包含一个正整数n nn保证n ≤ 10 4 n \le {10}^4n≤104。输入的第二行有n nn个正整数其中第i ii个数字表示a i a_iai​的值。数据保证1 ≤ a 1 ≤ a 2 ≤ ⋯ ≤ a n 1 \le a_1 \le a_2 \le \cdots \le a_n1≤a1​≤a2​≤⋯≤an​。【输出】输出仅一行包含一个非负整数表示你所求的方差的最小值的n 2 n^2n2倍。【输入样例】4 1 2 4 6【输出样例】52【解题思路】【算法标签】#省选# #线性DP-一维#【代码详解】// 32分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN2005;intn;// 序列长度inta[N];// 原始序列intda[N];// 差分序列signedmain(){cinn;// 输入序列长度for(inti1;in;i)// 输入原始序列{cina[i];}// 计算差分序列da[i] a[i1] - a[i]for(inti1;in;i){da[i]a[i1]-a[i];}// 对差分序列进行排序为全排列做准备sort(da1,dan);intans1e9;// 初始化答案为无穷大// 枚举差分序列的所有排列do{ints10;// 用于计算 Σfᵢ²ints20;// 用于计算 Σfᵢintfa0;// 累积的f值// 根据当前排列计算f值for(inti1;in;i){fada[i];// 计算当前的f值s1fa*fa;// 累加fᵢ²s2fa;// 累加fᵢ}// 计算当前排列的代价n * Σfᵢ² - (Σfᵢ)²ansmin(ans,n*s1-s2*s2);}while(next_permutation(da1,dan));// 生成下一个排列coutansendl;// 输出最小代价return0;// 程序正常结束}// 100分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN10005,M500005,INF1e18;intn;// 序列长度inta[N];// 原始序列intd[N];// 差分序列ints[N];// 差分序列的前缀和intans1e18;// 最终答案intdp[2][M];// 滚动数组用于动态规划signedmain(){// 输入处理cinn;// 输入序列长度for(inti1;in;i)// 输入原始序列{cina[i];}// 计算差分序列d[i] a[i1] - a[i]for(inti1;in;i){d[i]a[i1]-a[i];}// 对差分序列进行排序sort(d1,dn);// 计算差分序列的前缀和for(inti1;in;i){s[i]s[i-1]d[i];}// 动态规划初始化dp[0][0]0;// 初始状态没有元素时总和为0// 动态规划主循环for(inti0;in-1;i)// 处理差分序列的前i1个元素{// 初始化下一行的dp数组为无穷大for(intj0;js[i1]*(i1);j){dp[1][j]INF;}// 状态转移for(intj0;js[i]*i;j)// 枚举当前可能的总和{if(dp[0][j]INF)// 如果当前状态可达{// 转移1: 将d[i1]加入当前集合dp[1][js[i1]]min(dp[1][js[i1]],dp[0][j]s[i1]*s[i1]);// 转移2: 以某种方式处理d[i1] (需要推导具体含义)dp[1][j(i1)*d[i1]]min(dp[1][j(i1)*d[i1]],dp[0][j](i1)*d[i1]*d[i1]2*j*d[i1]);}}// 滚动数组将下一行的值复制到当前行for(intj0;js[i1]*(i1);j){dp[0][j]dp[1][j];}}// 在最终状态中寻找最优解for(intS0;Ss[n-1]*(n-1);S)// 枚举所有可能的总和{if(dp[0][S]INF)// 如果状态不可达跳过{continue;}// 计算最终代价n * dp[0][S] - S * Sansmin(ans,n*dp[0][S]-S*S);}coutansendl;// 输出最小代价return0;// 程序正常结束}【运行结果】4 1 2 4 6 52