专栏文章

题解：P1025 [NOIP2001 提高组] 数的划分

别别人内卷我在躺平
P1025题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqds3si
此快照首次捕获于
2025/12/04 03:09
3 个月前
此快照最后确认于
2025/12/04 03:09
3 个月前
查看原文
本题算法：搜索。
这题就是分苹果，一模一样。注意到题目有一句话：“每份不能为空，任意两个方案不相同。”那么，什么是相同呢？就是说 2,2,32,2,3 和 3,2,23,2,2 是重复的，那么，我们可以让分配方案中的每一份都递增。我们用 ansans 数组存储答案，每次从 ansx−1ans_{x-1} 开始枚举到 n−sumn-sum。这里的 sumsum 就是剩下的数的和，因为如果和超过了 nn 那么这个方案就不成立了。在循环时，如果这个数没有用过，就存进答案，看下一个数，否则退回来，把标记也变成 00，和减去 ii。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int n,k;
int ans[maxn];
int sum=0;
int total=0;
void dfs(int x)
{
	if(x>k)
	{
		if(sum==n) total++;
		return ;
	}
	for(int i=ans[x-1];i<=n-sum;i++)
	{
		if(i==0) continue;
		ans[x]=i;
		sum+=i;
		dfs(x+1);
		
		ans[x]=0;
		sum-=i;
	}
}
signed main()
{
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	dfs(1);
	cout<<total; 
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...