Lights Off

题目描述

注意：本题时间限制为 4s，是默认值的两倍。 Bessie 想睡觉，但农场的灯一直亮着让她无法入睡。她该如何把它们关掉？

Bessie 有两个长度为 $N$（$2\le N\le 20$）的二进制串，分别表示一排灯和一排开关。每盏灯要么亮（1）要么灭（0）。每个开关要么处于激活（1）要么未激活（0）。

一次 操作（move） 由以下步骤依次组成： 切换（toggle）恰好一个开关（若未激活则设为激活，反之亦然）。 对于每一个处于激活状态的开关，切换对应那盏灯的状态（若亮则灭，反之亦然）。 将开关循环右移一位。具体地，若表示开关的二进制串初始为 $s_0s_1\dots s_{N-1}$，则变为 $s_{N-1}s_0s_1\dots s_{N-2}$。

对于上述问题的 $T$（$1\le T\le 2\cdot 10^5$）组实例，求将所有灯都关掉所需的最少操作次数。

输入格式

第一行包含 $T$ 和 $N$。 接下来 $T$ 行，每行包含一对长度为 $N$ 的二进制串。

输出格式

对于每一对二进制串，输出将所有灯关闭所需的最少操作次数。

4 3
000 101
101 100
110 000
111 000

0
1
3
2

1 10
1100010000 1000011000

2

提示

第一组样例：灯已经全部关闭。 第二组样例：第一次操作翻转第三个开关。 第三组样例：第一次操作翻转第一个开关，第二次操作翻转第二个开关，第三次操作再次翻转第二个开关。 第四组样例：第一次操作翻转第一个开关，第二次操作翻转第三个开关。 可以证明，每种情况下这都是所需的最少操作次数。

可以证明，需要 $2$ 次操作才能将所有灯关闭。 第一次操作翻转第七个开关，然后第二次操作再次翻转该开关。

SCORING: 输入 3-5：$N \le 8$ 输入 6-13：$N\le 18$ 输入 14-20：无额外限制。 题目来源：William Yue, Eric Yang, and Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold