P7945 「Wdcfr-1」Yet Another Cirno Game (easy version)

题目描述

**两个版本之间的唯一区别是是否需要找到一种方法来获得最大分数。** 琪露诺画了一张图。这张图包含 $4\cdot n$ 个节点,编号为 $0$ 到 $4\cdot n - 1$。此外: - 对于任何 $0\le i\le 3$ 和 $0 \le j, k < n$,节点 $(n\cdot i + j)$ 和节点 $(n\cdot i + k)$ 是连接的。 - 对于任何 $0 \le i < n$ 和 $0 \le j, k \le 3$,节点 $(i + n\cdot j)$ 和节点 $(i + n\cdot k)$ 是连接的。 琪露诺叫来了大妖精和她一起玩。 游戏规则如下: - 首先,琪露诺选择 $2\cdot n$(即一半)的节点,并将它们涂成蓝色。其余的节点保持红色。 - 然后进行 $2\cdot n$ 回合:每回合中,琪露诺首先选择一个蓝色节点,而大妖精选择一个红色节点。如果这两个节点是连接的,大妖精得一分。 尝试最大化大妖精获得的分数。

输入格式

第一行包含一个整数 $n$。接下来一行有 $2\cdot n$ 个数字:它们是琪露诺选择的节点。

输出格式

对于每个测试用例,输出一个整数 $x$,表示大妖精可以获得的最大分数。 在这个版本中,你不需要输出其他任何东西。

说明/提示

### 解释 在下图中,矩阵中的节点是相互连接的。琪露诺选择了节点 $0,1,2,3,4,5$。 下面的箭头显示了大妖精可以获得的最大分数的一种可能方式。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7v3w2cz9.png) ### 约束 $1\le n\le 2\times 10^6$。 题面翻译由 ChatGPT-4o 提供。