← 返回题目列表

Codeforces · 1779/G

G. 世纪游戏

中文机器翻译题面 查看原题

时机终于到来,MKnez 和 Baltic 将主办世纪之战。为此,他们建造了一个村庄来安置参与者。

该村庄呈等边三角形,由 3 条长度为 $$$n$$$ 的道路界定。它被 $$$n^2$$$ 分割成 $$$n^2$$$ 较小的等边三角形,边长为 $$$1$$$,并由平行于边的 $$$3n-3$$$ 附加道路切割而成。见图 $$$n=3$$$。每条 $$$3n$$$ 道路均由多个(可能是 $$$1$$$)长度为 $$$1$$$ 的路段组成,这些路段连接相邻的交叉路口。

已为每条 $$$3n$$$ 道路选择了方向(因此,对于每条道路,将相同的方向分配给其所有路段)。交通只能沿指定方向行驶(即道路是单向的)。

您的任务是调整交通规划,以便从每个交叉路口都可以到达其他每个交叉路口。具体来说,您可以反转任意数量长度为 $$$1$$$ 的路段的交通方向。您需要反转交通方向的路段最少有多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 10^5$$$) — 三角形村庄边的大小。

接下来三行,每行包含一个长度为 $$$n$$$ 的二进制字符串,描述道路的交通方向。

下面三行中的第$$$i$$$包含一个长度为$$$n$$$的二进制字符串$$$s_i$$$,表示与上图中$$$i$$$表示的路段平行的每条道路的方向。具体地,如果第$$$j$$$条最短道路(与图中$$$i$$$表示的路段平行)与图中$$$i$$$表示的路段方向相同,则$$$s_i$$$的第$$$j$$$字符为“1”,如果方向相反则为“0”。因此 $$$s_i$$$ 的第一个字符描述仅包含 $$$1$$$ 路段的道路方向,而最后一个字符描述包含 $$$n$$$ 路段的道路方向。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印需要反转交通方向的路段的最小数量。

示例

输入 #1

3
3
001
001
010
1
0
0
0
3
111
011
100

输出 #1

2
0
3

注意

第一个示例对应于声明中的图片。存在多种解决方案可以精确反转 $$$2$$$ 路段的交通方向,但仅反转 $$$1$$$ 路段永远无法从任何其他路段到达每个交叉路口。下图显示了一种可能的解决方案,其中倒置的路段以蓝色突出显示。

在第二个示例中,答案是 $$$0$$$,因为已经可以从任何其他路口到达每个路口。