d445 - C-分堆大考驗

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算對於從 1 到 N 的連續整數集合，能劃分成兩個和相等的子集合的方案數。如果不存在這樣的劃分方案，則輸出 0。

解題思路

首先，計算從 1 到 N 的總和 tol = (sum + 1) * sum / 2。如果 tol 是奇數，則不可能劃分為兩個和相等的子集合，直接輸出 0。

如果 tol 是偶數，則問題等價於尋找從 1 到 N 的數字中，和為 tol / 2 的子集合的數量。可以使用動態規劃來解決這個問題。

定義 b[i] 為和為 i 的子集合的數量。初始化 b[0] = 1，表示和為 0 的空集合存在一個。

然後，遍歷從 N 到 1 的數字 a。對於每個數字 a，從 tol / 2 到 0 遍歷 i。如果 b[i] 不為 0 且 i + a <= tol / 2，則 b[i + a] += b[i]。這表示如果和為 i 的子集合存在，那麼和為 i + a 的子集合也存在。

最後，b[tol / 2] 包含和為 tol / 2 的子集合的數量。由於交換集合位置被認為是同一種劃分方案，因此需要將結果除以 2。

複雜度分析

• 時間複雜度: O(N * (N*(N+1)/2)/2) = O(N^3)
• 空間複雜度: O(N*(N+1)/2) = O(N^2)

程式碼

#include <iostream>
using namespace std;
int main(){
	long long int sum;
	while(cin >> sum){
		long long int tol;
		tol=(sum+1)*sum/2;
		if(tol%2==1)
			cout << "0\n";
		else{
			long long int b[tol/2+1]={0};
			b[0]=1;
			for(int a=sum;a>=1;a--){
				for(int i=tol/2;i>=0;i--){
					if(b[i]!=0&&i+a<=tol/2){
						b[i+a]+=b[i];
					}
				}
			}
			cout << b[tol/2]/2 << "\n";
		}
	}
}