P1810 集合分组 题解

2023/11/22 Blog

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

解法

考虑两个集合相似的条件。仔细读题发现 $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;
}
对我博客最大的鼓励来自于你的评论(什么玩梗),欢迎选择 来回复, 也可以在 GitHub discussion 留言。

Search

    公告

    博主这下真摆烂了。我下辈子也不碰 Jekyll 和 MathJax 了!
    留言板,现在博主的精神状态非常好,有事烧纸。

    联系方式

    QQ: 33299235
    email: 33299235@qq.com
    Gmail: scp020.cn@gmail.com

    本人的其它个人主页

    洛谷
    CSDN

    友链

    拜谢stevehim(已退役,祝好)
    拜谢日记
    拜谢cppomstar

    views counting

    Document

    Table of Contents