翻译
查看原帖
翻译
461012
dyyzy楼主2024/8/13 16:28

题目描述

FJ 的 NN 头奶牛加入了社交网络“牛书”。

每一头奶牛在牛书上都有一个或多个与他互动的朋友,FJ 做了一个列表,列出了所有奶牛的每一个朋友。但在这一过程中,他错误地将一个额外的数字加入了列表。(所以最终的列表包含 N+1N+1 个数字,而不是预期的 NN 个数字)

请帮助 FJ 找出哪一个数字可能是那一个错误的数字。

输入格式

第 11 行:一个整数 NN。

第 22 至 N+2N+2 行:第 i+1i+1 行包括一头奶牛的朋友的个数,也有可能是错误的那个数字。

输出格式

第 11 行:一个整数 kk,表示有多少个数字可能是错误的(若 k=0k = 0,表示移出任意一个数字都无法产生一个可行的朋友配对)

第 22 至 K+1K+1 行:每一行包括一个 FJ 列表标号的索引,该索引对应的数字可能是额外的标号。也就是说,这个数字被移除可使得剩余的 NN 个数字成为一个合法的朋友关系。索引按顺序输出。

说明/提示

FJ 有四头奶牛。其中两头有一个朋友,两头有两个朋友,一头有三个朋友(当然,其中一个数字是错误的,不应出现在列表上)。

移除 FJ 列表上的第一个数字(数字 11)余下的序列是 2,2,1,32,2,1,3,是合法的。如果我们把四头奶牛命名为A,B,C,D,这样就有(A,B),(A,C),(A,D),(B,C)的配对方式,其中A有三个朋友,B,C有两个朋友,D有一个朋友。同样的,移除列表中的其他数字 11 或 33,也可以形成合法的朋友关系,移除数字 22 则无法形成合法的朋友关系。容易发现,若移除了数字 22,剩余的数字为奇数,显然无法形成合法的朋友关系。

2024/8/13 16:28
加载中...