luogu#P3104. [USACO14MAR] Counting Friends G
[USACO14MAR] Counting Friends G
题目描述
FJ 的 头奶牛加入了社交网络“牛书”。
每一头奶牛在牛书上都有一个或多个朋友,于是 FJ 做了一个列表,列出了每头奶牛的朋友数量。但在这一过程中,他错误地将一个额外的数加入了列表(所以最终的列表包含 个数,而不是预期的 个数)。
请帮助 FJ 找出哪一个数可能是错误的那个数。
输入格式
第 行:一个整数 。
第 至 行:共 个数,每一行表示一头奶牛的朋友数量,也有可能是错误的那个数。
输出格式
第 行:一个整数 ,表示有多少个数可能是错误的(若 ,表示移出任意一个数都无法产生一个可行的朋友配对)。
第 至 行:每一行包括一个 FJ 列表的编号,对应的数可能是那个错误的数。也就是说,这个数字被移除可使得剩余的 个数字成为一组合法的朋友关系。编号按从小到大顺序输出。
4
1
2
2
1
3
3
1
4
5
提示
样例解释
FJ 有四头奶牛。其中两头有一个朋友,两头有两个朋友,一头有三个朋友(当然,其中一个数字是错误的,不应出现在列表上)。
移除 FJ 列表上的第一个数字,余下的序列是 ,是合法的。如果我们把四头奶牛命名为 ,就有 的配对方式符合要求。同样的,移除列表中的第四、第五个数字,也可以形成合法的朋友关系,移除数字 则无法形成合法的朋友关系。容易发现,若移除了数字 ,剩余的数字为奇数,显然无法形成合法的朋友关系。