[IOI2014] friend 朋友
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目背景
这是一道交互题
题目描述
我们建立了一个由编号为 的 个人组成的社交网络。网络中的有些对会成为朋友。如果 号人成为 号人的朋友,则 号人同时也会成为 号人的朋友。
这些人将通过 个阶段加入这个网络,阶段也编号为 至 。第 号人在第 个阶段加入。在阶段 , 号人加入网络并成为唯一的人。此后 个阶段的各个阶段,都有一个人会被主持人加入到网络中,而这个主持人可以是已在网络中的任何一个人。在阶段 中(),该阶段的主持人可以用如下三种方式之一把第 号人加入到网络中:
- IAmYourFriend:将第 号人仅变成主持人的朋友。
- MyFriendsAreYourFriends:将第 号人变成主持人当前的每一个朋友的朋友。 注意,这个方式不会将第 号人变成主持人的朋友。
- WeAreYourFriends:将第 号人变成主持人的朋友,同时也变成主持人当前的每一个朋友的朋友。
在建立此网络之后,我们想挑选一个调查的样本,也就是说要从网络中选择一组人。由于朋友之间通常拥有相似的兴趣,因此样本不应包含任何一对互为朋友的人。每个人都会有一个调查的可信度,表示为一个正整数,而我们想要找出一个可信度总和最大的样本。
任务
给定各阶段的描述以及每个人的可信度值,请找出一个可信度总和最大的样本。你只需要实现函数 findSample
。
findSample(n, confidence, host, protocol)
- : 人数.
confidence
: 大小为 的数组;confidence[i]
表示第 号人的可信度。host
: 大小为 的数组;host[i]
表示阶段 i 的主持人。protocol
: 大小为 的数组;protocol[i]
表示在阶段 () 所采用的方式的代码:0
代表 IAmYourFriend,1
代表 MyFriendsAreYourFriends,而2
代表 WeAreYourFriends。- 由于在阶段
0
中没有主持人,因此host[0]
和protocol[0]
是没有被定义的,而且在你的程序中也不应访问它们。
这个函数应该返回样本可信度总和的最大值。
输入格式
以下为交互库的输入格式。
第 行:一个正整数 ,为人数。
第 行:共 个整数 $\mathrm{confidence}[0],\ldots,\mathrm{confidence}[n-1]$.
第 行:共 个整数 $\mathrm{host}[1],\mathrm{protocol}[1], \mathrm{host}[2], \mathrm{protocol}[2],\cdots, \mathrm{host}[n-1], \mathrm{protocol}[n-1]$。
输出格式
本题只支持 C++ 系列语言。
你只能提交一个源文件实现上述的函数,其命名与接口需遵循下面的要求。不需要添加额外的头文件。
int findSample(int n, int confidence[], int host[], int protocol[]);
6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0
35
提示
对于 的数据,,。
子任务 | 分值 | 可信度 | 采用的方式 | |
---|---|---|---|---|
1 | 全部三种方式 | |||
2 | 只有 MyFriendsAreYourFriends |
|||
3 | 只有 WeAreYourFriends |
|||
4 | 只有 IAmYourFriend |
|||
5 | 所有可信度值均为 | 只有 MyFriendsAreYourFriends 和 IAmYourFriend 两种方式 |
||
6 | 全部三种方式 |
暑期康复训练二
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2024-8-2 7:30
- End at
- 2024-8-2 12:00
- Duration
- 4.5 hour(s)
- Host
- Partic.
- 30