「SvR-2」1+2=3

Luogu

IDLGP9088

Time1000ms

Memory128MB

DifficultyP5

贪心2023网络流洛谷原创O2优化图论建模欧拉回路费用流洛谷月赛Ad-hoc

你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。例如，$1\text{ - }2$ 和 $1\text{ - }0$ 两个木棒，如果按 $1\text{ - }0,1\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\text{ - }\textcolor{red}{\underline{\textbf 2}},\textcolor{red}{\underline{\textbf 1}}\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。 ## Input **本题有多组数据。** 输入的第一行一个正整数表示数据组数 $T$。对于每组数据，一行 $9$ 个非负整数，分别表示 $0\text{ - }0,0\text{ - }1,0\text{ - }2,1\text{ - }0,1\text{ - }1,1\text{ - }2,2\text{ - }0,2\text{ - }1,2\text{ - }2$ 型木棒的个数。 ## Output $T$ 行，每行一个整数表示答案。 [samples] ## Note #### 数据规模与约定对于全部数据，保证 $1\le T\le 10^5$，记 $a_{i,j}$ 表示 $i\text-j$ 木棒的个数，保证 $0\le a_{i,j}\le 10^9$。 **本题自动开启捆绑测试和 O2 优化。** 记 $sum$ 表示一个测试点中所有数据的所有 $a_{i,j}$ 之和。 | Subtask | $T$ | $sum$ | 特殊性质 |分值 | | :------: | :------: | :------: | :------: | :------: | | $1$ | $1 \leq T \leq 10$ | $1\le sum\le 10$ |无| $10 \operatorname{pts}$ | | $2$ | $1 \leq T \leq 50$ | $1\le sum\le 80$ | 无|$20 \operatorname{pts}$ | | $3$ | 无特殊限制 | 无特殊限制 |A| $15\operatorname{pts}$ | | $4$ | 无特殊限制 | 无特殊限制 |B| $20 \operatorname{pts}$ | | $5$ | $1\le T\le 1000$ | 无特殊限制 |C| $20 \operatorname{pts}$ | | $6$ | 无特殊限制 | 无特殊限制 |无| $15 \operatorname{pts}$ | 特殊性质 A：$a_{i,j}$ 在 $[0,10^9]$ 中均匀随机生成。特殊性质 B：所有 $a_{i,j}>0$。特殊性质 C：所有 $a_{i,j}\le 100$。

Samples

Input #1

3
4 1 3 4 7 7 9 10 3
6 3 6 4 3 4 5 6 6
6 10 7 1 4 2 6 4 2

Output #1

31
23
19

API Response (JSON)

{
  "problem": {
    "name": "「SvR-2」1+2=3",
    "description": {
      "content": "你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。 例如，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{red}{\\unde",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9088"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。\n\n例如，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{red}{\\unde...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments