P1810 集合分组题解-CSDN博客

本文链接：https://blog.csdn.net/luogu_553625/article/details/134557861

文章介绍了如何解决一个关于集合相似性的编程问题，通过计算元素和的模数来确定集合之间的关系，并给出了一个C++代码示例。关键在于理解集合元素和的性质以及使用模运算进行分组。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

P1810 集合分组题解

限制条件很弱的题，感觉有点太水了。

解法

考虑两个集合相似的条件。仔细读题发现 $n$ 这个条件很怪，于是断定答案一定与 $n$ 有关。

根据题目描述，两个集合相等则不相似。若两个集合中元素的和相等，则两集合相等，或者两集合至少有两个元素不同，无法通过更改一个集合中的一个元素使两集合相等。

若两集合相似，则两集合只有一个（或一对）元素不同。题中说了集合中的数都为正数，且不大于 $n$ ，所以两相似集合中元素的和的差的绝对值在 $[1, n]$ 之间。所以以 $n + 1$ 为模数对相似集合中元素的和取模，两个余数肯定不相同。一个命题的逆否命题等价于该命题，所以如果两个集合的余数相同，则两个集合一定不相似。我们就可以将这 $k$ 个集合根据其余数分成 $n + 1$ 个组，集合编号即为余数。注意到会有余数为 $0$ 的情况，我们只要把 $0$ 放到编号为 $n + 1$ 的组里就行了。

题中说 $m > n$ ，所以这个问题一定有解。

代码

#include<bits/stdc++.h>
int n,k,m,sum[50010];
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1,num,tmp;i<=k;i++)
	{
		scanf("%d",&num);
		for(int j=1;j<=num;j++) scanf("%d",&tmp),sum[i]+=tmp;
	}
	for(int i=1;i<=k;i++) printf("%d\n",sum[i]%(n+1)+1);
	return 0;
}