列表

详情

NC237542. Interesting Set

描述

A set consisting of positive integers is called , if after arbitrarily deleting one of its elements, the remaining set can be divided into two subsets with equal sum.

Given a positive integer n, please construct an interesting set with exactly n elements, or report that it is impossible. To simplify the checking progress, you need to point out the approach of dividing the set when each of the elements is deleted, if there exists a solution.

输入描述

The first and only line of input contains a single integer , the requiring size of the set.

输出描述

If there is no solution, print a single .

Otherwise, print a single  in the first line. The second line should contains n space-separated integers , denoting the elements of the set. The integers must be pairwise distinct. It can be shown that if a solution exists, there must be a solution with all .

After that, for each i from 1 to n, print a line to give out your division of subsets when the i-th element is deleted. The line should begin with a number  denoting the size of one of the subset, followed by k_i pairwise distinct integers  denoting the indices of elements of the subset.  must be held. The checker will automatically computes the other subset and check whether they have equal sums.

示例1

输入: 

6

输出: 

NO

示例2

输入: 

7

输出: 

YES
1 3 5 7 9 11 13 
4 2 3 4 5 
3 1 5 7 
4 1 2 4 6 
3 2 3 7 
2 4 7 
3 2 4 5 
4 1 2 3 5

说明:

For the first example, it can be proved that there is no solution with n=6.

For the second example, \{1,3,5,7,9,11,13\} is an interesting set. For example, if you delete 1 from the set, you can divide the remaining set into \{3,5,7,9\} and \{11,13\} with 3+5+7+9=24=11+13, and when deleting 13 from the set, we have 1+3+5+9=20=7+13.

Note that you can print a_1,...,a_n in arbitrary order, not necessarily sorted. The sample output above sorts them for better reading experience. The same goes for A_{i,1},...,A_{i,k_i}.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 386ms, 内存消耗: 6216K, 提交时间: 2022-11-21 22:09:24 

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int N=2020;
int a[N];
int st[N];
int cnt;
int n;
int t;
bool dfs(int step,int sum)
{
	if(sum==0)
	{
		cnt=step;
		return true;
	}
	
	for(int i=n;i>=1;i--)
	{
		if(a[i]>sum||t==i)continue;
		if(st[i])continue;
		st[i]=1;
		if(dfs(step+1,sum-a[i]))return true;
		st[i]=0;
	}
	return false;
}
signed main()
{
	
	cin>>n;
	if(n<=6||n%2==0)
	{
		cout<<"NO"<<endl;
	}
	else 
	{
		cout<<"YES"<<endl;
		int sum=0;
		for(int i=1;i<=n;i++)a[i]=i*2-1,sum+=a[i],cout<<a[i]<<" ";
		cout<<endl;
		for(int i=1;i<=n;i++)
		{
			t=i;
			int x=(sum-a[i])/2;
			//flag=0;
			for(int j=1;j<=n;j++)st[j]=0;
			dfs(0,x);
			cout<<cnt<<" ";
			for(int j=1;j<=n;j++)
			if(st[j])cout<<j<<" ";
			cout<<endl;
		}
	}
}

C++ 解法, 执行用时: 97ms, 内存消耗: 6104K, 提交时间: 2022-05-28 15:56:58 

#include<bits/stdc++.h>
using namespace std;

#define N 2010
int n,a[N];
int m,opt[N];

bool dfs(int u,int nw,int goal,int ban){
	if(u==0) return 0;
	if(a[u]!=ban && nw+a[u]<=goal){
		opt[++m]=u;
		if(nw+a[u]==goal){
			printf("%d ",m);
			for(int i=1;i<=m;i++) printf("%d ",opt[i]);
			printf("\n");
			return 1;
		}
		if(dfs(u-1,nw+a[u],goal,ban)==1) return 1;
		--m;
	}
	return dfs(u-1,nw,goal,ban);
}

int main(){
	scanf("%d",&n);
	if(n<=6 || n%2==0){
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	for(int i=1;i<=n;i++) a[i]=i*2-1;
	for(int i=1;i<=n;i++) printf("%d ",a[i]);printf("\n");
	for(int i=1;i<=n;i++){
		m=0;
		dfs(n,0,(n*n-a[i])/2,a[i]);
	}
	return 0;
}

上一题

© 2025 nowcoder.com