首页 > 试题广场 >

选择队伍(hard)

[编程题]选择队伍(hard)
  • 热度指数：1 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}某学校有 4 \times n 名学生，分属四组 \mathrm{a},\,\mathrm{b},\,\mathrm{c},\,\mathrm{d}，每组人数均为 n。定义两名学生之间的默契值为

\displaystyle f(i, j) = (i \oplus j) + (i \mid j) + (i \,\&\, j)

\hspace{15pt}一支队伍由四组学生各选一名学生组队，该队伍的总默契值为

\displaystyle f(a, b) + f(a, c) + f(c, d)

\hspace{15pt}请计算组建 m 支队伍能够获得的最大总默契值，队员不能重复使用。

【名词解释】
\hspace{15pt}其中，\& 表示按位与运算，\mid 表示按位或运算，\oplus 表示按位异或运算。

输入描述:
\hspace{15pt}第一行输入两个整数 n, m \left(1 \le m \le n \le 100\right)，分别表示每组学生的人数和要组建的队伍数；
\hspace{15pt}此后 4 行，每行输入 n 个整数，分别表示四组学生的编号：第 1~4 行对应 \mathrm{a}_i、\mathrm{b}_i、\mathrm{c}_i、\mathrm{d}_i \left(1 \le \mathrm{a}_i,\,\mathrm{b}_i,\,\mathrm{c}_i,\,\mathrm{d}_i \le 2^{30}\right)。


输出描述:
\hspace{15pt}输出一个整数，表示所选队伍的最大总默契值。
示例1

输入

2 1
1 2
1 2
1 2
1 2

输出

18

说明

\hspace{15pt}在这组测试数据中，选择 a_1 = 1、b_2 = 2、c_2 = 2、d_1 = 1 时： 
\hspace{23pt}\bullet\,该情况的具体计算如下： 
\hspace{38pt}\circ\, f(a_1, b_2) = (1 \oplus 2) + (1 \mid 2) + (1 \,\&\, 2) = 3 + 3 + 0 = 6； 
\hspace{38pt}\circ\, f(a_1, c_2) = (1 \oplus 2) + (1 \mid 2) + (1 \,\&\, 2) = 3 + 3 + 0 = 6； 
\hspace{38pt}\circ\, f(c_2, d_1) = (2 \oplus 1) + (2 \mid 1) + (2 \,\&\, 1) = 3 + 3 + 0 = 6； 
\hspace{23pt}\bullet\,因此总默契值为 6 + 6 + 6 = 18，达到最大值。
示例2

输入

10 5
5 23 87 12 45 76 34 99 100 58
10 1 92 34 67 88 45 23 56 79
7 44 90 33 56 11 77 88 22 66
3 55 66 77 88 99 101 202 303 404

输出

5240
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 7浏览

热门推荐

相关试题

选择队伍(hard)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号