企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1466 [USACO2.2] 集合 Subset Sums - 洛谷

【题目描述】

对于从 1∼n的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果n=3，对于 {1,2,3} 能划分成两个子集合，每个子集合的所有数字和是相等的：

{3} 和 {1,2} 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果n=7，有四种方法能划分集合 {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

【核心思想】

1. 问题分析：给定n nn，将集合{ 1 , 2 , … , n } \{1, 2, \ldots, n\}{1,2,…,n}划分为两个子集，使两子集元素和相等。求划分方案总数（交换两子集位置视为同一种方案）。总和S = n ( n + 1 ) 2 S = \frac{n(n+1)}{2}S=2n(n+1)​，若S SS为奇数则无解；否则每个子集目标和为m = S 2 m = \frac{S}{2}m=2S​。问题转化为：从{ 1 , … , n } \{1, \ldots, n\}{1,…,n}中选取若干个数，使其和恰好为m mm的方案数。

2. 算法选择：

   • 01 背包变形（计数型 DP）：d 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

3. 关键步骤：

   • 读入：n nn
   • 计算总和：t o t = n ( n + 1 ) 2 tot = \frac{n(n+1)}{2}tot=2n(n+1)​
   • 奇数特判：若t o t m o d 2 = 1 tot \bmod 2 = 1totmod2=1，输出0 00并退出
   • 初始化：m = t o t 2 m = \frac{tot}{2}m=2tot​，d p [ 1 ] [ 1 ] = 1 dp[1][1] = 1dp[1][1]=1（选数字 1 和为 1 的方案有 1 种）
   • DP 递推（i ii从2 22到n nn，j jj从0 00到m mm）：
     • 若j < i j < ij<i：d 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≥i：d 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]

4. 时间/空间复杂度：

   • 时间复杂度：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(n+1)}{4}m=4n(n+1)​
   • 空间复杂度：O ( n ⋅ m ) = O ( n 3 ) O(n \cdot m) = O(n^3)O(n⋅m)=O(n3)，二维 DP 数组

5. 计数型 DP 的核心思想：

   • 子集和问题转化：集合划分等价于找一个子集使其和为总和的一半，另一半自动确定
   • 方案数累加：与 01 背包求最大值不同，计数型 DP 将"取最大值"改为"方案数相加"
   • 避免重复计数：因只统计一个子集的方案数，另一个子集被唯一确定，自然避免了交换位置的重复
   • 奇数和无解：总和为奇数时无法均分，直接返回 0
   • 适用于子集划分、整数拆分、计数型背包等问题

【解题思路】

【算法标签】

#普及 #递推

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,m,dp[45][4000];intmain(){cin>>n;// 输入nm=n*(n+1)/4;// 每个组合的数的总和要是1-n总和的1/2inttot=n*(n+1)/2;// 计算n个数的总和if(tot%2==1){// 这里要特判（否则最后一个测试点无法通过）cout<<0<<endl;// 如果和为奇数，就找不到方案return0;}dp[1][1]=1;// dp[i][j]，i为第i个数，j为背包大小（有点类似01背包，但递推公式不完全是）for(inti=2;i<=n;i++){// 从第二个数开始遍历for(intj=0;j<=m;j++){// 遍历背包大小if(j<i){// 01背包这里是j<w[i]，题目中w[i]=i，所以写成j<idp[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]）}}}cout<<dp[n][m]<<endl;// 输出结果return0;}

【运行结果】

7 4