寻找团伙

Luogu

IDLGB3618

Time1000ms

Memory128MB

DifficultyP2

搜索深度优先搜索 DFS进制位运算

世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 $n$ 个人里面挑选一部分人共襄盛举。要办这件事，一共涉及 $k$ 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执不下，导致整个团队丧失这方面的能力。相应地，如果这项能力只有奇数个人拥有，那么他们总能形成一个多数派，帮团队去做这方面的工作。需要注意的是，团队拥有的每一项能力，对计划的成功率的贡献是不一样的。第一项能力最重要，它的权重是 $2^{k-1}$；第二项能力的权重是 $2^{k-2}$；依次类推。第 $k$ 项能力最不重要，权重只有 $1$。计划的成功率得分，即是**团队拥有的所有能力对应的权重之和**。你希望计划成功率最大。因此，你需要选出合适的人士，来参与到你的宏图伟业中。 ## Input 第一行，两个正整数 $n, k$。分别表示供你挑选的人的数量，以及能力的种类数。接下来 $n$ 行，每行表示每个人拥有的能力。这一行首先有一个整数 $c$，表示该人士拥有多少种能力；接下来是 $c$ 个 $[1, k]$ 之间的正整数，表示该人士拥有哪些能力。 ## Output 仅一行，一个整数，表示计划的成功率得分。 [samples] ## Note #### 样例解释第一组样例，共 5 个人，每个人拥有的能力不一样。最终选择的结果是让这 5 个人都参与计划，得分 $16+8+4+2+1 = 31$。第二组样例，我们选择只让 $1$ 参与。那么团队具有能力 $1,2, 3$，得分 $16+8+4=28$。第三组样例，我们让 $1,2,3$ 参与。由于团队中有偶数个成员拥有能力 $5$，故团队并不拥有能力 $5$。奇数个成员拥有能力 $2$，故团队拥有能力 $2$。最终，团队具有能力 $1,2,3,4$。得分 $16+8+4+2=30$。 #### 数据规模与约定对于 $100\%$ 的数据，有 $n\leq 21, k\leq 60$。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

21 60
0 
0 
3 60 27 48
0 
1 48
2 52 14
2 4 31
0 
0 
2 28 43
2 6 31
0 
1 7
3 45 6 48
0 
1 51
0 
2 28 20
2 37 51
1 8
53 59 39 29 23 53 27 13 16 44 34 38 24 9 32 58 54 31 1 7 45 3 30 36 17 48 42 22 18 21 6 11 25 33 37 52 10 60 49 57 2 28 8 14 5 47 4 41 35 43 50 46 26 12

Output #4

1152884121210322895

API Response (JSON)

{
  "problem": {
    "name": "寻找团伙",
    "description": {
      "content": "世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 $n$ 个人里面挑选一部分人共襄盛举。 要办这件事，一共涉及 $k$ 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。 你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3618"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 $n$ 个人里面挑选一部分人共襄盛举。\n\n要办这件事，一共涉及 $k$ 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。\n\n你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments