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