本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1466 [USACO2.2] 集合 Subset Sums - 洛谷【题目描述】对于从 1∼n的连续整数集合能划分成两个子集合且保证每个集合的数字和是相等的。举个例子如果n3对于 {1,2,3} 能划分成两个子集合每个子集合的所有数字和是相等的{3} 和 {1,2} 是唯一一种分法交换集合位置被认为是同一种划分方案因此不会增加划分方案总数如果n7有四种方法能划分集合 {1,2,3,4,5,6,7}每一种分法的子集合各数字和是相等的{1,6,7} 和 {2,3,4,5}{2,5,7} 和 {1,3,4,6}{3,4,7} 和 {1,2,5,6}{1,2,4,7} 和 {3,5,6}给出n你的程序应该输出划分方案总数。【输入】输入文件只有一行且只有一个整数n【输出】输出划分方案总数。【输入样例】7【输出样例】4【核心思想】问题分析给定n nn将集合{ 1 , 2 , … , n } \{1, 2, \ldots, n\}{1,2,…,n}划分为两个子集使两子集元素和相等。求划分方案总数交换两子集位置视为同一种方案。总和S n ( n 1 ) 2 S \frac{n(n1)}{2}S2n(n1)​若S SS为奇数则无解否则每个子集目标和为m S 2 m \frac{S}{2}m2S​。问题转化为从{ 1 , … , n } \{1, \ldots, n\}{1,…,n}中选取若干个数使其和恰好为m mm的方案数。算法选择01 背包变形计数型 DPd p [ i ] [ j ] dp[i][j]dp[i][j]表示从前i ii个数中选取若干个数使其和为j jj的方案数状态转移对于第i ii个数可选可不选不选方案数为d p [ i − 1 ] [ j ] dp[i-1][j]dp[i−1][j]选方案数为d p [ i − 1 ] [ j − i ] dp[i-1][j-i]dp[i−1][j−i]前提是j ≥ i j \ge ij≥i最终答案d p [ n ] [ m ] dp[n][m]dp[n][m]因交换两子集视为同一种方案无需除以 2关键步骤读入n nn计算总和t o t n ( n 1 ) 2 tot \frac{n(n1)}{2}tot2n(n1)​奇数特判若t o t m o d 2 1 tot \bmod 2 1totmod21输出0 00并退出初始化m t o t 2 m \frac{tot}{2}m2tot​d p [ 1 ] [ 1 ] 1 dp[1][1] 1dp[1][1]1选数字 1 和为 1 的方案有 1 种DP 递推i ii从2 22到n nnj jj从0 00到m mm若j i j ijid p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j] dp[i-1][j]dp[i][j]dp[i−1][j]当前数太大无法选取若j ≥ i j \ge ij≥id p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i − 1 ] [ j − i ] dp[i][j] dp[i-1][j] dp[i-1][j-i]dp[i][j]dp[i−1][j]dp[i−1][j−i]不选或选第i ii个数输出d p [ n ] [ m ] dp[n][m]dp[n][m]时间/空间复杂度时间复杂度O ( n ⋅ m ) O ( n 3 ) O(n \cdot m) O(n^3)O(n⋅m)O(n3)其中m n ( n 1 ) 4 m \frac{n(n1)}{4}m4n(n1)​空间复杂度O ( n ⋅ m ) O ( n 3 ) O(n \cdot m) O(n^3)O(n⋅m)O(n3)二维 DP 数组计数型 DP 的核心思想子集和问题转化集合划分等价于找一个子集使其和为总和的一半另一半自动确定方案数累加与 01 背包求最大值不同计数型 DP 将取最大值改为方案数相加避免重复计数因只统计一个子集的方案数另一个子集被唯一确定自然避免了交换位置的重复奇数和无解总和为奇数时无法均分直接返回 0适用于子集划分、整数拆分、计数型背包等问题【解题思路】【算法标签】#普及 #递推【代码详解】#includebits/stdc.husingnamespacestd;intn,m,dp[45][4000];intmain(){cinn;// 输入nmn*(n1)/4;// 每个组合的数的总和要是1-n总和的1/2inttotn*(n1)/2;// 计算n个数的总和if(tot%21){// 这里要特判否则最后一个测试点无法通过cout0endl;// 如果和为奇数就找不到方案return0;}dp[1][1]1;// dp[i][j]i为第i个数j为背包大小有点类似01背包但递推公式不完全是for(inti2;in;i){// 从第二个数开始遍历for(intj0;jm;j){// 遍历背包大小if(ji){// 01背包这里是jw[i]题目中w[i]i所以写成jidp[i][j]dp[i-1][j];// 如果背包放不下方案数等于上一个i的方案数}else{// 如果装的下dp[i][j]dp[i-1][j]dp[i-1][j-i];// 方案数等于上一个i的方案数加上上一个i的j-i的方案数这里不用像01背包加c[i]}}}coutdp[n][m]endl;// 输出结果return0;}【运行结果】7 4